关键词: 岸桥作业调度, 最大完工时间, 有限作业范围, 混合整数规划, 混合模拟退火算法

Abstract: Because of the restrictions of cable pit location and cable length, quay crane can only move along the quayside within a certain range. Considering this practical characteristic, non-crossing and safety constraints, a new mixed integer programming model for quay crane scheduling with operation range constraints is established, which can minimize makespan of loading/unloading tasks. Because it is NP-hard in nature, a hybrid simulated annealing algorithm is designed to obtain the near optimal solutions. A heuristics algorithm is developed to find a good initial solution. A mutation operator from GA is proposed to obtain a suitable neighborhood solution which can provide a higher degree of solution diversification. The tabu list concept from the tabu search is adopted and embedded in the framework of the SA algorithm to prevent cycling. Computational experimental results show that the model is effective. The computational time and optimal solution of hybrid SA are superior to simple SA and TS. And the solving efficiency of hybrid SA is better than LINGO software when the instances become larger.

Key words: quay crane scheduling, makespan, finite operation range, mixed integer programming, hybrid simulated annealing algorithm