多停泊基地约束下港口拖轮作业的一体化调度优化

摘要/Abstract

摘要：

在分析拖轮调度问题基本性质的基础上，结合多处理器任务调度理论，构建了以拖轮总作业时间最小化为目标函数、考虑多停泊基地条件下的一体化调度优化模型；针对问题特点设计了混合模拟退火算法并对其进行求解；以二维实整数的方式作为解的表现形式，在初始解的生成过程中加入首艘可用拖轮的启发式规则，并运用三点交叉的方式产生新解.数值实例结果表明，所提出的算法收敛性较好，求解结果比现行调度规则所得结果的优化率提高了20%.对系统参数的分析表明：移泊作业所占比例和到港船舶类型对目标函数的影响较大；在拖轮配备中，总作业时间对拖轮配备情况具有极弱的敏感性，而在不同装卸作业时间下总作业时间的变化无规律性.

关键词: 拖轮调度, 多处理器任务调度, 模拟退火, 多基地, 灵敏度

Abstract:

Based on the analysis of the characteristics of the tugboat scheduling problem, the similarity between the tugboat scheduling problem and the multiprocessor scheduling problem, this paper formulated a 3stage scheduling model considering multianchorage, aimed at minimizing the total tugboat operation times. A hybrid simulated annealing algorithm was designed to solve the proposed problem. A two-dimensional real integer coding was used to illustrate the solution. The heuristics of the first available tugboat was embedded to generate the initial solution, and the threepoint crossover approach was adopted to generate new solutions. Numerical examples prove that the convergence characteristics of the algorithm are good and the results are better than those obtained from the existing scheduling rules by around 20%. Sensitivity analysis of related parameters reveals that the objective function is most sensitive to the proportion of the shifting-berth operation and ship style, slightly changed by the tugboat deployment scheme, and not sensitive to the handling operation times.

Key words: tugboat scheduling, multi-processor tasks scheduling, simulated annealing, multianchorage, sensitivity

中图分类号:

U 692.4

徐奇，边展，陈燕，靳志宏. 多停泊基地约束下港口拖轮作业的一体化调度优化[J]. 上海交通大学学报（自然版）, 2014, 48(1): 132-139.

XU Qi,BIAN Zhan,CHEN Yan,JIN Zhihong. Scheduling Optimization of Port Tugboat Operation Considering Multi-Anchorage[J]. Journal of Shanghai Jiaotong University, 2014, 48(1): 132-139.

参考文献

［1］刘志雄, 王少梅. 带特殊工艺约束的双目标并行多机调度问题研究［J］. 计算机集成制造系统, 2005, 11 (11): 16161620.

LIU Zhixiong, WANG Shaomei. Research on biobjectives parallel machines scheduling problem with special process constraint ［J］. Computer Integrated Manufacturing Systems, 2005, 11 (11): 16161620.

［2］刘志雄, 王少梅. 基于粒子群算法的并行多机调度问题研究［J］. 计算机集成制造系统, 2006, 12 (2): 183187.

LIU Zhixiong, WANG Shaomei. Research on parallel machines scheduling problem based on particle swarm optimization algorithm ［J］. Computer Integrated Manufacturing Systems, 2006, 12 (2): 183187.

［3］刘志雄. 考虑最短距离作业的港口拖轮作业调度优化［J］. 西南交通大学学报, 2011, 46 (5): 875881.

LIU Zhixiong. Port tugboat operation scheduling optimization considering the minimum operation distance ［J］. Journal of Southwest Jiaotong University, 2011, 46 (5): 875881.

［4］Wang S, Bo M. Resource allocation and scheduling problem based on genetic algorithm and ant colony optimization ［J］. Lecture Notes in Artificial Intelligence, 2007, 4426: 879886.

［5］何涛，朱宏辉. 遗传算法在拖轮调度中的应用［J］. 物流技术, 2008, 27 (4): 138139.

HE Tao, ZHU Honghui. Application of genetic algorithm in tugboat scheduling ［J］. Logistics Technology, 2008, 27 (4): 138139.

［6］He Tao, Ye Wen. Hybrid evolutionary strategy optimization for port tugboat operation scheduling ［C］∥2nd International Conference on Information Science and Engineering. USA: IEEE Computer Society, 2010: 14381441.

［7］李东辉，张均东，何治斌．教学实习船电力系统建模与仿真［J］．上海交通大学学报, 2008, 42 (2): 190193．

LI Donghui, ZHANG Jundong, HE Zhibin. Modeling and simulation of the power system on practice teaching ship ［J］. Journal of Shanghai Jiaotong University, 2008, 42 (2): 190193.

［8］Xu Q, Shao Q Q, Jin Z H. Optimization on tugboat operation scheduling based upon the hybrid simulated annealing ［C］∥The International Association of Maritime Economists Conference. Canada: IAME publisher, 2012.

［9］董良才，徐子奇，宓为建. 基于遗传算子粒子群算法的拖轮动态调度［J］. 数学的实践与认识, 2012, 42 (6): 122133.

DONG Liangcai, XU Ziqi, MI Weijian. The dynamic tugboat schedule based on particle swarm algorithm combined with genetic operators ［J］. Mathematics in Practice and Theory, 2012, 42 (6): 122133.

［10］计明军. 若干随机性全局优化算法的研究［D］. 大连: 大连理工大学应用数学系, 2004.

［11］靳志宏，计明军. 物流实用优化技术［M］. 北京: 中国物资出版社, 2008.

[1]	方晓涛, 严正, 王晗, 徐潇源, 陈玥. 考虑概率电压不平衡度越限风险的共享储能优化运行方法[J]. 上海交通大学学报, 2022, 56(7): 827-839.
[2]	吴庶宸, 戚宗锋, 李建勋. 基于深度学习的智能全局灵敏度分析[J]. 上海交通大学学报, 2022, 56(7): 840-849.
[3]	陈乐，王英，李海华. 基于三明治结构的高灵敏度新型电子皮肤[J]. 上海交通大学学报, 2020, 54(5): 499-506.
[4]	王鉴, 赵宏宇, 钟继鸿, 王孟渝, 蔡志俊. 临近空间飞行器的鲁棒控制器设计[J]. 空天防御, 2019, 2(3): 53-58.
[5]	骞华楠，陶璟，于随然. 高精度压力机连杆机构的误差分析及精度综合[J]. 上海交通大学学报（自然版）, 2019, 53(3): 269-275.
[6]	范厚明，马梦知，姚茜,郭振峰. 集装箱堆场箱位分配及多场桥调度协同优化问题[J]. 上海交通大学学报（自然版）, 2017, 51(11): 1367-1373.
[7]	赵志诚,王惠芳,张井岗. 高阶反向响应过程的分数阶PID控制器设计[J]. 上海交通大学学报（自然版）, 2015, 49(08): 1090-1095.
[8]	陈曜1，2，何鹏程1，卜天容1，丁玉丽1，韦以明1. 高灵敏马赫泽德环形谐振腔[J]. 上海交通大学学报（自然版）, 2014, 48(10): 1406-1409.
[9]	李亮亮，杜正春. 一种新型五轴加工中心误差测量装置的模型分析[J]. 上海交通大学学报（自然版）, 2013, 47(11): 1801-1806.
[10]	黎渊1, 蒋江2, 张民选1, 魏少军3 . 基于模拟退火算法的浮点转定点自动位宽优化工具[J]. 上海交通大学学报（自然版）, 2013, 47(01): 76-80.
[11]	袁立鹏,崔淑梅，卢红影，李尚义. 基于模拟退火遗传算法的电液伺服马达超低速性能 [J]. 上海交通大学学报（自然版）, 2010, 44(12): 1741-1746.
[12]	董明，吴一帆，吴畅，侯文皓. 随机需求下半导体生产车间的物流系统仿真优化[J]. 上海交通大学学报（自然版）, 2010, 44(03): 306-0310.
[13]	张勇，李光耀. 基于序列响应面方法的汽车板选材优化设计[J]. 上海交通大学学报（自然版）, 2010, 44(01): 62-0067.