改进的粒子群算法求解置换流水车间调度问题

doi:10.3724/SP.J.1087.2012.01022

计算机应用 ›› 2012, Vol. 32 ›› Issue (04): 1022-1024.DOI: 10.3724/SP.J.1087.2012.01022

改进的粒子群算法求解置换流水车间调度问题

张其亮¹,²,陈永生²,韩斌¹

1. 江苏科技大学电气与信息工程学院,江苏张家港 215600
2. 同济大学电子与信息工程学院,上海 200331

收稿日期:2011-10-13 修回日期:2011-12-05 发布日期:2012-04-20 出版日期:2012-04-01
通讯作者: 张其亮
作者简介:张其亮(1979-)，男，山东潍坊人，讲师，博士研究生，主要研究方向：智能算法优化；陈永生(1966-)，男，江苏镇江人，教授，博士，主要研究方向：智能算法优化、轨道交通；韩斌(1968-)，男，江苏南通人，教授，博士，主要研究方向：数字图像处理、算法优化。
基金资助:
国家“十一五”科技支撑项目

Improved particle swarm optimization for permutation flowshop scheduling problem

ZHANG Qi-liang¹,²,CHEN Yong-sheng²,HAN Bin¹

1. College of Electricity and Information Engineering, Jiangsu University of Science and Technology, Zhangjiagang Jiangsu 215600, China
2. College of Electronic and Information Engineering,Tongji University, Shanghai 200331,China

Received:2011-10-13 Revised:2011-12-05 Online:2012-04-20 Published:2012-04-01
Contact: ZHANG Qi-liang

摘要/Abstract

摘要： 针对置换流水车间调度问题，提出了一种改进的粒子群算法进行求解。改进算法引入了判断粒子群早熟的方法，并在发现粒子群早熟后采用逆转策略对种群最优粒子进行变异，利用模拟退火思想概率接收新的最优粒子。种群最优粒子的改变会引导粒子群跳出局部极值的约束，从而克服粒子群的早熟状态。通过对置换流水车间调度问题中Car系列和Rec系列部分基准数据的测试，证明了该算法的有效性。

关键词: 粒子群算法, 多样性, 局部收敛, 置换流水车间调度

Abstract: To solve permutation flowshop scheduling problem, an improved particle swarm optimization was proposed. Improved algorithm introduced a method to judge the premature state of the particle swarm, and used reversion strategy to mutate the best particle after the particle swarm being trapped in premature convergence, and used simulated annealing method to accept the new particle. The mutation for best particle can guide the particle swarm to escape from the local best values limit and overcome the particles premature stagnation. The simulation results based on Car and Rec benchmarks of permutation flowshop scheduling problem prove the effectiveness of the proposed algorithm.

Key words: Particle Swarm Optimization (PSO), diversity, local convergence, permutation flowshop scheduling

张其亮陈永生韩斌. 改进的粒子群算法求解置换流水车间调度问题[J]. 计算机应用, 2012, 32(04): 1022-1024.

ZHANG Qi-liang CHEN Yong-sheng HAN Bin. Improved particle swarm optimization for permutation flowshop scheduling problem[J]. Journal of Computer Applications, 2012, 32(04): 1022-1024.

参考文献

［1］ GAREY M R, JOHNSON D S, SETHI R. The complexity of flowshop and job shop cheduling［J］.Mathematics of Operations Research,1976,1(2):117-129. ［2］ EBERHART R C, KENNEDY J. A new optimizer using particle swarm theory［EB/OL］.[2011-05-01].http://webmining.spd.louisville.edu/Websites/COMB-OPT/FINAL-PAPERS/SwarmsPaper.pdf. ［3］高尚,杨静宇.求解流水作业调度问题的混合粒子群优化算法［C］// 2006中国控制与决策学术年会论文集. 沈阳:东北大学出版社,2006:1006-1008. ［4］田野,刘大有.求解流水车间调度问题的混合粒子群算法［J］.电子学报,2011,39(5):1087-1093. ［5］方伟,孙俊, 须文波.一种多样性控制的粒子群优化算法［J］.控制与决策,2008,23(8):863-868. ［6］刘志雄,严新平,赵润军.置换流水车间调度粒子群算法与参数设置分析［J］.武汉理工大学学报:交通科学与工程版,2010,34(6):1129-1132. ［7］ SUN KAI, YANG GEN-KE. An effective hybrid optimization algorithm for the flow shop scheduling problem［C］// Proceedings of the 2006 IEEE International Conference on Information Acquisition. [S.l.]:IEEE,2006:1234-1238. ［8］朱海梅, 吴永萍.一种高速收敛粒子群优化算法［J］.控制与决策,2010,25(1):20-24. ［9］ WANG LING, ZHENG DA-ZHONG. A modified evolutionary programming for flow shop scheduling［J］. International Journal of Advanced Manufacturing Technology,2003,22: 522-527. ［10］乔佩利,马丽丽,郑林.基于改进粒子群算法的车间作业调度问题研究［J］.哈尔滨理工大学学报,2011,16(2):35-39. ［11］ CARLIER J. Ordonnancements a contraintes disjonctives ［J］.Operations Research,1978,12:333-351. ［12］ REEVES C R. A genetic algorithms for flowshop sequencing［J］. Computers and Operation Research,1955,22(1):5-13.

[1]	毛铭泽, 曹芮浩, 闫春钢. 基于权值多样性的半监督分类算法[J]. 计算机应用, 2021, 41(9): 2473-2480.
[2]	朱亮, 徐华, 崔鑫. 基于基分类器系数和多样性的改进AdaBoost算法[J]. 计算机应用, 2021, 41(8): 2225-2231.
[3]	乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103.
[4]	李二超, 李康伟. 基于最小距离和聚合策略的分解多目标进化算法[J]. 计算机应用, 2021, 41(1): 22-28.
[5]	李二超, 杨蓉蓉. 基于自适应反向学习的多目标分布估计算法[J]. 计算机应用, 2021, 41(1): 15-21.
[6]	赵旭浩, 王轶群, 刘健, 徐春晖. 基于能量约束的自主水下航行器任务规划算法[J]. 计算机应用, 2019, 39(9): 2529-2534.
[7]	谭阳, 唐德权, 曹守富. 基于超球形模糊支配的高维多目标粒子群优化算法[J]. 计算机应用, 2019, 39(11): 3233-3241.
[8]	武旭晨, 朴春慧, 蒋学红. 基于GPU并行计算的电动出租车新建充电站选址模型[J]. 计算机应用, 2019, 39(10): 3071-3078.
[9]	袁小平, 蒋硕. 基于分层自主学习的改进粒子群优化算法[J]. 计算机应用, 2019, 39(1): 148-153.
[10]	王庆荣, 王瑞峰. 基于改进粒子群算法的配电网重构策略[J]. 计算机应用, 2018, 38(9): 2720-2724.
[11]	王永贵, 胡彩云, 李鑫. 基于局部远亲差分增强的扰动粒子群优化算法[J]. 计算机应用, 2018, 38(5): 1239-1244.
[12]	周海鹏, 高芹, 蒋丰千, 余大为, 乔焰, 李旸. 自适应混沌量子粒子群算法及其在WSN覆盖优化中的应用[J]. 计算机应用, 2018, 38(4): 1064-1071.
[13]	王玲娣, 徐华. AdaBoost的多样性分析及改进[J]. 计算机应用, 2018, 38(3): 650-654.
[14]	黄亚坤, 王杨, 王明星. 综合社区与关联序列挖掘的电子政务推荐算法[J]. 计算机应用, 2017, 37(9): 2671-2677.
[15]	吕立国, 季伟东. 结合质心思想和柯西变异策略的粒子群优化算法[J]. 计算机应用, 2017, 37(5): 1369-1375.

改进的粒子群算法求解置换流水车间调度问题

Improved particle swarm optimization for permutation flowshop scheduling problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics