Approximation algorithms for the twin robot scheduling problem

Florian Jaehn () and Andreas Wiehl ()
Additional contact information
Florian Jaehn: Helmut-Schmidt-University

Journal of Scheduling, 2020, vol. 23, issue 1, No 6, 117-133

Abstract: Abstract We consider the $$\mathscr {NP}$$NP-hard twin robot scheduling problem, which was introduced by Erdoğan et al. (Naval Res Logist (NRL) 61(2):119–130, 2014). Here, two moving robots positioned at the opposite ends of a rail have to perform automated storage and retrieval jobs at given positions along the gantry rail with a non-crossing constraint. The objective is to minimize the makespan. We extend the original problem by considering pickup and delivery times and present exact and approximation algorithms with a performance ratio of $$\approx \,1.1716$$≈1.1716 for large instances. Further, we compare the presented algorithms in a comprehensive numerical study.

Keywords: Automated storage and retrieval systems; Non-crossing constraints; Approximation algorithms; Crane scheduling (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-019-00631-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:23:y:2020:i:1:d:10.1007_s10951-019-00631-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-019-00631-9

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().