A Decomposition Heuristic for the Twin Robots Scheduling Problem

被引：21

作者：

Boysen, Nils ^{[1
]}

Briskorn, Dirk ^{[2
]}

Emde, Simon ^{[1
]}

机构：

[1] Univ Jena, Lehrstuhl Operat Management, D-07743 Jena, Germany

[2] Berg Univ Wuppertal, BWL, D-42119 Wuppertal, Germany

来源：

NAVAL RESEARCH LOGISTICS | 2015年 / 62卷 / 01期

关键词：

twin robots scheduling; noncrossing constraints; dynamic programming;

D O I：

10.1002/nav.21610

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This article provides an efficient heuristic based on decomposition for the twin robots scheduling problem (TRSP). TRSP concerns two moving robots executing storage and retrieval requests in parallel along a shared pathway. The depots are located at both ends of the line and a dedicated robot is assigned to each of them. While moving goods between their respective depots and some storage locations on the line, noncrossing constraints among robots need to be considered. Our heuristic uses a dynamic programming framework to determine the schedule of one robot while keeping the other one's fixed. It finds near-optimal solutions even for large problem instances with hundreds of jobs in a short time span. (c) 2014 Wiley Periodicals, Inc. 62:16-22, 2015

引用

页码：16 / 22

页数：7