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

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]. 《计算机应用》唯一官方网站, 2024, 44(9): 2829-2837.
[2]	张俊娜, 王欣新, 李天泽, 赵晓焱, 袁培燕. 基于动态服务缓存辅助的任务卸载方法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1493-1500.
[3]	张卓, 陈花竹. 基于一致性和多样性的多尺度自表示学习的深度子空间聚类[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 353-359.
[4]	黄亚伟, 钱雪忠, 宋威. 基于双档案种群大小自适应方法的改进差分进化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3844-3853.
[5]	马勇健, 史旭华, 王佩瑶. 基于两阶段搜索与动态资源分配的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 269-277.
[6]	徐赛娟, 裴镇宇, 林佳炜, 刘耿耿. 基于多阶段搜索的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2345-2351.
[7]	杜明, 顾万里, 周军锋, 王志军. 基于motif连通性的社区搜索方法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2190-2199.
[8]	向峰, 李中志, 熊熙, 李斌勇. 粒子群局部优化的反距离权重插值算法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 385-390.
[9]	闫红超, 汤伟, 姚斌. 求解置换流水车间调度问题的混合鸟群算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2952-2959.
[10]	秦晓, 成苗, 张绍兵, 何莲, 石向文, 王品学, 曾尚. 工业场景下基于秩信息对YOLOv4的剪枝[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1417-1423.
[11]	毛铭泽, 曹芮浩, 闫春钢. 基于权值多样性的半监督分类算法[J]. 计算机应用, 2021, 41(9): 2473-2480.
[12]	朱亮, 徐华, 崔鑫. 基于基分类器系数和多样性的改进AdaBoost算法[J]. 计算机应用, 2021, 41(8): 2225-2231.
[13]	李二超, 毛玉燕. 基于空间收缩技术的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3419-3425.
[14]	乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103.
[15]	李二超, 李康伟. 基于最小距离和聚合策略的分解多目标进化算法[J]. 计算机应用, 2021, 41(1): 22-28.

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

Improved particle swarm optimization for permutation flowshop scheduling problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics