An improved ant colony optimization for solving the flexible job shop scheduling problem with multiple time constraints

Shaofeng Yan; Guohui Zhang; Jinghe Sun; Wenqiang Zhang; Shaofeng Yan; Guohui Zhang; Jinghe Sun; Wenqiang Zhang

doi:10.3934/mbe.2023325

Mathematical Biosciences and Engineering

2023, Volume 20, Issue 4: 7519-7547. doi: 10.3934/mbe.2023325

Previous Article Next Article

Research article Special Issues

An improved ant colony optimization for solving the flexible job shop scheduling problem with multiple time constraints

1.
College of Management Engineering, Zhengzhou University of Aeronautics, Zhengzhou 450046, China
2.
College of Economics and Management, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
3.
College of Information Science and Engineering, Henan University of Technology, Zhengzhou 450046, China

Received: 11 November 2022 Revised: 24 December 2022 Accepted: 05 February 2023 Published: 16 February 2023

The flexible job shop scheduling problem is important in many research fields such as production management and combinatorial optimization, and it contains sub-problems of machine assignment and operation sequencing. In this paper, we study a many-objective FJSP (MaOFJSP) with multiple time constraints on setup time, transportation time and delivery time, with the objective of minimizing the maximum completion time, the total workload, the workload of critical machine and penalties of earliness/tardiness. Based on the given problem, an improved ant colony optimization is proposed to solve the problem. A distributed coding approach is proposed by the problem features. Three initialization methods are proposed to improve the quality and diversity of the initial solutions. The front end of the algorithm is designed to iteratively update the machine assignment to search for different neighborhoods. Then the improved ant colony optimization is used for local search of the neighborhood. For the searched scheduling set the entropy weight method and non-dominated sorting are used for filtering. Then mutation and closeness operations are proposed to improve the diversity of the solutions. The algorithm was evaluated through experiments based on 28 benchmark instances. The experimental results show that the algorithm can effectively solve the MaOFJSP problem.
- many-objective flexible job-shop scheduling problem,
- improved ant colony optimization,
- setup time,
- transportation time,
- delivery time
Citation: Shaofeng Yan, Guohui Zhang, Jinghe Sun, Wenqiang Zhang. An improved ant colony optimization for solving the flexible job shop scheduling problem with multiple time constraints[J]. Mathematical Biosciences and Engineering, 2023, 20(4): 7519-7547. doi: 10.3934/mbe.2023325

Related Papers:

Abstract

The flexible job shop scheduling problem is important in many research fields such as production management and combinatorial optimization, and it contains sub-problems of machine assignment and operation sequencing. In this paper, we study a many-objective FJSP (MaOFJSP) with multiple time constraints on setup time, transportation time and delivery time, with the objective of minimizing the maximum completion time, the total workload, the workload of critical machine and penalties of earliness/tardiness. Based on the given problem, an improved ant colony optimization is proposed to solve the problem. A distributed coding approach is proposed by the problem features. Three initialization methods are proposed to improve the quality and diversity of the initial solutions. The front end of the algorithm is designed to iteratively update the machine assignment to search for different neighborhoods. Then the improved ant colony optimization is used for local search of the neighborhood. For the searched scheduling set the entropy weight method and non-dominated sorting are used for filtering. Then mutation and closeness operations are proposed to improve the diversity of the solutions. The algorithm was evaluated through experiments based on 28 benchmark instances. The experimental results show that the algorithm can effectively solve the MaOFJSP problem.

References

[1]	P. Brucker, R. Schlie, Job-shop scheduling with multi-purpose machines, Computing, 45 (1990), 369–375. https://doi.org/10.1007/BF02238804 doi: 10.1007/BF02238804
[2]	H. Zhang, G. Xu, R. Pan, H. Ge, A novel heuristic method for the energy-efficient flexible job-shop scheduling problem with sequence-dependent set-up and transportation time, Eng. Optim., 54 (2022), 1646–1667. https://doi.org/10.1080/0305215X.2021.1949007 doi: 10.1080/0305215X.2021.1949007
[3]	X. Shao, W. Liu, Q. Liu, C. Zhang, Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem, Int. J. Adv. Manuf. Technol., 67 (2013), 2885–2901. https://doi.org/10.1007/s00170-012-4701-3 doi: 10.1007/s00170-012-4701-3
[4]	G. Zhang, X. Shao, P. 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
[5]	F. M. Defersha, D. Obimuyiwa, A. D. Yimer, Mathematical model and simulated annealing algorithm for setup operator constrained flexible job shop scheduling problem, Comput. Ind. Eng., 171 (2022), 108487. https://doi.org/10.1016/j.cie.2022.108487 doi: 10.1016/j.cie.2022.108487
[6]	D. Kress, D. Müller, J. Nossack, A worker constrained flexible job shop scheduling problem with sequence-dependent setup times, OR Spectrum, 41 (2019), 179–217. https://doi.org/10.1007/s00291-018-0537-z doi: 10.1007/s00291-018-0537-z
[7]	M. Li, D. Lei, An imperialist competitive algorithm with feedback for energy-efficient flexible job shop scheduling with transportation and sequence-dependent setup times, Eng. Appl. Artif. Intell., 103 (2021), 104307. https://doi.org/10.1016/j.engappai.2021.104307 doi: 10.1016/j.engappai.2021.104307
[8]	Y. Wang, Q. Zhu, A hybrid genetic algorithm for flexible job shop scheduling problem with sequence-dependent setup times and job lag times, IEEE Access, 9 (2021), 104864–104873. https://doi.org/10.1109/ACCESS.2021.3096007 doi: 10.1109/ACCESS.2021.3096007
[9]	Y. Du, J. Li, C. Luo, L. Meng, A hybrid estimation of distribution algorithm for distributed flexible job shop scheduling with crane transportations, Swarm Evol. Comput., 62 (2021), 100861. https://doi.org/10.1016/j.swevo.2021.100861 doi: 10.1016/j.swevo.2021.100861
[10]	J. Q. Li, Y. Du, K. Z. Gao, P. Y. Duan, D. W. Gong, Q. K. Pan, et al., A hybrid iterated greedy algorithm for a crane transportation flexible job shop problem, IEEE Trans. Autom. Sci. Eng., 19 (2021), 2153–2170. https://doi.org/10.1109/TASE.2021.3062979 doi: 10.1109/TASE.2021.3062979
[11]	W. Ren, Y. Yan, Y. Hu, Y. Guan, Joint optimisation for dynamic flexible job-shop scheduling problem with transportation time and resource constraints, Int. J. Prod. Res., 60 (2022), 5675–5696. https://doi.org/10.1080/00207543.2021.1968526 doi: 10.1080/00207543.2021.1968526
[12]	J. Yan, Z. Liu, C. Zhang, T. Zhang, Y. Zhang, C. Yang, Research on flexible job shop scheduling under finite transportation conditions for digital twin workshop, Rob. Comput. Integr. Manuf., 72 (2021), 102198. https://doi.org/10.1016/j.rcim.2021.102198 doi: 10.1016/j.rcim.2021.102198
[13]	J. Li, J. Deng, C. Li, Y. Han, J. Tian, B. Zhang, et al., An improved Jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times, Knowl.-Based Syst., 200 (2020), 106032. https://doi.org/10.1016/j.knosys.2020.106032 doi: 10.1016/j.knosys.2020.106032
[14]	X. Wu, X. Liu, N. Zhao, An improved differential evolution algorithm for solving a distributed assembly flexible job shop scheduling problem, Memet. Comput., 11 (2019), 335–355. https://doi.org/10.1007/s12293-018-00278-7 doi: 10.1007/s12293-018-00278-7
[15]	G. Zhang, Y. Hu, J. Sun, W. Zhang, An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints, Swarm Evol. Comput., 54 (2020), 100664. https://doi.org/10.1016/j.swevo.2020.100664 doi: 10.1016/j.swevo.2020.100664
[16]	K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ, IEEE Trans. Evol. Comput., 6 (2002), 182–197. https://doi.org/10.1109/4235.996017 doi: 10.1109/4235.996017
[17]	R. Chen, B. Yang, S. Li, S. Wang, A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem, Comput. Ind. Eng., 149 (2020), 106778. https://doi.org/10.1016/j.cie.2020.106778 doi: 10.1016/j.cie.2020.106778
[18]	X. 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
[19]	G. 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
[20]	L. Wang, J. Cai, M. Li, Z. Liu, Flexible job shop scheduling problem using an improved ant colony optimization, Sci. Program., 2017 (2017), 9016303. https://doi.org/10.1155/2017/9016303 doi: 10.1155/2017/9016303
[21]	H. Ding, X. Gu, Improved particle swarm optimization algorithm based novel encoding and decoding schemes for flexible job shop scheduling problem, Comput. Oper. Res., 121 (2020), 104951. https://doi.org/10.1016/j.cor.2020.104951 doi: 10.1016/j.cor.2020.104951
[22]	F. M. Defersha, D. Obimuyiwa, A. D. Yimer, Mathematical model and simulated annealing algorithm for setup operator constrained flexible job shop scheduling problem, Comput. Ind. Eng., 171 (2022), 108487. https://doi.org/10.1016/j.cie.2022.108487 doi: 10.1016/j.cie.2022.108487
[23]	G. Zhang, X. Lu, X. Liu, L. Zhang, S. Wei, W. Zhang, An effective two-stage algorithm based on convolutional neural network for the bi-objective flexible job shop scheduling problem with machine breakdown, Expert Syst. Appl., 203 (2022), 117460. https://doi.org/10.1016/j.eswa.2022.117460 doi: 10.1016/j.eswa.2022.117460
[24]	T. Jiang, H. Zhu, G. Deng, Improved African buffalo optimization algorithm for the green flexible job shop scheduling problem considering energy consumption, J. Intell. Fuzzy Syst., 38 (2020), 4573–4589. https://doi.org/10.3233/JIFS-191370 doi: 10.3233/JIFS-191370
[25]	H. Zhu, T. Jiang, Y. Wang, Discrete african buffalo optimization algorithm for the low-carbon flexible job shop scheduling problem, J. Adv. Manuf. Syst., 19 (2020), 837–854. https://doi.org/10.1142/S0219686720500390 doi: 10.1142/S0219686720500390
[26]	T. Jiang, C. Zhang, Q. M. Sun, Green job shop scheduling problem with discrete whale optimization algorithm, IEEE Access, 7 (2019), 43153–43166. https://doi.org/10.1109/ACCESS.2019.2908200 doi: 10.1109/ACCESS.2019.2908200
[27]	T. Jiang, C. Zhang, H. Zhu, J. Gu, G. Deng, et al., Energy-efficient scheduling for a job shop using an improved whale optimization algorithm, Mathematics, 6 (2018), 220. https://doi.org/10.3390/math6110220 doi: 10.3390/math6110220
[28]	P. Brandimarte, Routing and scheduling in a flexible job shop by tabu search, Ann. Oper. Res., 41 (1993), 157–183. https://doi.org/10.1007/BF02023073 doi: 10.1007/BF02023073
[29]	S. Dauzère-Pérès, J. Paulli, An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search, Ann. Oper. Res., 70 (1997), 281–306. https://doi.org/10.1023/A:1018930406487 doi: 10.1023/A:1018930406487
[30]	E. Zitzler, L. Thiele, Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, IEEE Trans. Evol. Comput., 3 (1999), 257–271. https://doi.org/10.1109/4235.797969 doi: 10.1109/4235.797969
[31]	D. C. Montgomery, R. H. Myers, W. H. Carter Jr, G. G. Vining, The hierarchy principle in designed industrial experiments, Qual. Reliab. Eng. Int., 21 (2005), 197–201. https://doi.org/10.1002/qre.615 doi: 10.1002/qre.615
[32]	M. Yuan, Y. Li, L. Zhang, F. Pei, Research on intelligent workshop resource scheduling method based on improved NSGA-Ⅱ algorithm, Rob. Comput. Integr. Manuf., 71 (2021), 102141. https://doi.org/10.1016/j.rcim.2021.102141 doi: 10.1016/j.rcim.2021.102141

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)