A Linear Time Algorithm for Optimal Quay Crane Scheduling

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

    Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-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 languageEnglish
    Title of host publication International Conference on Computational Logistics : Lecture Notes in Computer Science
    Number of pages13
    Volume13557
    PublisherSpringer
    Publication date14 Sept 2022
    Pages60–73
    DOIs
    Publication statusPublished - 14 Sept 2022
    EventInternational Conference on Computational Logistics 2022 - Universitat Pompeu Fabra, Barcelona, Spain
    Duration: 21 Sept 202223 Sept 2022
    https://eventum.upf.edu/78123/detail/international-conference-on-computational-logistics-iccl-2022.html

    Conference

    ConferenceInternational Conference on Computational Logistics 2022
    LocationUniversitat Pompeu Fabra
    Country/TerritorySpain
    CityBarcelona
    Period21/09/202223/09/2022
    Internet address

    Keywords

    • Quay crane scheduling
    • Container terminals
    • Computational complexity

    Fingerprint

    Dive into the research topics of 'A Linear Time Algorithm for Optimal Quay Crane Scheduling'. Together they form a unique fingerprint.

    Cite this