A decomposition heuristic for the twin robots scheduling problem. (2nd December 2014)

• Record Type: Journal Article
• Authors: Boysen, Nils; Briskorn, Dirk; Emde, Simon
• Is Part Of: Naval research logistics. Volume 62:Number 1(2015:Feb.)
• Page Start: 16
• Page End: 22
• Publication Date: 2014-12-02
• Subjects: Logistics, Naval -- Periodicals; Supplies and stores -- Periodicals; 359.07
• DOI: 10.1002/nav.21610
• Languages: English
• ISSNs: 0894-069X

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>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. © 2014 Wiley Periodicals, Inc. 62:16–22, 2015</p> </abstract>