An approximation algorithm for quay crane scheduling with handling priority in port container terminals

Abstract

The quay crane scheduling problem studied in this article is to determine the handling sequence of ship bays for quay cranes assigned to a container ship considering handling priority of every ship bay. This article provides a mixed integer programming model for the considered quay crane scheduling problem that is NP-complete in nature. An approximation algorithm is proposed to obtain near optimal solutions and a worst-case analysis for the approximation algorithm is performed. Computational experiments are conducted to examine the proposed model and solution algorithm. The computational results show that the proposed approximation algorithm is effective and efficient in solving the considered quay crane scheduling problem. © 2010 Taylor & Francis.