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

摘要： 受电缆线坑位置与缆线长度的限制，岸桥作业只能在一定的横向移动范围之内。考虑到这一现实要求，结合岸桥作业禁止跨越与安全距离等特有约束，以最小化装卸作业的makespan为目标，构建了新的岸桥作业调度混合整数规划模型。针对问题的NP-hard特性，设计了一种混合模拟退火算法，运用启发式算法生成质量较高的初始解，结合遗传算法的变异运算生成邻域新解，增强了解的多样性，引入禁忌搜索算法的禁忌表操作，避免了循环搜索，提高了求解效率。大规模实验结果表明所建立的模型是有效的，算法的求解质量与效率明显优于标准模拟退火算法与禁忌搜索算法。当实验规模逐渐增大时，与LINGO软件相比，算法在求解效率方面的优势越来越明显。

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