Multi-flexible integrated scheduling algorithm for multi-flexible integrated scheduling problem with setup times

Dan Yang; Zhiqiang Xie; Chunting Zhang; Dan Yang; Zhiqiang Xie; Chunting Zhang

doi:10.3934/mbe.2023429

Mathematical Biosciences and Engineering

2023, Volume 20, Issue 6: 9781-9817. doi: 10.3934/mbe.2023429

Previous Article Next Article

Research article

Multi-flexible integrated scheduling algorithm for multi-flexible integrated scheduling problem with setup times

School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150000, China

Received: 29 December 2022 Revised: 27 February 2023 Accepted: 13 March 2023 Published: 24 March 2023

To address the multi-flexible integrated scheduling problem with setup times, a multi-flexible integrated scheduling algorithm is put forward. First, the operation optimization allocation strategy, based on the principle of the relatively long subsequent path, is proposed to assign the operations to idle machines. Second, the parallel optimization strategy is proposed to adjust the scheduling of the planned operations and machines to make the processing as parallel as possible and reduce the no-load machines. Then, the flexible operation determination strategy is combined with the above two strategies to determine the dynamic selection of the flexible operations as the planned operations. Finally, a potential operation preemptive strategy is proposed to judge whether the planned operations will be interrupted by other operations during their processing. The results show that the proposed algorithm can effectively solve the multi-flexible integrated scheduling with setup times, and it can also better solve the flexible integrated scheduling problem.
- multi-flexible integrated scheduling,
- flexible planning path,
- flexible sequential operations,
- flexible manufacturing,
- setup times
Citation: Dan Yang, Zhiqiang Xie, Chunting Zhang. Multi-flexible integrated scheduling algorithm for multi-flexible integrated scheduling problem with setup times[J]. Mathematical Biosciences and Engineering, 2023, 20(6): 9781-9817. doi: 10.3934/mbe.2023429

Related Papers:

Abstract

To address the multi-flexible integrated scheduling problem with setup times, a multi-flexible integrated scheduling algorithm is put forward. First, the operation optimization allocation strategy, based on the principle of the relatively long subsequent path, is proposed to assign the operations to idle machines. Second, the parallel optimization strategy is proposed to adjust the scheduling of the planned operations and machines to make the processing as parallel as possible and reduce the no-load machines. Then, the flexible operation determination strategy is combined with the above two strategies to determine the dynamic selection of the flexible operations as the planned operations. Finally, a potential operation preemptive strategy is proposed to judge whether the planned operations will be interrupted by other operations during their processing. The results show that the proposed algorithm can effectively solve the multi-flexible integrated scheduling with setup times, and it can also better solve the flexible integrated scheduling problem.

References

[1]	V. M. Valenzuela-Alcaraz, M. A. Cosio-Leon, A. D. Romero-Ocano, C. A. Brizuela, A cooperative coevolutionary algorithm approach to the no-wait job shop scheduling problem, Expert Syst. Appl., 194 (2022). https://doi.org/10.1016/j.eswa.2022.116498 doi: 10.1016/j.eswa.2022.116498
[2]	M. A. Salido, J. Escamilla, F. Barber, A. Giret, D. Tang, M. Dai, Energy efficiency, robustness, and makespan optimality in job-shop scheduling problems, AI EDAM, 30 (2016), 118–125. https://doi.org/10.1017/S0890060415000335 doi: 10.1017/S0890060415000335
[3]	M. Dai, Z. Zhang, A. Giret, M. A. Salido, An enhanced estimation of distribution algorithm for energy-efficient job-shop scheduling problems with transportation constraints, Sustainability, 11 (2019), 3085. https://doi.org/10.3390/su11113085 doi: 10.3390/su11113085
[4]	X. Hao, M. Gen, L. Lin, G. A. Suer, Effective multiobjective EDA for bi-criteria stochastic job-shop scheduling problem, J. Intell. Manuf., 28 (2017), 833–845. https://doi.org/10.1007/s10845-014-1026-0 doi: 10.1007/s10845-014-1026-0
[5]	Y. Wang, X. Wang, Inventory based two-objective job shop scheduling model and its hybrid genetic algorithm, Appl. Soft Comput., 13 (2013), 1400–1406. http://dx.doi.org/10.1016/j.asoc.2012.03.073 doi: 10.1016/j.asoc.2012.03.073
[6]	S. Nguyen, M. Zhang, M. Johnston, K. C. Tan, Automatic design of scheduling policies for dynamic multi-objective job shop scheduling via cooperative coevolution genetic programming, IEEE Trans. Evol. Comput., 18 (2013), 193–208. http://dx.doi.org/10.1109/TEVC.2013.2248159 doi: 10.1109/TEVC.2013.2248159
[7]	H. Wang, B. R. Sarker, J. Li, J. Li, Adaptive scheduling for assembly job shop with uncertain assembly times based on dual Q-learning, Int. J. Prod. Res., 59(2021), 5867–5883. https://doi.org/10.1080/00207543.2020.1794075 doi: 10.1080/00207543.2020.1794075
[8]	K. C. Ying, P. Pourhejazy, C. Y. Cheng, C. H. Wang, Cyber-physical assembly system-based optimization for robotic assembly sequence planning, J. Manuf. Syst., 58 (2021), 452–466. https://doi.org/10.1016/j.jmsy.2021.01.004 doi: 10.1016/j.jmsy.2021.01.004
[9]	A. De Giorgio, A. Maffei, M. Onori, L. Wang, Towards online reinforced learning of assembly sequence planning with interactive guidance systems for industry 4.0 adaptive manufacturing, J. Manuf. Syst., 60 (2021), 22–34. https://doi.org/10.1016/j.jmsy.2021.05.001 doi: 10.1016/j.jmsy.2021.05.001
[10]	A. Baykasoglu, F. S. Madenoglu, A. Hamzadayi, Greedy randomized adaptive search for dynamic flexible job-shop scheduling, J. Manuf. Syst., 56 (2020), 425–451. https://doi.org/10.1016/j.jmsy.2020.06.005 doi: 10.1016/j.jmsy.2020.06.005
[11]	A. Baykasoglu, F. S. Madenoglu, Greedy randomized adaptive search procedure for simultaneous scheduling of production and preventive maintenance activities in dynamic flexible job shops, Soft Comput., 25 (2021), 14893–14932. https://doi.org/10.1007/s00500-021-06053-0 doi: 10.1007/s00500-021-06053-0
[12]	A. Vital-Soto, A. Azab, M. F. Baki, Mathematical modeling and a hybridized bacterial foraging optimization algorithm for the flexible job-shop scheduling problem with sequencing flexibility, J. Manuf. Syst., 54(2020), 74–93. https://doi.org/10.1016/j.jmsy.2019.11.010 doi: 10.1016/j.jmsy.2019.11.010
[13]	G. Gong, R. Chiong, Q. Deng, X. Gong, A hybrid artificial bee colony algorithm for flexible job shop scheduling with worker flexibility, Int. J. Prod. Res., 58 (2020), 4406–4420. https://doi.org/10.1080/00207543.2019.1653504 doi: 10.1080/00207543.2019.1653504
[14]	R. Li, W. Gong, C. Lu, A reinforcement learning based RMOEA/D for bi-objective fuzzy flexible job shop scheduling, Expert Syst. Appl., 203 (2022), 117380. https://doi.org/10.1016/j.eswa.2022.117380 doi: 10.1016/j.eswa.2022.117380
[15]	R. Li, W. Gong, C. Lu, Self-adaptive multi-objective evolutionary algorithm for flexible job shop scheduling with fuzzy processing time, Comput. Ind. Eng., 168 (2022), 108099. https://doi.org/10.1016/j.cie.2022.108099 doi: 10.1016/j.cie.2022.108099
[16]	R. Liu, R. Piplani, C. Toro, Deep reinforcement learning for dynamic scheduling of a flexible job shop, Int. J. Prod. Res., 60 (2022), 4049–4069. https://doi.org/10.1080/00207543.2022.2058432 doi: 10.1080/00207543.2022.2058432
[17]	K. Lei, P. Guo, W. Zhao, Y. Wang, L. Qian, X. Meng, et al., A multi-action deep reinforcement learning framework for flexible Job-shop scheduling problem, Expert Syst. Appl., 205 (2022), 117796. https://doi.org/10.1016/j.eswa.2022.117796 doi: 10.1016/j.eswa.2022.117796
[18]	Y. Du, J. Li, X. Chen, P. Duan, Q. Pan, Knowledge-based reinforcement learning and estimation of distribution algorithm for flexible job shop scheduling problem, IEEE Trans. Emerging Top. Comput. Intell., 2022 (2022). https://doi.org/10.1109/TETCI.2022.3145706 doi: 10.1109/TETCI.2022.3145706
[19]	X. Li, K. Xing, Iterative widen heuristic beam search algorithm for scheduling problem of flexible assembly systems, IEEE Trans. Ind. Inf., 17 (2021), 7348–7358. https://doi.org/10.1109/TII.2021.3049338 doi: 10.1109/TII.2021.3049338
[20]	C. Finetto, M. Faccio, G. Rosati, A. Rossi, Mixed-model sequencing optimization for an automated single-station fully flexible assembly system (F-FAS), Int. J. Adv. Manuf. Technol., 70 (2014), 797–812. https://doi.org/10.1007/s00170-013-5308-z doi: 10.1007/s00170-013-5308-z
[21]	A. Hottenrott, M. Schiffer, M. Grunow, Flexible assembly layouts in smart manufacturing: An impact assessment for the automotive industry, IISE Trans., 2022 (2022). https://doi.org/10.1080/24725854.2022.2124470 doi: 10.1080/24725854.2022.2124470
[22]	W. Ren, J. Wen, Y. Yan, Y. Hu, Y. Guan, J. Li, Multi-objective optimisation for energy-aware flexible job-shop scheduling problem with assembly operations, Int. J. Prod. Res., 59 (2021), 7216–7231. https://doi.org/10.1080/00207543.2020.1836421 doi: 10.1080/00207543.2020.1836421
[23]	W. Lin, Q. Deng, W. Han, G. Gong, K. Li, An effective algorithm for flexible assembly job-shop scheduling with tight job constraints, Int. Trans. Oper. Res., 1 (2020). https://doi.org/10.1111/itor.12767 doi: 10.1111/itor.12767
[24]	P. Fattahi, N. B. Rad, F. Daneshamooz, S. Ahmadi, A new hybrid particle swarm optimization and parallel variable neighborhood search algorithm for flexible job shop scheduling with assembly process, Assem. Autom., 40 (2020), 419–432. https://doi.org/10.1108/AA-11-2018-0178 doi: 10.1108/AA-11-2018-0178
[25]	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
[26]	S. Zhang, S. Wang, Flexible assembly job-shop scheduling with sequence-dependent setup times and part sharing in a dynamic environment, constraint programming model, mixed-integer programming model, and dispatching rules, IEEE Trans. Eng. Manage., 65 (2018), 487–504. https://doi.org/10.1109/TEM.2017.2785774 doi: 10.1109/TEM.2017.2785774
[27]	X. Li, J. Lu, C. Yang, J. Wang, Research of flexible assembly job-shop batch-scheduling problem based on improved artificial bee colony, Front. Bioeng. Biotechnol., 10 (2022). https://doi.org/10.3389/fbioe.2022.909548 doi: 10.3389/fbioe.2022.909548
[28]	Z. Xie, X. Zhang, Y. Xia, J. Yang, Y. Xin, A hybrid method of heuristic algorithm and constraint programming for no-wait integrated scheduling problem, J. Int. Technol., 22 (2021), 1085–1092. https://doi.org/10.53106/160792642021092205012 doi: 10.53106/160792642021092205012
[29]	Z. Xie, W. Zhou, Z. Yu, Integrated scheduling algorithm for dynamic adjustment of equipment maintenance start time, J. Mech. Eng., 57 (2021), 240–246. https://doi.org/10.3901/JME.2021.04.240 doi: 10.3901/JME.2021.04.240
[30]	Z. Xie, N. Lv, Integrated scheduling algorithm with pre-start device, J. Mech. Eng., 57 (2021), 217–225. https://doi.org/10.3901/JME.2021.17.217 doi: 10.3901/JME.2021.17.217
[31]	Z. Xie, H. Teng, J. Ming, X. Yue, A two-workshop collaborative, integrated scheduling algorithm considering the prescheduling of the root-subtree processes, Comput. Intell. Neurosci., 2022 (2022). https://doi.org/10.1155/2022/9065638 doi: 10.1155/2022/9065638
[32]	X. Zhan, Z. Xie, D. Yao, Integrated scheduling algorithm of two workshops based on process end time driven and processing area priority, Electronics, 11 (2022), 2594. https://doi.org/10.3390/electronics11162594 doi: 10.3390/electronics11162594
[33]	Y. Gao, Z. Xie, X. Yu, A hybrid algorithm for integrated scheduling problem of complex products with tree structure, Multimedia Tools Appl., 79 (2020), 32285–32304. https://doi.org/doi.org/10.1007/s11042-020-09477-2 doi: 10.1007/s11042-020-09477-2
[34]	Z. Wang, C. Lu, An integrated job shop scheduling and assembly sequence planning approach for discrete manufacturing, J. Manuf. Syst., 61 (2021), 27–44. https://doi.org/10.1016/j.jmsy.2021.08.003 doi: 10.1016/j.jmsy.2021.08.003
[35]	Y. Gao, Z. Xie, D. Yang, X. Yu, Flexible integrated scheduling algorithm based on remaining work probability selection coding, Expert Syst., 38 (2021), e12683. https://doi.org/10.1111/exsy.12683 doi: 10.1111/exsy.12683
[36]	Z. Xie, Z. Gui, J. Yang, Dynamic parallel integrated flexible scheduling algorithm based on device driver and essential path, J. Mech. Eng., 50 (2014), 203–212. https://doi.org/10.3901/JME.2014.18.203 doi: 10.3901/JME.2014.18.203
[37]	Z. Xie, H. Zhou, J. Yu, Z. Gui, Conflict mediation algorithm of integrated flexible scheduling based on device driver, Trans. Beijing Inst. Technol., 34 (2014), 1150–1156. https://doi.org/10.3969/j.issn.1002-137X.2013.04.042 doi: 10.3969/j.issn.1002-137X.2013.04.042
[38]	H. Lu, G. Huang, H. Yang, Integrating order review/release and dispatching rules for assembly job shop scheduling using a simulation approach, Int. J. Prod. Res., 49 (2011), 647–669. https://doi.org/10.1080/00207540903524490 doi: 10.1080/00207540903524490
[39]	Z. Xie, S. Hao, G. Ye, G. Tan, A new algorithm for complex product flexible scheduling with constraint between jobs, Comput. Ind. Eng., 57 (2009), 766–772. https://doi.org/10.1016/j.cie.2009.02.004 doi: 10.1016/j.cie.2009.02.004
[40]	Z. Xie, Q. Wang, Flexible integrated scheduling algorithm based on reverse order layer priority, J. Electron. Inf. Technol., 44 (2022), 1554–1562. https://doi.org/10.11999/JEIT211378 doi: 10.11999/JEIT211378
[41]	R. El-Khalil, Z. Darwish, Flexible manufacturing systems performance in U.S. automotive manufacturing plants, a case study, Prod. Plann. Control, 30 (2019), 48–59. https://doi.org/10.1080/09537287.2018.1520318 doi: 10.1080/09537287.2018.1520318
[42]	X. Yang, J. Liu, Q. Chen, N. Mao, Performance analysis of flexible assembly job shop scheduling under variable distrurbance intensity, Comput. Integr. Manuf. Syst., 27 (2021), 800–814. https://doi.org/10.13196/j.cims.2021.03.013 doi: 10.13196/j.cims.2021.03.013

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)