Approximation algorithms for the twin robot scheduling problem

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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of scheduling 2020-02, Vol.23 (1), p.117-133
Main Authors: Jaehn, Florian, Wiehl, Andreas
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Artificial Intelligence
Business and Management
Calculus of Variations and Optimal Control
Optimization
Job shops
Mathematical analysis
Operations Research/Decision Theory
Optimization
Production scheduling
Robots
Scheduling
Supply Chain Management
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1094-6136
1099-1425
DOI:10.1007/s10951-019-00631-9