  In this work we propose a decomposition approach to solve the quay crane
scheduling problem. This is an important maritime transportation problem faced
in container terminals where quay cranes are used to handle cargo. The
objective is to determine a sequence of loading and unloading operations for
each crane in order to minimize the completion time. We solve a mixed integer
programming formulation for the quay crane scheduling problem, decomposing it
into a vehicle routing problem and a corresponding scheduling problem. The
routing sub-problem is solved by minimizing the longest crane completion time
without taking crane interference into account. This solution provides a lower
bound for the makespan of the whole problem and is sent to the scheduling
sub-problem, where a completion time for each task and the makespan are
determined. This scheme resembles Benders' decomposition and, in particular,
the scheme underlying combinatorial Benders' cuts. We evaluate the proposed
approach by solving instances from the literature and comparing the results
with other available methods.
