改进的离散型萤火虫优化算法求解柔性作业车间调度问题

计算机与现代化 ›› 2021, Vol. 0 ›› Issue (08): 11-15.

改进的离散型萤火虫优化算法求解柔性作业车间调度问题

(1.西华师范大学数学与信息学院，四川南充637009;2.西华师范大学计算方法与应用研究所，四川南充637009)

出版日期:2021-08-19 发布日期:2021-08-19
作者简介:郑捷(1996—),女,四川岳池人,硕士研究生,研究方向:智能算法,数学建模,E-mail: 2092885201@qq.com; 通信作者:潘大志(1974—),男,四川三台人,教授,博士,研究方向:智能计算,算法设计,E-mail: pdzzj@126.com。
基金资助:
国家自然科学基金资助项目(11871059); 四川省教育厅自然科学基金资助项目(18ZA0469); 西华师范大学英才科研基金资助项目(17YC385)

Improved Discrete Firefly Optimization Algorithm to Solve Flexible Job Shop Scheduling Problem

(1. School of Mathematics and Information, China West Normal University, Nanchong 637009, China;
2. Institute of Computing Method and Application Software， China West Normal University, Nanchong 637009, China)

Online:2021-08-19 Published:2021-08-19

摘要/Abstract

摘要： 针对传统的群智能优化算法在求解柔性作业车间调度问题(FJSP)时，存在寻优能力不足且易陷入局部最优等缺点，本文以最小化最大完工时间为目标，将萤火虫算法(FA)用于求解柔性作业车间调度问题，提出一种改进的离散型萤火虫算法(DFA)。首先，通过两段式编码建立FA连续优化问题与FJSP离散优化问题之间的联系；其次，设计一种群初始化方法，以确保初始解的质量以及多样性；然后，提出改进离散型萤火虫优化算法并引入局部搜索算法，加强算法的全局搜索能力和局部搜索能力；最后，对标准算例进行仿真，验证DFA算法求解FJSP的有效性。通过与遗传算法和粒子群优化算法进行仿真对比，表明了DFA求解FJSP的优越性。

关键词: 柔性作业车间调度问题, 最大完工时间, 离散型萤火虫算法, 两段式编码

Abstract: Aiming at the problem that when solving the flexible job shop scheduling problem (FJSP), the traditional swarm intelligence optimization algorithm has some disadvantages, such as insufficient optimization ability and easy to fall into local optimum, taking minimizing the maximum completion time as targets, firefly algorithm (FA) is applied to solve flexible job shop scheduling problem (FJSP), and an improved discrete firefly algorithm (DFA) is proposed. Firstly, the relationship between the FA continuous optimization problem and the FJSP discrete optimization problem is established through two-stage coding. Secondly, a population initialization method is designed to ensure the quality and diversity of initial solutions. Then, an improved discrete firefly optimization algorithm is proposed and a local search algorithm is introduced to enhance the global search ability and local search ability of the algorithm. Finally, the standard example is simulated and the validity of DFA algorithm for FJSP is verified. Through simulation comparison with genetic algorithm and particle swarm optimization algorithm, the superiority of DFA in solving FJSP is verified.

Key words: flexible job shop scheduling problem(FJSP), maximum completion time, discrete firefly algorithm, two-stage coding

郑捷, 潘大志, . 改进的离散型萤火虫优化算法求解柔性作业车间调度问题 [J]. 计算机与现代化, 2021, 0(08): 11-15.

ZHENG Jie , PAN Da-zhi , . Improved Discrete Firefly Optimization Algorithm to Solve Flexible Job Shop Scheduling Problem[J]. Computer and Modernization, 2021, 0(08): 11-15.

参考文献［23］

［1］	BRUCKER P, SCHLIE R. Job-shop scheduling with multi-purpose machines［J］. Computing, 1990,45(4):369-375.
［2］	VILCOT G, BILLAUT J C, ESSWEIN C. A tabu search algorithm for solving a bicriteria flexible job shop scheduling problem［J］. IFAC Proceedings Volumes, 2006,39(3):7-62.
［3］	FATTAHI P, MEHRABAD M S, JOLAI F. Mathematical modeling and heuristic approaches to flexible job shop scheduling problems［J］. Journal of Intelligent Manufacturing, 2007,18(3):331-342.
［4］	CHEN J C, CHEN K H, WU J J, et al. A study of the flexible job shop scheduling problem with parallel machines and reentrant process［J］. The International Journal of Advanced Manufacturing Technology, 2008,39(3-4):344-354.
［5］	XING L N, CHEN Y W, WANG P, et al. A knowledge-based ant colony optimization for flexible job shop scheduling problems［J］. Applied Soft Computing Journal, 2010,10(3):888-896.
［6］	MEKNI S, CHAAR B F, KSOURI M. TRIBES optimization algorithm applied to the flexible job shop scheduling problem［J］. IFAC Proceedings Volumes, 2010,43(4):344-349.
［7］	VAGHEFINEZHAD S, WONG K Y. A genetic algorithm approach for solving a flexible job shop scheduling problem［J］. International Journal of Computer Science Issues, 2012,9(3):85-90.
［8］	LI J Q, DENG J W, LI C Y, et al. An improved jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times［J］. Knowledge-Based Systems, 2020,200:106032.
［9］	张桐瑞,吴定会. 混合竞争群优化算法求解柔性车间调度问题［J/OL］. 控制工程:1-9［2020-11-23］. https://doi.org/10.14107/j.cnki.kzgc.20190657.
［10］	戴月明,王明慧,王春,等. 骨干双粒子群算法求解柔性作业车间调度问题［J］. 系统仿真学报, 2017,29(6):1268-1276.
［11］	姜天华. 混合灰狼优化算法求解柔性作业车间调度问题［J］. 控制与决策, 2018,33(3):503-508.
［12］	谢锐强,张惠珍. 求解柔性作业车间调度问题的两段式狼群算法［J/OL］. 计算机工程与应用:1-7［2020-11-23］. http://kns.cnki.net/kcms/detail/11.2127.TP.20200528.1423.010.html.
［13］	陶婷婷,宋豫川,王建成,等. 改进离散型飞蛾扑火优化算法求解柔性作业车间调度问题［J］. 机械工程师, 2020(11):25-29.
［14］	张捷,李彬,姜杰,等. 基于郊狼优化算法的柔性作业车间调度问题［J］. 现代制造工程, 2020(10):39-44.
［15］	WANG L, CAI J, LI M, et al. Flexible job shop scheduling problem using an improved ant colony optimization［J］. Scientific Programming, 2017(3):1-11.
［16］	LI J Q, PAN Q K, GAO K Z. Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems［J］. International Journal of Advanced Manufacturing Technology, 2011,55(9-12):1159-1169.
［17］	YANG X S. Firefly algorithm［M］// Nature-Inspired Metaheuristic Algorithms. Luniver Press, 2008:79-90.
［18］	CHENG R W, GEN M, TSUJIMURA Y. A tutorial survey of job-shop scheduling problems using genetic algorithms—I. representation［J］. Computers & Industrial Engineering, 1996,30(4):983-997.
［19］	连裕翔,张超勇,孟磊磊,等. 基于改进Jaya算法的柔性作业车间调度问题［J/OL］. 计算机集成制造系统:1-19［2020-12-02］. http://kns.cnki.net/kcms/detail/11.5946.tp.20201009.0942.004.html.
［20］	赵诗奎. 求解柔性作业车间调度问题的两级邻域搜索混合算法［J］. 机械工程学报, 2015,51(14):175-184.
［21］	罗函明,罗天洪,吴晓东,等. 求解混合流水车间调度问题的离散布谷鸟算法［J］. 计算机工程与应用, 2020,56(22):264-271.
［22］	高亮，张国辉，王晓娟. 柔性作业车间调度智能算法及其应用［M］. 华中科技大学出版社, 2012:12-13.
［23］	KACEM I, HAMMADI S, BORNE P. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems［J］. IEEE Transactions on Systems, Man, and Cybernetics Part C:Applications and Reviews, 2002,32(1):1-13.