Optimal Algorithm for the General Quay Crane Double-Cycling Problem

Optimal Algorithm for the General Quay Crane Double-Cycling Problem

0.00 Avg rating0 Votes
Article ID: iaor20164347
Volume: 49
Issue: 4
Start Page Number: 957
End Page Number: 967
Publication Date: Nov 2015
Journal: Transportation Science
Authors: , ,
Keywords: supply & supply chains, combinatorial optimization, scheduling, heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.