On the Complexity of Crane Scheduling

Maximilian Aspern ()
Additional contact information
Maximilian Aspern: Technische Universität München

A chapter in Operations Research Proceedings 2024, 2025, pp 16-22 from Springer

Abstract: Abstract Motivated by a real-world application in industrial storage yards, we consider the problem of scheduling predetermined container relocation moves by an automated twin-crane system. In this setting, two gantry cranes operate in parallel on a grid of container stacks but cannot pass each other. The goal is to minimize the total time required to perform all given operations. We show that this problem, which we call Twin-Crane Scheduling, is APX-hard. More precisely, the problem cannot be approximated within a factor smaller than 1.01 unless P = NP. However, we show that the optimal solution can easily be approximated within a factor of 2 through a simple list scheduling algorithm.

Keywords: Scheduling; Computational Complexity; Approximation Algorithms (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:lnopch:978-3-031-92575-7_3

Ordering information: This item can be ordered from
http://www.springer.com/9783031925757

DOI: 10.1007/978-3-031-92575-7_3

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().