Abstract: This paper focuses on the quay crane scheduling on one vessel, and suggests that the idle of crane will affect the efficiency of the whole container terminal. We consider a single container as task unit and constrains such as quay crane's moving time and safe margin and establish a multi-objective programming model to minimize the vessel completion time and crane idle time. Noticing the lower bound of completion time, the problem will be divided into two situations:determined by the workload of key bays and determined by average workload. Respectively, we proposed the heuristic algorithm based on neighborhood search and "bay segmentation" algorithm based on the greedy strategy, and proved that in the case where the lower bound is determined by the average workload, our algorithm will not lead to idle of any cranes. The results of numerical experiments with different scales and lower bounds show that the quay crane schedule obtained by our model and algorithm are more suitable for actual production operation, and can effectively approach the lower bound of the completion time. The algorithm has a significant improvement in the speed of the algorithm with the existing research.

Key words: quay crane scheduling, multi-objective programming, heuristic algorithm