最小化最大完工时间与等待时间的岸桥作业调度双目标优化及其遗传算法

A Genetic Algorithm to Minimize the Makespan and Waiting Time for the Bi-Objective Quay Crane Scheduling Problem

分析了岸桥支援对船舶装卸作业效率的影响,指出减少岸桥等待时间,有利于加强岸桥支援,并能提高码头整体运作效率。考虑岸桥作业不可相互穿越与安全距离等特有约束,建立了岸桥作业调度双目标混合整数规划模型,其优化目标是最小化最大完工时间与岸桥等待时间。针对该问题的NP-hard特性,设计了一种遗传算法,对算法搜索空间进行了讨论,并推导了问题的一个下界。数据实验表明,所建立的模型能够在最小化最大完工时间的同时,有效地减少岸桥等待现象的发生,其算法在允许的运算时间内能获得稳定的满意解。

This paper analyzes the influence of quay crane movements among several vessels on the efficiency of loading and unloading operations, and suggests that the waiting time of quay crane should beshortened to enhance the productivity of quay crane. Given the non-crossing and safety constraints, we establish a mixed integer programming model for quay crane scheduling problem, with the bi-objective tominimize the makespan of a vessel and the waiting time of the quay crane. Because of its NP-hard nature, a genetic algorithm is designed to obtain the near optimal solutions. A lower-bound is established tofacilitate the effectiveness searching of the proposed algorithm. Computational study shows that the MIP model can minimize the makespan of a vessel, while effectively reduce the quay crane＇s waiting time, andthe algorithm can find stable and satisfying solutions in a reasonable amount of CPU time.