Approximation algorithms for the twin robot scheduling problem

Jaehn, Florian; Wiehl, Andreas

doi:10.1007/s10951-019-00631-9

Approximation algorithms for the twin robot scheduling problem

Publication date

2020-01-07

Document type

Forschungsartikel

Author

Jaehn, Florian

Wiehl, Andreas

Organisational unit

BWL, insb. Management Science und Operations Research

DOI

10.1007/s10951-019-00631-9

URI

https://openhsu.ub.hsu-hh.de/handle/10.24405/22492

Scopus ID

2-s2.0-85077585653

Publisher

Springer

Series or journal

Journal of Scheduling

ISSN

1094-6136

Periodical volume

23

Periodical issue

1

First page

117

Last page

133

Peer-reviewed

✅

Part of the university bibliography

✅

Language

English

Keyword

Approximation algorithms

Automated storage and retrieval systems

Crane scheduling

Non-crossing constraints

Abstract

We consider the 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 ≈1.1716 for large instances. Further, we compare the presented algorithms in a comprehensive numerical study.

Version

Published version

Access right on openHSU

Metadata only access