考虑任务优先约束的同类岸桥作业调度优化

Modeling and Solving Uniform Quay Crane Scheduling Problem with Task Precedence Constraints

分析了以箱组为任务对象QCSP与以整贝为任务对象QCSP的异同,指出前者更能均衡各岸桥作业负荷,并减少船舶装卸作业时间。考虑到岸桥具有作业效率差异的特点,将其视为同类平行机调度问题,同时结合任务优先约束、岸桥作业不可相互穿越与安全距离等特有约束,建立了更加符合实际的以箱组为任务对象的岸桥作业调度混合整数规划模型,其优化目标是最小化装卸作业的makespan。针对模型求解的复杂度,设计了一种遗传算法,对算法搜索空间进行了讨论,并推导了问题的低界。实验算例表明所建立的模型能够反映岸桥作业调度过程中作业效率差异及任务优先约束现象,其算法能够在允许的运算时间内获得稳定的满意解,并且优化结果要全面优于以整贝为任务对象QCSP的调度方案。

Through the analysis of the influence of difference between QCSP with container groups and QcsP with complete bays, it is pointed out that QCSP with container groups can achieve balance for workload of every quay crane easierly and shorten the makespan of the container vessel. Considering operation efficiency difference a- mong quay cranes, the quay crane scheduling is analyzed as uniform parallel machine scheduling with the task precedence constraints, non -crossing and safety constraints. A new mixed integer programming model for quay crane scheduling with container groups is established, so as to minimize the makespan. Because of its difficulty, a genetic algorithm is designed to obtain the near optimal solutions. A lowerbound is given to evaluate the effec- tiveness of the proposed algorithm. Random instances show that the model can reflect the situation of operation efficiency difference and task precedence constraints. And the results of GA are stable and acceptable in allowa- ble CPU time. Meanwhile, the optimization results in this paper outperform schemes from QCSP with complete bays.