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

• Published in: Computers & industrial engineering 2018-09, Vol.123, p.303-313
• Main Authors: Huang, Shell Ying, Li, Ya
• Format: Article
• Language: English
• Subjects: Container terminals; Dynamic programming; Lower bound; Quay crane scheduling
• ISSN: 0360-8352; 1879-0550
• DOI: 10.1016/j.cie.2018.06.010

•A novel 2-level Dynamic Programming algorithm.•All three shortcomings of bay-based crane scheduling algorithms overcome.•A lower bound to reduce computational time of the algorithm.•Evaluation using real vessel data show close to lower bound scheduling results and short computational time. 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.