求解柔性作业车间调度问题的新型改进Jaya算法

doi:10.3778/j.issn.1002-8331.2111-0189

摘要/Abstract

摘要： 为有效解决复杂的柔性作业车间调度问题，以最小化最大完成时间为目标，提出了一种结合了变邻域搜索算法的新型改进Jaya算法来求解。为不断挖掘和优化探索最优解，提高算法求解的结果质量，通过Jaya算法的原理重新提出一种解的更新机制，此外在Jaya算法原理的基础上嵌入一种变邻域搜索策略，并在传统邻域结构的基础上重新设计了两种新型邻域结构，扩大了邻域搜索范围，增强了Jaya算法的局部搜索能力，避免算法因失去解的多样性从而陷入局部最优。运用基准算例对该算法的求解性能进行了验证，并与其他算法的仿真结果进行对比，结果表明该改进算法的求解效率更高。

关键词: 柔性作业车间, 生产调度, Jaya算法, 变邻域搜索

Abstract: In order to effectively solve the complex flexible job shop scheduling problem(FJSP) with the objective of minimizing the maximum completion time, a new and improved Jaya algorithm incorporating a variable-neighborhood search algorithm（NIJA） is proposed to solve it. In order to continuously explore and optimize the optimal solution and improve the quality of the result of algorithm solution, a solution update mechanism is re-proposed through the principle of Jaya algorithm, and in addition, a variable neighborhood search strategy is embedded on the basis of the principle of Jaya algorithm, and two new neighborhood structures are redesigned on the basis of traditional neighborhood structure to expand the neighborhood search range and enhance the local search capability of Jaya algorithm. The algorithm avoids losing the diversity of solutions and thus falls into local optimum. The algorithm performance is verified using benchmark cases and compared with the simulation results of other algorithms in the literature, which show that the improved algorithm is more efficient.

Key words: flexible job shop（FJS）, production scheduling, Jaya algorithm, variable neighborhood search

裴小兵, 祁文博, 戴毓彤. 求解柔性作业车间调度问题的新型改进Jaya算法[J]. 计算机工程与应用, 2022, 58(19): 318-325.

PEI Xiaobing, QI Wenbo, DAI Yutong. New Improved Jaya Algorithm for Solving Flexible Job Shop Scheduling Problem[J]. Computer Engineering and Applications, 2022, 58(19): 318-325.

参考文献

[1] 顾幸生，丁豪杰.面向柔性作业车间调度问题的改进博弈粒子群算法[J].同济大学学报（自然科学版），2020，48（12）：1782-1789.
GU X S，DING H J.An improved gaming particle swarm optimization algorithm for flexible job-shop scheduling problems[J].Journal of Tongji University（Natural Science），2020，48（12）：1782-1789.
[2] 王家海，李营力，刘铮玮，等.柔性作业车间调度的精确邻域结构混合进化算法[J].同济大学学报（自然科学版），2021，49（3）：440-448.
WANG J H，LI Y L，LIU Z W，et al.Evolutionary algorithm with precise neighborhood structure for flexible workshop scheduling[J].Journal of Tongji University（Natural Science），2021，49（3）：440-448.
[3] LI X，GAO L.An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J].International Journal of Production Economics，2016，174：93-110.
[4] HAO Y F，JI C L，XIAO W.Research on NSGA-II flexible job shop scheduling based on variable length chromosomes[J].Journal of Physics（Conference Series），2021，1883（1）：012025.
[5] 姜天华.混合灰狼优化算法求解柔性作业车间调度问题[J].控制与决策，2018，33（3）：503-508.
JIANG T H.Flexible job shop scheduling problem with hybrid grey wolf optimization algorithm[J].Control and Decision，2018，33（3）：503-508.
[6] 田旻，刘人境.分层混合遗传算法求解柔性作业车间调度问题[J].工业工程与管理，2017，22（5）：32-39.
TIAN M，LIU R J.Solving flexible job-shop scheduling problem based on hierarchical hybrid genetic algorithm[J].Industrial Engineering and Management，2017，22（5）：32-39.
[7] NOURI H E，DRISS O B，GHéDIRA K.Solving the flexible job shop problem by hybrid metaheuristics-based multiagent model[J].Journal of Industrial Engineering International，2018，14：1-14
[8] SHEN L，DAUZèRE-PéRèS S，NEUFELD J S.Solving the flexible job shop scheduling problem with sequence-dependent setup times[J].European Journal of Operational Research，2018，265（2）：503-516.
[9] RAO V R.Jaya：A simple and new optimization algorithm for solving constrained and unconstrained optimization problems[J].International Journal of Industrial Engineering Computations，2016，7（1）：19-34.
[10] GAO K，SADOLLAH A，ZHANG Y，et al.Discrete Jaya algorithm for flexible job shop scheduling problem with new job insertion[C]//Proceedings of 2016 14th International Conference on Control，Automation，Robotics and Vision，2016：13-15.
[11] CALDEIRA R H，GNANAVELBABU A.Solving the flexible job shop scheduling problem using an improved Jaya algorithm[J].Computers & Industrial Engineering，2019，137.
[12] 栾飞，吴书强，李富康，等.一种求解柔性作业车间调度问题的鲸鱼群优化算法[J].机械科学与技术，2020，39（2）：241-246.
LUAN F，WU S Q，LI F K，et al.A whale swarm optimization algorithm for solving flexible job shop scheduling problem[J].Mechanical Science and Technology for Aerospace Engineering，2020，39（2）：241-246.
[13] 王建华，潘宇杰，孙瑞.自适应Jaya算法求解多目标柔性车间绿色调度问题[J].控制与决策，2021（7）：1714-1722.
WANG J H，PAN Y J，SUN R.Multi-objective flexible job shop green scheduling problem with self-adaptive Jaya algorithm[J].Control and Decision，2021（7）：1714-1722.
[14] 张国辉，高亮，李培根，等.改进遗传算法求解柔性作业车间调度问题[J].机械工程学报，2009，45（7）：145-151.
ZHANG G H，GAO L，LL P G，et al.Improved genetic algorithm for the flexible job-shop scheduling problem[J].Journal of Mechanical Engineering，2009，45（7）：145-151.
[15] DE SIQUEIRA E C，SOUZA M J F，DE SOUZA S R.An MO-GVNS algorithm for solving a multi-objective hybrid flow shop scheduling problem[J].International Transactions in Operational Research，2020，27：614-650.
[16] KACEM I，HAMMADI S，BORNE P.Approach by localization and multi-objective 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.
[17] GAO K Z，SUGANTHAN P N.Pareto-based grouping discrete harmony search algorithm for multi-objective flexible job shop scheduling[J].Information Sciences，2014，289：76-90.
[18] ZHANG G H，GAO L，SHI Y.An effective genetic algorithm for the flexible job-shop scheduling problem[J]. Expert Systems with Applications，2010，38（4）：3563-3573.
[19] ZHANG C，LI P，GUAN Z，et al. A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem[J].Computers & Operations Research，2007，34（11）：3229-3242.
[20] 崔琪，吴秀丽，余建军.变邻域改进遗传算法求解混合流水车间调度问题[J].计算机集成制造系统，2017，23（9）：1917-1927.
CUI Q，WU X L，YU J J.Improved genetic algorithm variable neighborhood search for solving hybrid flow shop scheduling problem[J]. Computer Integrated Manufacturing Systems，2017，23（9）：1917-1927.
[21] RANJBAR M，KAZEMI A.A generalized variable neighborhood search algorithm for the talent scheduling problem[J].Computers & Industrial Engineering，2018，126：673-680.
[22] ABDERRAHIM M，BEKRAR A，TRENTESAUX D，et al.Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints[J]. Optimization Letters，2022，16（1）：255-280.
[23] 吴树景，游有鹏，罗福源.变邻域保优遗传算法求解柔性车间调度问题[J].计算机工程与应用，2020，56（22）：236-243.
WU S J，YOU Y P，LUO F Y.Genetic-variable neighborhood search algorithm with elite protection strategy for flexible job shop scheduling problem[J].Computer Engineering and Applications，2020，56（22）：236-243.
[24] KACEM I，HAMMADI S，BORNE P.Pareto-optimality approach for flexible job-shop scheduling problems：Hybridization of evolutionary algorithms and fuzzy logic[J].Mathematics and Computers in Simulation，2002，60（3/5）：245-276.
[25] BRANDIMARTE P.Routing and scheduling in a flexible job shop by tabu search[J].Annals of Operations Research，1993，41（3）：157-183.
[26] 刘巍巍，马雪丽，刘晓冰.面向柔性作业车间调度问题的改进变邻域搜索算法[J].计算机应用与软件，2015，32（4）：234-238.
LIU W W，MA X L，LIU X B.Improved variable neighbourhood search algorithm for flexible job shop scheduling problem[J].Computer Applications and Software，2015，32（4）：234-238.
[27] YANG Y.A modified biogeography-based optimization for the flexible job shop scheduling problem[J].Mathematical Problems in Engineering，2015，22：1-10.
[28] LEI W，CAO J C，MING L，et al.Flexible job shop scheduling problem using an improved ant colony optimization[J].Scientific Programming，2017，2017：1-11.
[29] HAMID K，SEYED H R，ZANDIEH M.An efficient knowledge-based algorithm for the flexible job shop scheduling problem[J].Knowledge-Based Systems，2012，36：236-244.
[30] GAO K Z，SUGANTHAN P N，CHUA T J，et al.A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion[J].Expert Systems with Applications，2015，42：7652-7663.
[31] LI J Q，PAN Q K，LIANG Y C.An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems[J].Computers & Industrial Engineering，2010，59（4）：647-662.