An improved genetic algorithm with dynamic neighborhood search for job shop scheduling problem

Kongfu Hu; Lei Wang; Jingcao Cai; Long Cheng; Kongfu Hu; Lei Wang; Jingcao Cai; Long Cheng

doi:10.3934/mbe.2023774

Mathematical Biosciences and Engineering

2023, Volume 20, Issue 9: 17407-17427. doi: 10.3934/mbe.2023774

Previous Article Next Article

Research article

An improved genetic algorithm with dynamic neighborhood search for job shop scheduling problem

1.
School of Mechanical Engineering, Anhui Polytechnic University, Wuhu 241000, China
2.
AnHui Key Laboratory of Detection Technology and Energy Saving Devices, AnHui Polytechnic University, Wuhu 241000, China

Academic Editor: Yang Kuang

Received: 25 May 2023 Revised: 20 August 2023 Accepted: 22 August 2023 Published: 11 September 2023

The job shop scheduling problem (JSP) has consistently garnered significant attention. This paper introduces an improved genetic algorithm (IGA) with dynamic neighborhood search to tackle job shop scheduling problems with the objective of minimization the makespan. An inserted operation based on idle time is introduced during the decoding phase. An improved POX crossover operator is presented. A novel mutation operation is designed for searching neighborhood solutions. A new genetic recombination strategy based on a dynamic gene bank is provided. The elite retention strategy is presented. Several benchmarks are used to evaluate the algorithm's performance, and the computational results demonstrate that IGA delivers promising and competitive outcomes for the considered JSP.
- job shop scheduling problem,
- improved genetic algorithm,
- idle time,
- improved POX,
- neighborhood searching,
- dynamic gene bank,
- elite retention
Citation: Kongfu Hu, Lei Wang, Jingcao Cai, Long Cheng. An improved genetic algorithm with dynamic neighborhood search for job shop scheduling problem[J]. Mathematical Biosciences and Engineering, 2023, 20(9): 17407-17427. doi: 10.3934/mbe.2023774

Related Papers:

Abstract

The job shop scheduling problem (JSP) has consistently garnered significant attention. This paper introduces an improved genetic algorithm (IGA) with dynamic neighborhood search to tackle job shop scheduling problems with the objective of minimization the makespan. An inserted operation based on idle time is introduced during the decoding phase. An improved POX crossover operator is presented. A novel mutation operation is designed for searching neighborhood solutions. A new genetic recombination strategy based on a dynamic gene bank is provided. The elite retention strategy is presented. Several benchmarks are used to evaluate the algorithm's performance, and the computational results demonstrate that IGA delivers promising and competitive outcomes for the considered JSP.

References

[1]	X. Y. Li, L. Gao, An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem, Int. J. Prod. Econ., 174 (2016), 93–110. https://doi.org/10.1016/j.ijpe.2016.01.016 doi: 10.1016/j.ijpe.2016.01.016
[2]	X. Y. Li, L. Gao, Q. K. Pan, L. Wan, K. M. Chao, An effective hybrid genetic algorithm and variable neighborhood search for integrated process planning and scheduling in a packaging machine workshop, IEEE Trans. Syst. Man. Cybern. Syst., 49 (2018), 1933–1945. https://10.1109/TSMC.2018.2881686 doi: 10.1109/TSMC.2018.2881686
[3]	G. H. Zhang, L. Gao, Y. Shi, An effective genetic algorithm for the flexible job-shop scheduling problem, Expert Syst. Appl., 38 (2011), 3563–3573. https://doi.org/10.1016/j.eswa.2010.08.145 doi: 10.1016/j.eswa.2010.08.145
[4]	R. Mellado Silva, C. Cubillos, D. C. Paniagua, A constructive heuristic for solving the Job-Shop Scheduling Problem, IEEE Latin Am. Trans., 14 (2016), 2758–2763. https://10.1109/TLA.2016.7555250 doi: 10.1109/TLA.2016.7555250
[5]	G. Vilcot, J. C. Billaut, A tabu search algorithm for solving a multicriteria flexible job shop scheduling problem, Int. J. Prod. Res., 49 (2011), 6963–6980. https://doi.org/10.3182/20060517-3-FR-2903.00038 doi: 10.3182/20060517-3-FR-2903.00038
[6]	G. H. Zhang, X. Y. Shao, P. G. Li, L. Gao, An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem, Comput. Ind. Eng., 56 (2009), 1309–1318. https://doi.org/10.1016/j.cie.2008.07.021 doi: 10.1016/j.cie.2008.07.021
[7]	J. Zhang, J. Jie, W. L. Wang, X. Xu, A hybrid particle swarm optimisation for multi-objective flexible job-shop scheduling problem with dual-resources constrained, Int. J. Comput. Sci. Math., 8 (2018), 526. https://doi.org/10.1504/IJCSM.2017.088956 doi: 10.1504/IJCSM.2017.088956
[8]	L. N. Xing, Y. W. Chen, P. Wang, Q. S. Zhao, J. Xiong, A knowledge-based ant colony optimization for flexible job shop scheduling problems, Appl. Soft Comput., 10 (2010), 888–896. https://doi.org/10.1016/j.asoc.2009.10.006 doi: 10.1016/j.asoc.2009.10.006
[9]	J. Wu, G. D. Wu, J. J. Wang, Flexible job-shop scheduling problem based on hybrid ACO algorithm, Int. J. Simul. Model., 16 (2017), 497–505. https://10.2507/IJSIMM16(3)CO11 doi: 10.2507/IJSIMM16(3)CO11
[10]	J. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, MIT Press, 1992.
[11]	C. D. Liou, Y. C. Hsieh, Y. Y. Chen, A new encoding scheme-based hybrid algorithm for minimising two-machine flow-shop group scheduling problem, Int. J. Syst. Sci., 44 (2013), 77–93. https://doi.org/10.1080/00207721.2011.581396 doi: 10.1080/00207721.2011.581396
[12]	J. C. Tang, G. J. Zhang, B. B. Lin, B. X. Zhang, A hybrid algorithm for flexible job-shop scheduling problem with setup times, Int. J. Prod. Manage. Eng., 5 (2017), 23–30. https://doi.org/10.1016/j.proeng.2011.08.689 doi: 10.1016/j.proeng.2011.08.689
[13]	A. Turkyilmaz, S. Bulkan, A hybrid algorithm for total tardiness minimisation in flexible job shop: genetic algorithm with parallel VNS execution, Int. J. Prod. Res., 53 (2015), 1832–1848. https://doi.org/10.1080/00207543.2014.962113 doi: 10.1080/00207543.2014.962113
[14]	I. Ono, M. Yamamura, S. Kobayashi, A genetic algorithm for job-shop scheduling problems using job-based order crossover, in Proceedings of IEEE International Conference on Evolutionary Computation, (1996), 547–552.
[15]	Y. Victor, B. Larisa, T. Andrei, Hybrid flowshop with unrelated machines, sequence-dependent setup time, availability constraints and limited buffers, Comput. Ind. Eng., 56 (2019), 1452–1463. https://doi.org/10.1016/j.cie.2008.09.004 doi: 10.1016/j.cie.2008.09.004
[16]	H. C. Chang, T. K. Liu, Optimisation of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms, J. Intell. Manuf., 28 (2017), 1973–1986. https://doi.org/10.1007/s10845-015-1084-y doi: 10.1007/s10845-015-1084-y
[17]	H. Mokhtari, A. Hasani, An energy-efficient multi-objective optimization for flexible job-shop scheduling problem, Comput. Chem. Eng., 104 (2017), 339–352. https://doi.org/10.1016/j.compchemeng.2017.05.004 doi: 10.1016/j.compchemeng.2017.05.004
[18]	J. F. Goncalves, M. G. C. Resende, An extended Akers graphical method with a biased random-key genetic algorithm for job-shop scheduling, Int. Trans. Oper. Res., 27 (2014), 215–246. https://doi.org/10.1111/itor.12044 doi: 10.1111/itor.12044
[19]	C. Y. Zhang, P. G. Li, Z. L. Guan, Y. Q. Rao, A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem, Comput. Oper. Res., 34 (2007), 3229–3242. https://doi.org/10.1016/j.cor.2005.12.002 doi: 10.1016/j.cor.2005.12.002
[20]	W. Chen, H. Yang, Y. Hao, Scheduling of dynamic multi-objective flexible enterprise job-shop problem based on hybrid QPSO, IEEE Access, 7 (2019), 127090–127097. https://10.1109/ACCESS.2019.2938773 doi: 10.1109/ACCESS.2019.2938773
[21]	Y. C. Wang, J. M. Usher, Application of reinforcement learning for agent-based production scheduling, Eng. Appl. Artif. Intell., 18 (2005), 73–82. https://doi.org/10.1016/j.engappai.2004.08.018 doi: 10.1016/j.engappai.2004.08.018
[22]	P. M. Pardalos, O. V. Shylo, An algorithm for the job shop scheduling problem based on global equilibrium search techniques, Comput. Manag. Sci., 3 (2006), 331–348. https://doi.org/10.1007/s10287-006-0023-y doi: 10.1007/s10287-006-0023-y
[23]	M. M. Nasiri, F. Kianfar, A hybrid scatter search for the partial job shop scheduling problem, Int. J. Adv. Manuf. Technol., 52 (2011), 1031–1038. https://doi.org/10.1007/s00170-010-2792-2 doi: 10.1007/s00170-010-2792-2
[24]	G. L. Gong, Q. W. Deng, R. Chiong, X. Gong, H. Huang, An effective memetic algorithm for multi-objective job-shop scheduling, Knowl. Based Syst., 182 (2019), 104840. https://doi.org/10.1016/j.knosys.2019.07.011 doi: 10.1016/j.knosys.2019.07.011
[25]	F. Q. Zhao, J. L. Zhang, C. Zhang, J. Wang, An improved shuffled complex evolution algorithm with sequence mapping mechanism for job shop scheduling problems, Expert Syst. Appl., 42 (2015), 3953–3966. https://doi.org/10.1016/j.eswa.2015.01.007 doi: 10.1016/j.eswa.2015.01.007
[26]	N. Sharma, H. Sharma, A. Sharma, Beer froth artificial bee colony algorithm for job-shop scheduling problem, Appl. Soft Comput., 68 (2018), 507–524. https://doi.org/10.1016/j.asoc.2018.04.001 doi: 10.1016/j.asoc.2018.04.001
[27]	A. Leila, Z. Kamran, An agent-based parallel approach for the job shop scheduling problem with genetic algorithms, Math. Comput. Modell., 52 (2010), 1957–1965. https://doi.org/10.1016/j.mcm.2010.04.019 doi: 10.1016/j.mcm.2010.04.019
[28]	J. Xie, X. Y. Li, L. Gao, L. Gui, A hybrid algorithm with a new neighborhood structure for job shop scheduling problems, Comput. Ind. Eng., 169 (2022), 108205. https://doi.org/10.1016/j.cie.2022.108205 doi: 10.1016/j.cie.2022.108205

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)