An exact solution approach for scheduling cooperative gantry cranes
Publication date
2019-08-06
Document type
Forschungsartikel
Author
Organisational unit
Universität Siegen
Publisher
Elsevier
Series or journal
European Journal of Operational Research
ISSN
Periodical volume
273
Periodical issue
1
First page
82
Last page
101
Peer-reviewed
✅
Part of the university bibliography
✅
Language
English
Keyword
Scheduling
Container logistics
Seaport logistics
Twin cranes
Crane scheduling
Abstract
We consider a scheduling problem for two gantry cranes moving on the same rails at a single storage block. Containers originating at the seaside have to be stored in the block and containers that are already stored in the storage area at the beginning of the planning horizon have to be delivered to the landside handover point within given time windows. Most commonly in seaport operations, the berthing time of vessels is to be minimized. Thus, the objective considered in this article is to minimize the makespan of seaside container processing while guaranteeing on-time processing of landside containers and while considering non-crossing constraints among cranes. We allow preemption of seaside container processing. This means that one crane may move a seaside container to an intermediate storage slot, and the other crane takes it to its designated position. This has previously been shown to be an effective method of reducing the makespan when compared to classical approaches. We present a dynamic programming (DP) algorithm and a related beam search heuristic. The DP method makes use of bounding techniques and applies dominance properties of optimal solutions. In computational tests, we show that the DP approach clearly outperforms CPLEX and that it is able to quickly solve instances with real-world yard settings. The beam search heuristic is shown to be capable of quickly improving solutions of heuristic approaches that have previously been introduced in the literature. This allows both algorithms to be applied in real-world online settings, where container data is revealed incrementally.
Version
Published version
Access right on openHSU
Metadata only access