Abstract: Based on the analysis of the tugboat scheduling problem, it is formulated as a multiprocessor task scheduling problem(MTSP)that has the characteristics of sharing common machine sets in all stages. Combined with the scheduling theory, a tugboat scheduling model with two stages of operations(berthing/unberthing)and setup times is presented. The algorithm based on the heuristic rules and simulated annealing(HSA)is developed to solve the special MTSP. By the comparison of the results obtained from the algorithm with those based on three existing scheduling rules in practice, the HSA solved results are far less than those from the existing scheduling rules. Thus the effectiveness and efficiency of the proposed approach are verified. Based on that, the scheduling results under different number of tugboats reveal that the overall operation times of tugboats and the average time for each tugboat is contradictory to some degree. By another numerical example, the paper points out that if tugboats return to the anchorage base timely, the overall operation times can be reduced effectively, and thus the utilization rate of tugboats and green transportation can be realized.

Key words: logistics engineering and management, tugboat operation mode optimization, multi-stage common parallel machines, hybrid simulated annealing

摘要： 在对拖轮调度问题进行分析的基础之上,将拖轮调度问题归结为一类具有多阶段共用平行机器特征的多处理器任务调度问题。建立了考虑靠泊与停泊两阶段、考虑切换时间的拖轮调度优化模型,并设计了启发式规则与模拟退火相结合的混合算法(HSA)求解该模型。通过运用所设计算法求解仿真算例,并将其结果与三种基于现行调度规则的调度方案进行比较,验证了模型与算法的高效性。基于此,对不同拖轮数量状态下的调度研究结果显示,拖轮总作业时间与平均单艘拖轮作业时间二者存在着一定的矛盾性;并指出采用拖轮适时返回停泊基地的作业模式,可有效地降低拖轮作业时间,进而提高有限拖轮资源的利用率,实现节能减排、绿色运输。

关键词: 物流工程与管理, 拖轮作业模式优化, 多阶段共用平行机, 混合模拟退火