Dynamic programming approach on quay crane scheduling in container ports

Abstract

Efficient quay crane scheduling in container terminals is crucial for minimising vessel turnaround times and improving port throughput. This Final Year Project extends the work presented in the bounded two-level Dynamic Programming (DP) algorithm for the Quay Crane Scheduling Problem (QCSP) in container terminals, by thoroughly investigating and enhancing this method for practical application. The first layer applies a bounded DP approach to allocate bays among cranes while strictly enforcing non-crossing and minimum safety distance constraints. A memoisation table and lower-bound estimates optimise performance, making the method scalable for real-world scenarios. The second layer refines workload balance by redistributing partial "boundary lumps" from the first layer. Multiple strategies are explored, including fixed-chunk splits (3, 7, or 11 sub-lumps) and a binary-search approach for finer workload adjustments. Multi-pass expansions further assess whether repeated refinements improve makespan. Extensive evaluations across eight distinct workload distributions (e.g., left-heavy, right-heavy, single large bay) confirm that partial lumps consistently reduce makespan compared to the first-layer DP alone. While all second-layer strategies improve balance, binary search and finer 11-chunk splits yield the best results, especially in imbalanced cases. However, multi-pass refinements show diminishing returns beyond the first pass, and certain cases exhibit no additional gains. Overall, this project demonstrates that a two-layer DP framework—when extended and thoroughly evaluated—is both computationally practical and effective for quay crane scheduling. The approach meets its objectives and provides insights for future research, including adaptive chunking, real-time integration, and co-optimisation with berth and yard scheduling.