基于粒子群算法的并行多机调度问题研究

• 论文 •

基于粒子群算法的并行多机调度问题研究

刘志雄，王少梅

1.武汉科技大学机械自动化学院，湖北武汉 430081；2.武汉理工大学物流工程学院，湖北武汉 430063

收稿日期:2004-11-22 修回日期:2005-01-17 出版日期:2006-02-15 发布日期:2006-02-25
基金资助:
武汉科技大学机械传动与制造工程湖北省重点实验室开放基金资助项目(2005A17)。

Research on parallel machines scheduling problem based on particle swarm optimization algorithm

LIU Zhi-xiong,WANG Shao-mei

1.Coll. of Machinery & Automation, Wuhan Univ. of S & T, Wuhan 430081, China; 2.Coll. of Logistics Eng., Wuhan Univ. of Tech., Wuhan 430063, China

Received:2004-11-22 Revised:2005-01-17 Online:2006-02-15 Published:2006-02-25
Supported by:
The Open Research Projects Supported by the Project Fund of the Hubei Province Key Laboratory of Mechanical Transmission and Manufacturing Engineering Wuhan University of S&T,China(No.2005A17).

摘要/Abstract

摘要： 将港口拖轮作业调度问题描述为一类带特殊工艺约束的并行多机调度问题，采用粒子群算法求解该类调度问题，提出了一种2维粒子表示方法，通过对粒子位置向量进行排序生成有效调度，并采用粒子位置向量多次交换的局部搜索方法来提高算法的搜索效率。最后，通过计算验证了混合粒子群算法的有效性。

关键词: 粒子群算法, 并行多机调度, 特殊工艺约束, 港口拖轮调度

Abstract: Port tugboat operation scheduling is regarded as parallel machines scheduling problem with special process constraint. Particle swarm optimization algorithm was used to solve the scheduling problem. The two-dimensional particle representation of parallel machines scheduling was proposed, and valid scheduling was generated by sequencing position vectors of particles. The local search approach of repeated interchanges of the particle position vectors was proposed to improve search efficiency. Finally the hybrid particle swarm algorithm was validated by computation.

Key words: particle swarm optimization algorithm, parallel machines scheduling, special process constraint, port tugboat scheduling

中图分类号:

TP18

刘志雄,，王少梅. 基于粒子群算法的并行多机调度问题研究[J]. .

LIU Zhi-xiong,,WANG Shao-mei. Research on parallel machines scheduling problem based on particle swarm optimization algorithm[J]. .

参考文献

［1］ KENNEDY J,EBERHART R C.Particle swarm optimization［A］.Proceedings of IEEE International Conference on Neutral Networks［C］.Piscatwang,NY,USA:IEEE Service Center,1995.1942-1948.

[2] EBERHART R C,SHI Y H.Particle swarm optimization:development,applications and resources［A］.Proceedings of Congress on Evolutionary Computation［C］.Piscatwang,NJ,USA:IEEE Service Center,2001.81-86.

[3] ZHOU Chi,GAO Haibing,GAO Liang,et al.Particle Swarm Optimization(PSO) algorithm［J］.Journal of Computer Application and Research,2003,21(12):5-11(in Chinese).［周驰，高海兵，高亮，等.粒子群优化算法［J］.计算机应用研究,2003,21(12):5-11.］

[4] LI Ning,ZOU Tong,SUN Debao.Particle swarm optimization for vehicle routing problem with time windows［J］.System Engineering—Theory & Practice,2004,24(4):130-135(in Chinese).［李宁，邹彤，孙德宝.带时间窗车辆路径问题的粒子群算法［J］.系统工程理论与实践,2004,24(4):130-135.］

[5] HUANG Lan,WANG Kangping,ZHOU Chunguang,et al.Particle swarm optimization for traveling salesman problems［J］.Journal of Jilin University,2003,141(4):477-480(in Chinese).［黄岚，王康平，周春光，等.粒子群优化算法求解旅行商问题［J］.吉林大学学报，2003,141(4):477-480.］

[6] TASGETIRN M F,LIANG Y C,SEVKLI M,et al.Particle swarm optimization algorithm for makespan and total flowtime minimization in permutation flowshop sequencing problem［EB/OL］.http://www.fatih.edu.tr/～ftasgetiren/download/EJOR_FTASGETIREN,2004-11-18.

[7] LIU Zhixiong,WANG Shaomei.The computer simulation study of port tugboat operation［J］.Journal of System Simulation,2004,16(1):45-47(in Chinese).［刘志雄，王少梅.港口拖轮作业的计算机仿真研究［J］.系统仿真学报,2004,16(1):45-47.］

[1]	袁友伟,黄锡恺,俞东进,李忠金. 移动边缘计算环境下服务工作流容错调度算法[J]. 计算机集成制造系统, 2021, 27(6): 1693-1702.
[2]	吴暖,王诺,于安琪,吴迪. 基于柔性靠泊的港口疏船调度多目标优化及最优解选择[J]. 计算机集成制造系统, 2021, 27(5): 1531-1540.
[3]	高鹏,苏雍贺,靳健,谢祥颖,张长志,陶飞. 基于分布式光伏运维的多类型资源调度技术[J]. 计算机集成制造系统, 2021, 27(3): 787-799.
[4]	顾文斌,李育鑫,钱煜晖,肖紫涵,秦展鹏. 基于激素调节机制IPSO算法的相同并行机混合流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(10): 2858-2871.
[5]	刘亿鑫,朱小林. 双重不确定条件下危险品运输的多目标优化[J]. 计算机集成制造系统, 2020, 26(第4): 1130-1141.
[6]	陶俐言,赵鹏翡,陈冉冉. 基于动态机器故障率的并联加工系统资源多目标调度[J]. 计算机集成制造系统, 2020, 26(第1): 66-73.
[7]	张硕,钱晓明,楼佩煌,武星,孙超. 基于改进粒子群算法的大规模自动导引车系统路径规划优化[J]. 计算机集成制造系统, 2020, 26(9): 2484-2496.
[8]	吴蓓,丁文英,杜彦华,赵宁. 基于重力装载的自适应随机算法求解多箱型三维装箱问题[J]. 计算机集成制造系统, 2020, 26(11): 3084-3093.
[9]	苏珂,郑艺,朱运海,李杨,李邵鹏. 面向产品设计前期的集约化设计方法[J]. 计算机集成制造系统, 2020, 26(10): 2670-2677.
[10]	郭学鹏,朱永国,王发麟,宋利康,陈大伟. 基于个体扰动变异粒子群算法的线缆布线顺序规划方法[J]. 计算机集成制造系统, 2020, 26(10): 2753-2761.
[11]	张珊珊,李方义,贾秀杰,周丽蓉,刘浩华,张传伟,孔琳. 面向变速箱磨损状态评估的灰靶模型优化[J]. 计算机集成制造系统, 2019, 25(第9): 2159-2166.
[12]	李国超,周宏根,景旭文,田桂中,李磊. 基于小生境粒子群算法的刀具容屑槽刃磨工艺设计[J]. 计算机集成制造系统, 2019, 25(第7): 1746-1756.
[13]	李帅,张智聪,胡开顺,晏晓辉,张良伟,赵少勇,钟守炎,徐劲力. 面向突发事件的分布式制造资源协同调度[J]. 计算机集成制造系统, 2019, 25(第3): 654-660.
[14]	李聪波,杨青山,陈文倩,胡芮. 面向响应性能的集成式电子液压制动系统执行器参数优化[J]. 计算机集成制造系统, 2019, 25(第11): 2710-2719.
[15]	王京涛,陆金桂,王邦祥,赵东波. 食物链传导响应算法在齿轮箱优化中的应用[J]. 计算机集成制造系统, 2019, 25(第1): 197-207.