求解流水车间调度问题的混合粒子群算法

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (9): 33-36.

求解流水车间调度问题的混合粒子群算法

齐学梅1，2，罗永龙1，2，赵诚1，2

1.安徽师范大学数学计算机科学学院，安徽　芜湖 241003
2.安徽师范大学网络与信息安全工程技术研究中心，安徽　芜湖 241003

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2012-03-21 发布日期:2012-04-11

Hybrid particle swarm optimization algorithm for flow shop scheduling problem

QI Xuemei1，2, LUO Yonglong1，2, ZHAO Cheng1，2

1.School of Mathematics and Computer Science, Anhui Normal University, Wuhu, Anhui 241003, China
2.Network and Information Security Engineering Research Center, Anhui Normal University, Wuhu, Anhui 241003, China

Received:1900-01-01 Revised:1900-01-01 Online:2012-03-21 Published:2012-04-11

摘要/Abstract

摘要： 针对最小化流水车间调度总完工时间问题，提出了一种混合的粒子群优化算法（Hybrid Particle Swarm Algorithm，HPSA），采用启发式算法产生初始种群，将粒子群算法、遗传操作以及局部搜索策略有效地结合在一起。用Taillard’s基准程序随机产生大量实例，实验结果显示：HPSA通过对种群选取方法的改进和搜索范围的扩大提高了解的质量，在性能上均优于目前较有效的启发式算法和混合的禁忌搜索算法，产生最好解的平均百分比偏差和标准偏差均显著下降，最优解所占比例大幅度提高。

关键词: 粒子群优化, 流水车间调度, 局部搜索, 总完工时间

Abstract: A Hybrid Particle Swarm optimization Algorithm（HPSA） is presented to solve the flow shop scheduling problem with total flowtime minimization. The initial particle swarms are generated by heuristics. It combines the particle swarm optimization algorithm, genetic operators and local search strategies together. Taillard’s benchmark program is used to generate a large number of random instances. The experimental results indicate that the quality of solutions is improved using HPSA through the improvement of the option mode of population and a bigger searching scope. The performance of the proposed method is superior to the efficient heuristics currently used and hybrid tabu search algorithms. The average relation percentage deviation and standard deviation are reduced evidently, and the percent of optimal solutions increases obviously.

Key words: particle swarm optimization, flow shop scheduling, local search, total flowtime

齐学梅1，2，罗永龙1，2，赵诚1，2. 求解流水车间调度问题的混合粒子群算法[J]. 计算机工程与应用, 2012, 48(9): 33-36.

QI Xuemei1，2, LUO Yonglong1，2, ZHAO Cheng1，2. Hybrid particle swarm optimization algorithm for flow shop scheduling problem[J]. Computer Engineering and Applications, 2012, 48(9): 33-36.

[1]	孙泽宇，徐琛，苏艳超，李传锋，聂雅琳. 雾计算中跨层感知分簇路由协议[J]. 计算机工程与应用, 2021, 57(9): 109-117.
[2]	胡晓敏，王明丰，张首荣，李敏. 用于文本聚类的新型差分进化粒子群算法[J]. 计算机工程与应用, 2021, 57(4): 61-67.
[3]	徐辰华，骆珠光，吴冠宏，刘斌. 基于正弦因子和量子局部搜索的灰狼优化算法[J]. 计算机工程与应用, 2021, 57(24): 83-89.
[4]	陈万芬，王宇嘉，林炜星. 异构集成代理辅助多目标粒子群优化算法[J]. 计算机工程与应用, 2021, 57(23): 71-80.
[5]	杜守信，毋涛. 双种群混合遗传算法的裁剪分床应用研究[J]. 计算机工程与应用, 2021, 57(22): 182-189.
[6]	郝翔，贺毅朝，朱晓斌，翟庆雷. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
[7]	李雷孝，邓丹，李杰，王永生. 基于粒子群优化的全比较计算数据分发策略[J]. 计算机工程与应用, 2021, 57(15): 109-117.
[8]	廖玮霖，程杉，尚冬冬，魏昭彬. 多策略融合的粒子群优化算法[J]. 计算机工程与应用, 2021, 57(1): 69-76.
[9]	陈秋菊，徐建国. 优化正交匹配追踪和短时谱估计用于声音识别[J]. 计算机工程与应用, 2020, 56(7): 162-169.
[10]	罗函明，罗天洪，吴晓东，陈科百. 求解混合流水车间调度问题的离散布谷鸟算法[J]. 计算机工程与应用, 2020, 56(22): 264-271.
[11]	张水平，李殷俊，高栋，梁文. 带有动态爆炸半径的增强型烟花算法[J]. 计算机工程与应用, 2020, 56(18): 50-57.
[12]	黄建琼，郭文龙. 混合粒子群和改进细菌觅食的不平衡数据分类[J]. 计算机工程与应用, 2020, 56(10): 171-178.
[13]	尹建津1，张贝克1，高东1，许欣2. 改进蝙蝠算法解决FFSP问题及其应用研究[J]. 计算机工程与应用, 2019, 55(9): 243-247.
[14]	闫苗苗，刘三阳. 多班级交互式教学优化算法[J]. 计算机工程与应用, 2019, 55(9): 10-16.
[15]	张鑫1，邹德旋1，肖鹏1，喻秋2. 自适应简化粒子群优化算法及其应用[J]. 计算机工程与应用, 2019, 55(8): 250-263.