求解零空闲置换流水车间调度问题的离散烟花算法

刘翱, 冯骁毅, 邓旭东, 任亮, 刘波

系统工程理论与实践 ›› 2018, Vol. 38 ›› Issue (11) : 2874-2884.

PDF(798 KB)
中国科学院数学与系统科学研究院期刊网
PDF(798 KB)
系统工程理论与实践 ›› 2018, Vol. 38 ›› Issue (11) : 2874-2884. DOI: 10.12011/1000-6788(2018)11-2874-11
论文

求解零空闲置换流水车间调度问题的离散烟花算法

    刘翱1,2,3, 冯骁毅4, 邓旭东1,2, 任亮1,2, 刘波4
作者信息 +

A discrete fireworks algorithm for solving no-idle permutation flow shop problem

    LIU Ao1,2,3, FENG Xiaoyi4, DENG Xudong1,2, REN Liang1,2, LIU Bo4
Author information +
文章历史 +

摘要

针对以最小化最大完工时间为目标的零空闲置换流水线调度问题，提出了一种带有局部搜索的离散烟花算法.首先，结合调度问题的置换特征，定义了基于工件序列的编码方式；其次，结合反转和交换等操作重新定义了爆炸算子和变异算子；再次，开发了基于插入邻域的局部搜索策略，以增强烟花算法的局部搜索能力；最后，采用实验设计探讨了关键参数对算法性能的影响.基于Taillard基准问题的对比分析结果表明：所提方法在寻优精度、稳定性等指标上优于标准烟花算法、离散萤火虫算法、离散蛙跳算法、离散粒子群算法和遗传算法，且不劣于结合变邻域搜索的粒子群优化、混合离散粒子群优化、杂草优化等算法.

Abstract

In this paper, a discrete fireworks algorithm enhanced with local search is proposed to solve the no-idle permutation flow shop scheduling problem with respect to makespan minimization. Firstly, according to the characteristic of permutation, a job sequence-based encoding scheme is employed; secondly, a novel discrete fireworks algorithm is developed by redefining the explosion and mutation operators; thirdly, to enhance the local search, an insertion based local search is incorporated into the discrete fireworks algorithm; furthermore, the effects of key parameters on searching performance are investigated. Numerical results on the Taillard benchmark instances demonstrate that the proposed algorithm is superior to the standard fireworks algorithm, discrete firefly algorithm, discrete shuffled frog leaping algorithm, discrete particle swarm optimization and genetic algorithm in terms of solution accuracy and stability; meanwhile, the proposed algorithm also achieves competitive performance against particle swarm optimization with variable neighbour search, hybrid discrete particle swarm optimization and invasive weed optimization algorithm.

关键词

调度问题 / 流水车间 / 零空闲 / 离散烟花算法

Key words

scheduling problem / flow shop / no-idle / discrete fireworks algorithm

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用
刘翱 , 冯骁毅 , 邓旭东 , 任亮 , 刘波. 求解零空闲置换流水车间调度问题的离散烟花算法. 系统工程理论与实践, 2018, 38(11): 2874-2884 https://doi.org/10.12011/1000-6788(2018)11-2874-11
LIU Ao , FENG Xiaoyi , DENG Xudong , REN Liang , LIU Bo. A discrete fireworks algorithm for solving no-idle permutation flow shop problem. Systems Engineering - Theory & Practice, 2018, 38(11): 2874-2884 https://doi.org/10.12011/1000-6788(2018)11-2874-11
中图分类号： E917    TP2   

参考文献

[1] Pinedo M, Hadavi K. Scheduling:Theory, algorithms, and systems[M]. New York:Springer, 2012.
[2] Wang S, Wang L. A knowledge-based multi-agent evolutionary algorithm for semiconductor final testing scheduling problem[J]. Knowledge-based Systems, 2015(84):1-9.
[3] 王凌, 刘波. 微粒群优化与调度算法[M]. 北京:清华大学出版社, 2008.Wang L, Liu B. Particle swarm optimization and scheduling algorithms[M]. Beijing:Tsinghua University Press, 2008.
[4] Baptiste P, Lee K H. A branch and bound algorithm for the F/no-idle/Cmax[C]//Proceedings of International Conference on Industrial Engineering and Production Management, Berlin:Springer, 1997:429-438.
[5] Bagga P C. Minimizing total elapsed time subject to zero total idle time of machines in n×3 flowshop problem[J]. Indian Journal of Pure and Applied Mathematics, 2003, 34(2):219-228.
[6] Saadani N E H, Guinet A, Moalla M. A travelling salesman approach to solve the F/no-idle/Cmax problem[J]. European Journal of Operational Research, 2005, 161(1):11-20.
[7] Kalczynski P J, Kamburowski J. A heuristic for minimizing the makespan in no-idle permutation flow shops[J]. Computers & Industrial Engineering, 2005, 49(1):146-154.
[8] Baraz D, Mosheiov G. A note on a greedy heuristic for flow-shop makespan minimization with no machine idle-time[J]. European Journal of Operational Research, 2008, 184(2):810-813.
[9] Tasgetiren M F, Pan Q K, Wang L, et al. A DE based variable iterated greedy algorithm for the no-idle permutation flowshop scheduling problem with total flowtime criterion[C]//International Conference on Advanced Intelligent Computing Theories and Applications, Berlin:Springer, 2011:83-90.
[10] Tasgetiren M F, Buyukdagli O, Pan Q K, et al. A general variable neighborhood search algorithm for the no-idle permutation flowshop scheduling problem[C]//International Conference on Swarm, Evolutionary, and Memetic Computing, Berlin:Springer, 2013:24-34.
[11] Tasgetiren M F, Pan Q K, Suganthan P N, et al. A differential evolution algorithm for the no-idle flowshop scheduling problem with total tardiness criterion[J]. International Journal of Production Research, 2011, 49(16):5033-5050.
[12] Deng G, Gu X. A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion[J]. Computers & Operations Research, 2012, 39(9):2152-2160.
[13] Tasgetiren M F, Pan Q K, Suganthan P N, et al. A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion[J]. Applied Mathematical Modelling, 2013, 37(10):6758-6779.
[14] 刘长平, 叶春明. 求解零空闲置换流水车间调度问题的离散萤火虫算法[J]. 系统管理学报, 2014(5):723-727.Liu C P, Ye C M. A discrete firefly algorithm for minimizing the makespan in the no-idle permutation flow shops[J]. Journal of Systems & Management, 2014(5):723-727.
[15] 王亚敏, 冀俊忠.基于离散蛙跳算法的零空闲流水线调度问题求解[J].北京工业大学学报, 2010, 36(1):124-130.Wang Y M, Ji J Z. An algorithm based on discrete shuffled frog leaping for no-idle permutation flow shop scheduling problem[J]. Journal of Beijing University of Technology, 2010, 36(1):124-130.
[16] 潘全科, 王凌, 赵保华. 解决零空闲流水线调度问题的离散粒子群算法[J]. 控制与决策, 2008, 23(2):191-194.Pan Q K, Wang L, Zhao B H. Discrete particle swarm optimization for no-idle flow shop problem[J]. Control and Decision, 2008, 23(2):191-194.
[17] Pan Q K, Wang L. No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm[J]. International Journal of Advanced Manufacturing Technology, 2008, 39(7):796-807.
[18] Zhou Y, Chen H, Zhou G. Invasive weed optimization algorithm for optimization no-idle flow shop scheduling problem[J]. Neurocomputing, 2014, 137(5):285-292.
[19] 武磊, 潘全科, 桑红燕, 等. 求解零空闲流水线调度问题的和声搜索算法[J]. 计算机集成制造系统, 2009, 15(10):1960-1967.Wu L, Pan Q K, Sang H Y, et al. Harmony search algorithms for no-idle flow shop scheduling problems[J]. Computer Integrated Manufacturing Systems, 2009, 15(10):1960-1967.
[20] Tan Y, Zhu Y. Fireworks algorithm for optimization[C]//International Conference on Advances in Swarm Intelligence, Berlin:Springer, 2010:355-364.
[21] Zheng Y J, Song Q, Chen S Y. Multiobjective fireworks optimization for variable-rate fertilization in oil crop production[J]. Applied Soft Computing, 2013, 13(11):4253-4263.
[22] Imran A M, Kowsalya M. A new power system reconfiguration scheme for power loss minimization and voltage profile enhancement using fireworks algorithm[J]. International Journal of Electrical Power & Energy Systems, 2014, 62(2):312-322.
[23] Pholdee N, Bureerat S. Comparative performance of meta-heuristic algorithms for mass minimization of trusses with dynamic constraints[J]. Advances in Engineering Software, 2014, 75(3):1-13.
[24] Tan Y. Fireworks algorithms:Discrete firework algorithm for combinatorial optimization problem[M]. Berlin:Springer, 2015:209-226.
[25] Liu Z, Feng Z, Ke L. Fireworks algorithm for the multi-satellite control resource scheduling problem[C]//2015 IEEE Congress on Evolutionary Computation, Sendai:IEEE, 2015:1280-1286.
[26] 黄伟建, 郭芳. 基于烟花算法的云计算多目标任务调度[J]. 计算机应用研究, 2017, 34(6):1718-1720.Huang W J, Guo F. Multi-objective task scheduling based on fireworks algorithm in cloud computing[J]. Application Research of Computers, 2017, 34(6):1718-1720.
[27] 张以文, 吴金涛, 赵姝, 等. 基于改进烟花算法的Web服务组合优化[J]. 计算机集成制造系统, 2016, 22(2):422-432.Zhang Y W, Wu J T, Zhao S, et al. Optimization service composition based on improved firework algorithm[J]. Computer Integrated Manufacturing Systems, 2016, 22(2):422-432.
[28] 曹磊, 叶春明, 黄霞. 应用混沌烟花算法求解置换流水车间问题[J]. 计算机应用与软件, 2016, 33(11):188-192.Cao L, Ye C M, Huang X. Appling chaotic fireworks algorithm in solving permutation flow shop problem[J]. Computer Applications and Software, 2016, 33(11):188-192.
[29] 包晓晓, 叶春明, 黄霞. 烟花算法求解JSP问题的研究[J]. 计算机工程与应用, 2017, 53(3):247-252.Bao X X, Ye C M, Huang X. Solving job-shop scheduling problem by firework algorithm[J]. Computer Engineering and Application, 2017, 53(3):247-252.
[30] Liu B, Wang L, Jin Y H. An effective PSO-based memetic algorithm for flow shop scheduling[J]. IEEE Transactions on Systems, Man & Cybernetics-Part B:Cybernetics, 2007, 37(1):18-27.
[31] Ong Y S, Keane A J. Meta-Lamarckian learning in memetic algorithms[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(2):99-110.
[32] Taillard E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research, 1993, 64(2):278-285.
[33] 吴楚格, 王凌, 郑晓龙. 求解不相关并行机调度的一种自适应分布估计算法[J]. 控制与决策, 2016, 31(12):2177-2182.Wu C G, Wang L, Zheng X L. An adaptive estimation of distribution algorithm for solving the unrelated parallel machine scheduling[J]. Control and Decision, 2016, 31(12):2177-2182.
[34] Liang J J, Qin A K, Suganthan P N, et al. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(3):281-295.
[35] Shen J N, Wang L, Wang S Y. A bi-population EDA for solving the no-idle permutation flow-shop scheduling problem with the total tardiness criterion[J]. Knowledge-based Systems, 2015, 74:167-175.
[36] Yang P, Tang K, Lu X. Improving estimation of distribution algorithm on multimodal problems by detecting promising areas[J]. IEEE Transactions on Cybernetics, 2015, 45(8):1438-1449.
[37] Zhu Z, Xiao J, He S, et al. A multi-objective memetic algorithm based on locality-sensitive hashing for one-to-many-to-one dynamic pickup-and-delivery problem[J]. Information Sciences, 2015(329):73-89.
[38] 强永, 牟瑞芳. 考虑车辆限载的危险品运输车辆调度模型[J]. 系统工程理论与实践, 2017, 37(1):212-218.Qiang Y, Mou R F. Model of hazardous materials transportation scheduling with considering vehicle loading limit[J]. Systems Engineering-Theory & Practice, 2017, 37(1):212-218.
[39] 谢毅, 贺田塔, 倪倩芸,等. 面向能耗的云工作流调度优化[J]. 系统工程理论与实践, 2017, 37(4):1056-1071.Xie Y, He T T, Ni Q Y, et al. Scheduling for improving the energy efficiency of cloud workflow execution[J]. Systems Engineering-Theory & Practice, 2017, 37(4):1056-1071.
[40] Ding J Y, Song S J, Wu C. Carbon-efficient scheduling of flow shops by multi-objective optimization[J]. European Journal of Operational Research, 2016, 248(3):758-771.
[41] Yan C B, Zhao Q C. Analytical approach to estimate efficiency of series machines in production lines[J]. IEEE Transactions on Automation Science & Engineering, 2017, 99(8):1-14.
[42] 王东军, 刘翱, 刘克, 等. 基于优先规则的复杂并行机调度问题研究[J]. 系统工程理论与实践, 2016, 36(3):779-786.Wang D J, Liu A, Liu K, et al. Priority rule-based complex identical parallel machines scheduling[J]. Systems Engineering-Theory & Practice, 2016, 36(3):779-786.
[43] 陈通, 秦远辉, 万家宁, 等. 可重入柔性调度问题研究:模型、算法与应用[J]. 系统工程理论与实践, 2015, 35(5):1187-1201.Chen T, Qin Y H, Wan J N, et al. Re-entrant flexible scheduling:Models, algorithms and applications[J]. Systems Engineering-Theory & Practice, 2015, 35(5):1187-1201.
[44] Naderi B, Ruiz R. The distributed permutation flow shop scheduling problem[J]. Computers & Operations Research, 2010, 37(4):754-768.
[45] Hatami S, Ruiz R, Andres R C. The distributed assembly permutation flow shop scheduling problem[J]. International Journal of Production Research, 2013, 51(17):5292-5308.
[46] Deng J, Wang L, Wang S, et al. A competitive memetic algorithm for the distributed two-stage assembly flow-shop scheduling problem[J]. International Journal of Production Research, 2016, 54(12):1-17.
[47] 张洪涛, 崔珊珊, 刘广, 等. 机群保障资源配置建模与优化研究[J]. 系统工程理论与实践, 2015, 35(4):1019-1026.Zhang H T, Cui S S, Liu G, et al. Resource scheduling for air fleet operations[J]. Systems Engineering-Theory & Practice, 2015, 35(4):1019-1026.
[48] 刘翱, 刘克. 舰载机保障作业调度问题研究进展[J]. 系统工程理论与实践, 2017, 37(1):49-60.Liu A, Liu K. Advances in carrier-based aircraft deck operation scheduling[J]. Systems Engineering-Theory & Practice, 2017, 37(1):49-60.

基金

国家自然科学基金（71701156，71390331）；湖北省自然科学基金（2017CFB427）；教育部人文社会科学研究青年基金项目（16YJCZH056）；中国科学院前沿科学重点研究计划（QYZDB-SSW-SYS020）
PDF(798 KB)

Accesses

Citation

Detail
段落导航
相关文章

/

〈 〉