Abstract: In order to improve the efficiency of container port services and reduce the tardiness costs of ship services, a new mathematical model was established with the objective of minimizing the sojourn time of the ships and the total tardiness for the tug-berth joint scheduling problem under the established conditions of port hardwares (berths, tugboats, quay cranes), and a hybrid algorithm was designed for solving it. Firstly, the serial hybrid strategy of Quantum Genetic Algorithm (QGA) and Tabu Search (TS) algorithm was analyzed and determined. Secondly, according to the characteristics of the joint scheduling problem, the update strategy of dynamic quantum revolving gate was adopted when solving key problems in the executing process of the hybrid algorithm (chromosome structure design and measurement, genetic manipulation, population regeneration, etc.). Finally, the feasibility and effectiveness of the algorithm were verified by the production examples. The experimental results show that compared with results of manual scheduling, the sojourn time of the ships and total tardiness of the hybrid algorithm are reduced by 24% and 42.7% respectively; compared with the results of genetic algorithm, they are reduced by 10.9% and 22.5% respectively. The proposed model and algorithm can not only provide optimized operation schemes for berthing, unberthing as well as loading and unloading operations of port ships, but also increase the port competitiveness.

Key words: joint scheduling, tardiness, Quantum Genetic Algorithm (QGA), Tabu Search (TS), dynamic quantum revolving gate

摘要： 为了提高集装箱港口服务效率，减少船舶服务的拖期费用，针对港口硬件（泊位、拖轮、岸桥）既定条件下的拖轮-泊位联合调度问题，新建了以最小化总体船舶在港时间和总拖期时间为目标的数学模型，设计了一种混合算法进行求解。首先，分析确定了将量子遗传算法（QGA）和禁忌搜索（TS）算法进行串行混合的策略；然后，依据该联合调度问题特点，在解决算法实施中的关键技术问题（染色体结构设计和测量、遗传操作、种群更新等）的同时，采用了动态量子旋转门更新机制；最后，用生产实例验证了算法的可行性及有效性。算法实验结果表明，与人工调度结果相比，混合算法的总体船舶在港时间和总拖期时间分别减少了24%和42.7%；与遗传算法结果相比，分别减少了10.9%和22.5%。所提模型及算法不仅能为港口船舶的入泊、离泊和装卸作业环节提供优化作业方案，而且能增强港口竞争力。

关键词: 联合调度, 拖期, 量子遗传算法, 禁忌搜索, 动态量子旋转门