Article ID: | iaor20164347 |
Volume: | 49 |
Issue: | 4 |
Start Page Number: | 957 |
End Page Number: | 967 |
Publication Date: | Nov 2015 |
Journal: | Transportation Science |
Authors: | Lee Chung-Yee, Chu Chengbin, Liu Ming |
Keywords: | supply & supply chains, combinatorial optimization, scheduling, heuristics |
Quay crane efficiency is the key bottleneck for container port productivity. An important issue of container terminal optimization is the quay crane double‐cycling problem (QCDCP). For the simple scenario without hatch covers, a two‐machine flow shop scheduled model can be formulated that can be solved by Johnson’s rule. For the general QCDCP with hatch covers, the state‐of‐the‐art solution approaches are only heuristics. The computational complexity of the problem, however, remains an open question. This paper focuses on the general QCDCP. We investigate the computational complexity of the problem, by showing that it can be formulated as a flow shop scheduling problem with series‐parallel precedence constraints, thus allowing it to be solved polynomially. For ease of implementation, we present an optimal algorithm for the general QCDCP, which is a special and simplified version of Sidney’s algorithm.