A Linear Time Algorithm for Optimal Quay Crane Scheduling

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.