A bounded two-level dynamic programming algorithm for quay crane scheduling in container terminals

• Main Authors: Huang, Shell Ying, Li, Ya
• Other Authors: School of Computer Science and Engineering
• Format: Article
• Language: English
• Published: 2018
• Subjects: Quay Crane Scheduling; Container Terminals; DRNTU::Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/89771; http://hdl.handle.net/10220/46732
• Institution: Nanyang Technological University

One of the optimization problems in terminal operations is the quay crane scheduling problem. The quay crane scheduling algorithm plays a critical role because it directly affects the length of the vessel loading and unloading process, which means vessel turnaround time. We propose a bounded two-level dynamic programming (DP) algorithm which keeps the simplicity of the bay-based approach but overcomes its shortcomings. We also propose a method to estimate the lower bound to quay crane scheduling given the lists of unloading and loading containers and the number of quay cranes assigned to the vessel. This lower bound is used both to reduce computational time of the 2-level DP algorithm and to evaluate our crane scheduling method. Our experiments with real vessel unloading and loading lists for 80 vessels show that the vessel makespan is close to the lower bound. The computational times for the 80 vessels with up to 6600 container moves by cranes in loading and unloading a vessel are all under two minutes.