A Linear Time Algorithm for Optimal Quay Crane Scheduling

Mathias Offerlin Herup; Gustav Christian Wichmann Thiesgaard; Jaike van Twiller; Rune Møller Jensen

doi:10.1007/978-3-031-16579-5_5

A Linear Time Algorithm for Optimal Quay Crane Scheduling

Mathias Offerlin Herup, Gustav Christian Wichmann Thiesgaard, Jaike van Twiller, Rune Møller Jensen

Computer Science

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Abstract

This paper studies the Quay Crane Scheduling Problem (QCSP). The QCSP determines how a number of quay cranes should be scheduled in order to service a vessel with minimum makespan. Previous work considers the QCSP to be a combinatorially hard problem. For that reason, the focus has been on developing efficient heuristics. Our study shows, however, that the QCSP is tractable in the realistic setting, where quay cranes can share the workload of bays. We introduce a novel linear time algorithm that solves the QCSP and prove its correctness.

Original language	English
Title of host publication	International Conference on Computational Logistics : Lecture Notes in Computer Science
Number of pages	13
Volume	13557
Publisher	Springer
Publication date	14 Sept 2022
Pages	60–73
DOIs	https://doi.org/10.1007/978-3-031-16579-5_5
Publication status	Published - 14 Sept 2022
Event	International Conference on Computational Logistics 2022 - Universitat Pompeu Fabra, Barcelona, Spain Duration: 21 Sept 2022 → 23 Sept 2022 https://eventum.upf.edu/78123/detail/international-conference-on-computational-logistics-iccl-2022.html

Conference

Conference	International Conference on Computational Logistics 2022
Location	Universitat Pompeu Fabra
Country/Territory	Spain
City	Barcelona
Period	21/09/2022 → 23/09/2022
Internet address	https://eventum.upf.edu/78123/detail/international-conference-on-computational-logistics-iccl-2022.html

Keywords

Quay crane scheduling
Container terminals
Computational complexity

Access to Document

10.1007/978-3-031-16579-5_5

A_linear_time_scheduling_algorithm_for_container_terminal_quay_cranes_with_minimum_makespan_PAPERAccepted author manuscript, 5.94 MB

Cite this

@inproceedings{427a3428e70d41c1a59451f5be0dd4a6,

title = "A Linear Time Algorithm for Optimal Quay Crane Scheduling",

abstract = "This paper studies the Quay Crane Scheduling Problem (QCSP). The QCSP determines how a number of quay cranes should be scheduled in order to service a vessel with minimum makespan. Previous work considers the QCSP to be a combinatorially hard problem. For that reason, the focus has been on developing efficient heuristics. Our study shows, however, that the QCSP is tractable in the realistic setting, where quay cranes can share the workload of bays. We introduce a novel linear time algorithm that solves the QCSP and prove its correctness.",

keywords = "Quay crane scheduling, Container terminals, Computational complexity",

author = "Herup, {Mathias Offerlin} and Thiesgaard, {Gustav Christian Wichmann} and {van Twiller}, Jaike and Jensen, {Rune M{\o}ller}",

year = "2022",

month = sep,

day = "14",

doi = "10.1007/978-3-031-16579-5_5",

language = "English",

volume = "13557",

pages = "60–73",

booktitle = "International Conference on Computational Logistics",

publisher = "Springer",

address = "Germany",

note = "International Conference on Computational Logistics 2022, ICCL2022 ; Conference date: 21-09-2022 Through 23-09-2022",

url = "https://eventum.upf.edu/78123/detail/international-conference-on-computational-logistics-iccl-2022.html",

}

Herup, MO, Thiesgaard, GCW, van Twiller, J & Jensen, RM 2022, A Linear Time Algorithm for Optimal Quay Crane Scheduling. in International Conference on Computational Logistics: Lecture Notes in Computer Science. vol. 13557, Springer, pp. 60–73, International Conference on Computational Logistics 2022, Barcelona, Spain, 21/09/2022. https://doi.org/10.1007/978-3-031-16579-5_5

A Linear Time Algorithm for Optimal Quay Crane Scheduling. / Herup, Mathias Offerlin; Thiesgaard, Gustav Christian Wichmann; van Twiller, Jaike et al.
International Conference on Computational Logistics: Lecture Notes in Computer Science. Vol. 13557 Springer, 2022. p. 60–73.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

TY - GEN

T1 - A Linear Time Algorithm for Optimal Quay Crane Scheduling

AU - Herup, Mathias Offerlin

AU - Thiesgaard, Gustav Christian Wichmann

AU - van Twiller, Jaike

AU - Jensen, Rune Møller

PY - 2022/9/14

Y1 - 2022/9/14

N2 - This paper studies the Quay Crane Scheduling Problem (QCSP). The QCSP determines how a number of quay cranes should be scheduled in order to service a vessel with minimum makespan. Previous work considers the QCSP to be a combinatorially hard problem. For that reason, the focus has been on developing efficient heuristics. Our study shows, however, that the QCSP is tractable in the realistic setting, where quay cranes can share the workload of bays. We introduce a novel linear time algorithm that solves the QCSP and prove its correctness.

AB - This paper studies the Quay Crane Scheduling Problem (QCSP). The QCSP determines how a number of quay cranes should be scheduled in order to service a vessel with minimum makespan. Previous work considers the QCSP to be a combinatorially hard problem. For that reason, the focus has been on developing efficient heuristics. Our study shows, however, that the QCSP is tractable in the realistic setting, where quay cranes can share the workload of bays. We introduce a novel linear time algorithm that solves the QCSP and prove its correctness.

KW - Quay crane scheduling

KW - Container terminals

KW - Computational complexity

U2 - 10.1007/978-3-031-16579-5_5

DO - 10.1007/978-3-031-16579-5_5

M3 - Article in proceedings

VL - 13557

SP - 60

EP - 73

BT - International Conference on Computational Logistics

PB - Springer

T2 - International Conference on Computational Logistics 2022

Y2 - 21 September 2022 through 23 September 2022

ER -

A Linear Time Algorithm for Optimal Quay Crane Scheduling

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this