改进离散粒子群算法求解柔性流水车间调度问题

doi:10.11772/j.issn.1001-9081.2015.05.1342

计算机应用 ›› 2015, Vol. 35 ›› Issue (5): 1342-1347.DOI: 10.11772/j.issn.1001-9081.2015.05.1342

改进离散粒子群算法求解柔性流水车间调度问题

徐华, 张庭

江南大学物联网工程学院, 江苏无锡 214122

收稿日期:2014-12-11 修回日期:2015-01-22 出版日期:2015-05-10 发布日期:2015-05-14
通讯作者: 徐华
作者简介:徐华(1978-),女,江苏无锡人,副教授,博士,CCF会员,主要研究方向:人工神经网络、模糊系统; 张庭(1991-),男,江苏宿迁人,硕士研究生,主要研究方向:人工神经网络、粒子群算法、车间调度.
基金资助:
国家留学基金委资助项目(201308320030); 江苏省自然科学基金资助项目(BK20140165).

Improved discrete particle swarm algorithm for solving flexible flow shop scheduling problem

XU Hua, ZHANG Ting

School of Internet of Things Engineering, Jiangnan University, Wuxi Jiangsu 214122, China

Received:2014-12-11 Revised:2015-01-22 Online:2015-05-10 Published:2015-05-14

摘要/Abstract

摘要：

针对以最小化完工时间为目标的柔性流水车间调度问题(FFSP),提出了一种改进离散粒子群(DPSO)算法.所提算法重新定义粒子速度和位置的相关算子,并引入编码矩阵和解码矩阵来表示工件、机器以及调度之间的关系.为了提高柔性流水车间调度问题求解的改进离散粒子群算法的初始群体质量,通过分析初始机器选择与调度总完工时间的关系,首次提出一种基于NEH算法的最短用时分解策略算法.仿真实验结果表明,该算法在求解柔性流水车间调度问题上有很好的性能,是一种有效的调度算法.

关键词: 柔性流水车间调度, 离散粒子群算法, 最短用时分解策略, 优化算法

Abstract:

An improved Discrete Particle Swarm Optimization (DPSO) algorithm was proposed for solving the Flexible Flow Shop scheduling Problem (FFSP) with makespan criterion. The proposed algorithm redefined the operator of particle's velocity and position, and the encoding matrix and decoding matrix were introduced to represent the relationship between job, machine and scheduling. To improve the quality of initial population of the improved DPSO algorithm for the FFSP solution, by analyzing the relationship between the initial machine selection and the total completion time, a shortest time decomposition strategy based on NEH algorithm was proposed. The experimental results show that the algorithm has good performance in solving the flexible flow shop scheduling problem, and it is an effective scheduling algorithm.

Key words: flexible flow shop scheduling, Discrete Particle Swarm Optimization (DPSO) algorithm, shortest time decomposition strategy, optimization algorithm

中图分类号:

TP301

徐华, 张庭. 改进离散粒子群算法求解柔性流水车间调度问题[J]. 计算机应用, 2015, 35(5): 1342-1347.

XU Hua, ZHANG Ting. Improved discrete particle swarm algorithm for solving flexible flow shop scheduling problem[J]. Journal of Computer Applications, 2015, 35(5): 1342-1347.

参考文献

[1] GUPTA J N D. Two-stage, hybrid flow shop scheduling problem [J]. Operations Research, 1988, 39(4): 359-364.
[2] ROCK H. The three-machine no-wait flowshop problem is NP-complete[J]. Association for Computing Machinery, 1984, 31(2): 336-345.
[3] WANG K, SHAN M, HUANG M. Solution method of flowshop scheduling based on improved genetic algorithm[J]. Systems Engineering, 2008, 26(10): 116-118. (王克喜,单汨源,黄敏镁.基于改进遗传算法的流水车间调度求解方法[J].系统工程, 2008, 26(10): 116-118.)
[4] WANG J, ZHU H, ZHOU J. Optimal sub-population genetic algorithm for flexible flow shop scheduling problem [J]. Application Research of Computers, 2012, 29(2): 442-444. (王金鹏,朱洪俊,周俊.最优子种群遗传算法求解柔性流水车间调度问题[J].计算机应用研究, 2012, 29(2):442-444.)
[5] JOLAI F, SHEIKH S, RABBANI M, et al. A genetic algorithm for solving no-wait flexible flow lines with due window and job rejection [J]. International Journal of Advanced Manufacturing Technology, 2009, 42(5/6): 523-532.
[6] ZHANG Q, CHEN Y, HAN B. Improved particle swarm optimization for permutation flowshop scheduling problem [J]. Journal of Computers Applications, 2012, 32(4): 1022-1024. (张其亮,陈永生,韩斌.改进的粒子群算法求解置换流水车间调度问题[J].计算机应用, 2012, 32(4):1022-1024.)
[7] ZHANG Q, CHEN Y. Particle swarm optimization algorithm for flexible flow shop scheduling problem with mixed constraints [J]. Application Research of Computers, 2013, 30(11): 3253-3256.(张其亮,陈永生.解决具有混合约束柔性流水车间调度问题的粒子群优化算法[J].计算机应用研究,2013, 30(11):3253-3256.)
[8] XU A. Hybrid flow-shop scheduling based on immune clonal selection algorithm [J]. Computer Applications and Software, 2013, 20(3): 75-77. (许爱军.基于免疫克隆选择算法的混合流水车间调度方法[J].计算机应用与软件,2013, 30(3):75-77.)
[9] XUE H, WEI S, ZHANG P, et al. Flexible job-shop scheduling based on multiple ant colony algorithm[J]. Computer Engineering and Applications, 2013, 49(24): 243-248. (薛宏全,魏生民,张鹏,等.基于多种群蚁群算法的柔性作业车间调度研究[J].计算机工程与应用, 2013,49(24):243-248.)
[10] TANG J, ZHANG G, LIN B, et al. A hybrid algorithm for flexible job-shop scheduling problem[J]. Procedia Engineering, 2011, 15: 3678-3683.
[11] TEEKENG W, THAMMANO A. A combination of shuffled frog leaping and fuzzy logic for flexible job-shop scheduling problems[J]. Procedia Computer Science, 2011, 6: 69-75.
[12] ZHANG Q, CHEN Y. Hybrid PSO-NEH algorithm for solving no-wait flexible flow shop scheduling problem [J]. Systems Engineering - Theory and Practice, 2014, 34(3): 802-809. (张其亮,陈永生.基于混合粒子群-NEH算法求解无等待柔性流水车间调度问题[J].系统工程理论与实践,2014, 34(3):802-809.)
[13] NAWAZ M, ENSCORE E, HAM I. A heuristic algorithm for the m-machine, n-job flow shop [J]. Omega, 1983, 11(1): 91-95.
[14] KENNEDY J, EBERHART R. Particle swarm optimization[C]// Proceedings of the 1995 IEEE International Conference on Neural Networks. Piscataway: IEEE, 1995: 1942-1948.
[15] KENNEDY J, EBERHART R. A discrete binary version of the particle swarm algorithm[C]// Proceedings of the 1997 World Multi Conference on Systemics, Cybernetics and Informatics. Piscataway: IEEE, 1997: 4104-4109.
[16] SHAO X, LIU W, LIU Q, et al. Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem [J]. The International Journal of Advanced Manufacturing Technology, 2013, 67(9/10/11/12): 2885-2901.
[17] IMAN Z, GERARD L, ARINDAM G. A new technique for optimal allocation and sizing of capacitors and setting of LTC[J]. International Journal of Electrical Power and Energy Systems, 2013, 46: 250-257.
[18] WANG X, MU A, ZHU S. ISPO: A new way to solve traveling salesman problem[J]. Intelligent Control and Automation, 2013, 4(2): 122-125.
[19] AMIRA G, ABDESSLEM L, SALIM C. Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm[J]. International Journal of Bio-Inspired Computation, 2012, 4(4): 229-236.
[20] WANG W, YAO M, WU Y. Hybrid flow-shop scheduling approach based on genetic algorithm[J]. Journal of System Simulation, 2002, 14(7): 863-869. (王万良,姚明海,吴云高.基于遗传算法的混合Flow-shop调度方法[J].系统仿真学报,2002,14(7):863-869.)
[21] ZHOU H, TANG W, WEI Y. PSO-based optimization of flexible flow-shop scheduling[J]. China Mechanical Engineering, 2010, 21(9): 1053-1056. (周辉仁,唐万生,魏颖辉.基于微粒群算法的柔性流水车间调度优化[J].中国机械工程,2010, 21(9):1053-1056.)
[22] PENG J, LIU M, ZHANG M, et al. Cloud model evolutionary multi-objective flexible job-shop scheduling based on improved non-dominated sorting [J]. Journal of Mechanical Engineering, 2014, 50(12): 198-205. (彭建刚,刘明周,张铭鑫,等.基于改进非支配排序的云模型进化多目标柔性作业车间调度[J].机械工程学报, 2014,50(12):198-205.)
[23] YU Q, ZHAO L, PAN S. A scheduling optimization of flexible job-shop using genetic algorithm [J]. Modular Machine Tool and Automatic Manufacturing Technique, 2004(4): 34-36. (余琦玮,赵亮,潘双夏.基于遗传算法的柔性作业车间调度优化[J].组合机床与自动化加工技术,2004(4):34-36.)
[24] MIN D, DUNBING T, ADRIANA G, et al. Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm[J]. Robotics and Computer-Integrated Manufacturing, 2013, 29(5): 418-429.
[25] CUI J, LI T, ZHANG W. Hybrid flowshop scheduling model and its genetic algorithm[J]. Journal of University of Science and Technology Beijing, 2005, 27(5): 623-626. (崔建双,李铁克,张文新.混合流水车间调度模型及其遗传算法[J].北京科技大学学报,2005,7(5):623-626.)
[26] LUAN F, WANG W, FU W, et al. FJSP solving by improved GA based on PST hierarchy structure [J]. Computer Integrated Manufacturing Systems, 2014, 20(10): 2494-2501. (栾飞,王雯,傅卫平,等.基于PST层次结构的改进GA求解柔性车间调度问题[J].计算机集成制造系统,2014,20(10):2494-2501.)

改进离散粒子群算法求解柔性流水车间调度问题

Improved discrete particle swarm algorithm for solving flexible flow shop scheduling problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李开荣, 刘爽, 胡倩倩, 唐亦媛. 基于转角约束的改进蚁群优化算法路径规划[J]. 计算机应用, 2021, 41(9): 2560-2568.
[2]	陈俊, 何庆. 基于余弦相似度的改进蝴蝶优化算法[J]. 计算机应用, 2021, 41(9): 2668-2677.
[3]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[4]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[5]	汤安迪, 韩统, 徐登武, 谢磊. 基于混沌麻雀搜索算法的无人机航迹规划方法[J]. 计算机应用, 2021, 41(7): 2128-2136.
[6]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[7]	贾鹤鸣, 姜子超, 李瑶, 孙康健. 基于改进斑点鬣狗优化算法的同步优化特征选择[J]. 计算机应用, 2021, 41(5): 1290-1298.
[8]	许红亮, 杨桂芹, 蒋占军. 基于软件定义网络的数据中心自适应多路径负载均衡算法[J]. 计算机应用, 2021, 41(4): 1160-1164.
[9]	许飞雪, 刘勤明, 欧阳海玲, 叶春明. 基于性能合同的多部件系统维修策略模型优化[J]. 计算机应用, 2021, 41(4): 1184-1191.
[10]	冉家敏, 倪志伟, 彭鹏, 朱旭辉. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解[J]. 计算机应用, 2021, 41(3): 794-802.
[11]	樊小毛, 熊红林, 赵淦森. 带约束的清洁排班问题模型及其求解[J]. 计算机应用, 2021, 41(2): 577-582.
[12]	王泽昆, 贺毅朝, 李焕哲, 张发展. 基于新颖S型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题[J]. 计算机应用, 2021, 41(2): 461-469.
[13]	陆荣秀, 陈明明, 杨辉, 朱建勇. 基于溶液图像时序特征的元素组分含量动态监测系统[J]. 计算机应用, 2021, 41(10): 3075-3081.
[14]	董海, 吴瑶, 齐新娜. 基于改进鲸鱼优化算法的血液供应链网络多目标鲁棒优化设计[J]. 计算机应用, 2021, 41(10): 3063-3069.
[15]	汪虹余, 张彧, 杨恒, 穆楠. 基于蚁群优化算法的弱光图像显著性目标检测[J]. 计算机应用, 2021, 41(10): 2970-2978.