Two-stage iterated greedy algorithm for distributed flexible assembly permutation flowshop scheduling problems with sequence-dependent setup times

Yuan-Zhen Li; Lei-Lei Meng; Biao Zhang; Yuan-Zhen Li; Lei-Lei Meng; Biao Zhang

doi:10.3934/math.2025523

AIMS Mathematics

2025, Volume 10, Issue 5: 11488-11513. doi: 10.3934/math.2025523

Previous Article Next Article

Research article Special Issues

Two-stage iterated greedy algorithm for distributed flexible assembly permutation flowshop scheduling problems with sequence-dependent setup times

School of Computer Science, Liaocheng University, Liaocheng 252000, China

Received: 27 March 2025 Revised: 30 April 2025 Accepted: 12 May 2025 Published: 20 May 2025
MSC : 68T40, 68W20

In this study, the distributed flexible assembly permutation flowshop scheduling problem (DFAPFSP) with sequence-dependent setup times and makespan criterion was investigated. The DFAPFSP comprises two distinct phases: a distributed permutation flowshop in the initial stage, followed by an integration phase. The integration stage, which employs multiple parallel assembly machines, achieves significantly higher throughput efficiency compared to monolithic assembly machine architectures in high-volume manufacturing scenarios. A novel mixed-integer linear programming model was established to describe the problem. The DFAPFSP can be divided into two stages: production and assembly. A two-stage iterated greedy (TSIG) algorithm was designed based on the two-stage characteristics of the DFAPFSP. In the first stage, the production plan is optimized, and in the second stage, the assembly plan is optimized. The destruction, reconstruction, and local search algorithms in the two stages and acceptance criterion were redesigned. Numerous computational experiments and performance evaluations were performed by comparing the TSIG algorithm with state-of-the-art algorithms. The results and discussions show that the proposed TSIG algorithm is better than its peers for solving the DFAPFSP.
- optimization,
- distributed permutation flowshop scheduling,
- flexible assembly,
- sequence-dependent setup times,
- makespan,
- two-stage iterated greedy algorithm
Citation: Yuan-Zhen Li, Lei-Lei Meng, Biao Zhang. Two-stage iterated greedy algorithm for distributed flexible assembly permutation flowshop scheduling problems with sequence-dependent setup times[J]. AIMS Mathematics, 2025, 10(5): 11488-11513. doi: 10.3934/math.2025523

Related Papers:

Abstract

In this study, the distributed flexible assembly permutation flowshop scheduling problem (DFAPFSP) with sequence-dependent setup times and makespan criterion was investigated. The DFAPFSP comprises two distinct phases: a distributed permutation flowshop in the initial stage, followed by an integration phase. The integration stage, which employs multiple parallel assembly machines, achieves significantly higher throughput efficiency compared to monolithic assembly machine architectures in high-volume manufacturing scenarios. A novel mixed-integer linear programming model was established to describe the problem. The DFAPFSP can be divided into two stages: production and assembly. A two-stage iterated greedy (TSIG) algorithm was designed based on the two-stage characteristics of the DFAPFSP. In the first stage, the production plan is optimized, and in the second stage, the assembly plan is optimized. The destruction, reconstruction, and local search algorithms in the two stages and acceptance criterion were redesigned. Numerous computational experiments and performance evaluations were performed by comparing the TSIG algorithm with state-of-the-art algorithms. The results and discussions show that the proposed TSIG algorithm is better than its peers for solving the DFAPFSP.

References

[1]	K. Karabulut, H. Öztop, D. Kizilay, M. F. Tasgetiren, L. Kandiller, An evolution strategy approach for the distributed permutation flowshop scheduling problem with sequence-dependent setup times, Comput. Oper. Res., 142 (2022), 105733. https://doi.org/10.1016/j.cor.2022.105733 doi: 10.1016/j.cor.2022.105733
[2]	L. Meng, K. Gao, Y. Ren, B. Zhang, H. Sang, C. Zhang, Novel MILP and CP models for distributed hybrid flowshop scheduling problem with sequence-dependent setup times, Swarm Evol. Comput., 71 (2022), 101058. https://doi.org/10.1016/j.swevo.2022.101058 doi: 10.1016/j.swevo.2022.101058
[3]	S. Schulz, M. Schönheit, J. S. Neufeld, Multi-objective carbon-efficient scheduling in distributed permutation flow shops under consideration of transportation efforts, J. Clean. Prod., 365 (2022), 132551. https://doi.org/10.1016/j.jclepro.2022.132551 doi: 10.1016/j.jclepro.2022.132551
[4]	W. Li, X. Chen, J. Li, H. Sang, Y. Han, S. Du, An improved iterated greedy algorithm for distributed robotic flowshop scheduling with order constraints, Comput. Ind. Eng., 164 (2022), 107907. https://doi.org/10.1016/j.cie.2021.107907 doi: 10.1016/j.cie.2021.107907
[5]	Y. Li, Q. Pan, K. Gao, M. F. Tasgetiren, B. Zhang, J. Li, A green scheduling algorithm for the distributed flowshop problem, Appl. Soft Comput., 109 (2021), 107526. https://doi.org/10.1016/j.asoc.2021.107526 doi: 10.1016/j.asoc.2021.107526
[6]	M. Li, G. Wang, A review of green shop scheduling problem, Inf. Sci., 589 (2022), 478–496. https://doi.org/10.1016/j.ins.2021.12.122 doi: 10.1016/j.ins.2021.12.122
[7]	Z. Wang, Q. Pan, L. Gao, Y. Wang, An effective two-stage iterated greedy algorithm to minimize total tardiness for the distributed flowshop group scheduling problem, Swarm Evol. Comput., 74 (2022), 101143. https://doi.org/10.1016/j.swevo.2022.101143 doi: 10.1016/j.swevo.2022.101143
[8]	B. Zhang, Q. Pan, L. Meng, C. Lu, J. Mou, J. Li, An automatic multi-objective evolutionary algorithm for the hybrid flowshop scheduling problem with consistent sublots, Knowledge-Based Syst., 238 (2022), 107819. https://doi.org/10.1016/j.knosys.2021.107819 doi: 10.1016/j.knosys.2021.107819
[9]	W. Niu, J. Li, A two-stage cooperative evolutionary algorithm for energy-efficient distributed group blocking flow shop with setup carryover in precast systems, Knowledge-Based Syst., 257 (2022), 109890. https://doi.org/10.1016/j.knosys.2022.109890 doi: 10.1016/j.knosys.2022.109890
[10]	Y. Fu, Y. Hou, Z. Wang, X. Wu, K. Gao, L. Wang, Distributed scheduling problems in intelligent manufacturing systems, Tsinghua Sci. Technol., 26 (2021), 625–645. https://doi.org/10.26599/TST.2021.9010009 doi: 10.26599/TST.2021.9010009
[11]	N. Bagheri Rad, J. Behnamian, Recent trends in distributed production network scheduling problem, Artif. Intell. Rev., 55 (2021), 2945–2995. https://doi.org/10.1007/s10462-021-10081-5 doi: 10.1007/s10462-021-10081-5
[12]	C. Lu, Y. Huang, L. Meng, L. Gao, B. Zhang, J. Zhou, A Pareto-based collaborative multi-objective optimization algorithm for energy-efficient scheduling of distributed permutation flow-shop with limited buffers, Robot. Comput.-Integr. Manuf., 74 (2022), 102277. https://doi.org/10.1016/j.rcim.2021.102277 doi: 10.1016/j.rcim.2021.102277
[13]	B. Naderi, R. Ruiz, The distributed permutation flowshop scheduling problem, Comput. Oper. Res., 37 (2010), 754–768. https://doi.org/10.1016/j.cor.2009.06.019 doi: 10.1016/j.cor.2009.06.019
[14]	S. Hatami, R. Ruiz, C. Andres-Romano, The distributed assembly permutation flowshop scheduling problem, Int. J. Prod. Res., 51 (2013), 5292–5308. https://doi.org/10.1080/00207543.2013.807955 doi: 10.1080/00207543.2013.807955
[15]	Y. Li, Q. Pan, R. Ruiz, H. Sang, A referenced iterated greedy algorithm for the distributed assembly mixed no-idle permutation flowshop scheduling problem with the total tardiness criterion, Knowledge-Based Syst., 239 (2022), 108036. https://doi.org/10.1016/j.knosys.2021.108036 doi: 10.1016/j.knosys.2021.108036
[16]	Y. Xu, L. Wang, S. Wang, M. Liu, An effective hybrid immune algorithm for solving the distributed permutation flow-shop scheduling problem, Eng. Optim., 46 (2014), 1269–1283. https://doi.org/10.1080/0305215X.2013.827673 doi: 10.1080/0305215X.2013.827673
[17]	J. Gao, R. Chen, W. Deng, An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem, Int. J. Prod. Res., 51 (2013), 641–651. https://doi.org/10.1080/00207543.2011.644819 doi: 10.1080/00207543.2011.644819
[18]	Y. Li, Q. Pan, X. He, H. Sang, K. Gao, X. Jing, The distributed flowshop scheduling problem with delivery dates and cumulative payoffs, Comput. Ind. Eng., 165 (2022), 107961. https://doi.org/10.1016/j.cie.2022.107961 doi: 10.1016/j.cie.2022.107961
[19]	X. Han, Y. Han, B. Zhang, H. Qin, J. Li, Y. Liu, et al., An effective iterative greedy algorithm for distributed blocking flowshop scheduling problem with balanced energy costs criterion, Appl. Soft Comput., 129 (2022), 109502. https://doi.org/10.1016/j.asoc.2022.109502 doi: 10.1016/j.asoc.2022.109502
[20]	C. Lu, Q. Liu, B. Zhang, L. Yin, A Pareto-based hybrid iterated greedy algorithm for energy-efficient scheduling of distributed hybrid flowshop, Expert Syst. Appl., 204 (2022), 117555. https://doi.org/10.1016/j.eswa.2022.117555 doi: 10.1016/j.eswa.2022.117555
[21]	H. Qin, Y. Han, Y. Liu, J. Li, Q. Pan, X. Han, A collaborative iterative greedy algorithm for the scheduling of distributed heterogeneous hybrid flow shop with blocking constraints, Expert Syst. Appl., 201 (2022), 117256. https://doi.org/10.1016/j.eswa.2022.117256 doi: 10.1016/j.eswa.2022.117256
[22]	B. Naderi, R. Ruiz, A scatter search algorithm for the distributed permutation flowshop scheduling problem, Eur. J. Oper. Res., 239 (2014), 323–334. https://doi.org/10.1016/j.ejor.2014.05.024 doi: 10.1016/j.ejor.2014.05.024
[23]	H. Bargaoui, O. Belkahla Driss, K. Ghédira, A novel chemical reaction optimization for the distributed permutation flowshop scheduling problem with makespan criterion, Comput. Ind. Eng., 111 (2017), 239–250. https://doi.org/10.1016/j.cie.2017.07.020 doi: 10.1016/j.cie.2017.07.020
[24]	H. Li, X. Li, L. Gao, A discrete artificial bee colony algorithm for the distributed heterogeneous no-wait flowshop scheduling problem, Appl. Soft Comput., 100 (2021), 106946. https://doi.org/10.1016/j.asoc.2020.106946 doi: 10.1016/j.asoc.2020.106946
[25]	Y. Yu, F. Zhang, G. Yang, Y. Wang, J. Huang, Y. Han, A discrete artificial bee colony method based on variable neighborhood structures for the distributed permutation flowshop problem with sequence-dependent setup times, Swarm Evol. Comput., 75 (2022), 101179. https://doi.org/10.1016/j.swevo.2022.101179 doi: 10.1016/j.swevo.2022.101179
[26]	H. Guo, H. Sang, B. Zhang, L. Meng, L. Liu, An effective metaheuristic with a differential flight strategy for the distributed permutation flowshop scheduling problem with sequence-dependent setup times, Knowledge-Based Syst., 242 (2022), 108328. https://doi.org/10.1016/j.knosys.2022.108328 doi: 10.1016/j.knosys.2022.108328
[27]	G. Zhang, K. Xing, Differential evolution metaheuristics for distributed limited-buffer flowshop scheduling with makespan criterion, Comput. Oper. Res., 108 (2019), 33–43. https://doi.org/10.1016/j.cor.2019.04.002 doi: 10.1016/j.cor.2019.04.002
[28]	S. Lin, K. Ying, Minimizing makespan for solving the distributed no-wait flowshop scheduling problem, Comput. Ind. Eng., 99 (2016), 202–209. https://doi.org/10.1016/j.cie.2016.07.027 doi: 10.1016/j.cie.2016.07.027
[29]	C. Cheng, K. Ying, H. Chen, H. Lu, Minimising makespan in distributed mixed no-idle flowshops, Int. J. Prod. Res., 57 (2019), 48–60. https://doi.org/10.1080/00207543.2018.1457812 doi: 10.1080/00207543.2018.1457812
[30]	L. Meng, C. Zhang, Y. Ren, B. Zhang, C. Lv, Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem, Comput. Ind. Eng., 142 (2020), 106347. https://doi.org/10.1016/j.cie.2020.106347 doi: 10.1016/j.cie.2020.106347
[31]	X. Tao, Q. Pan, L. Gao, An efficient self-adaptive artificial bee colony algorithm for the distributed resource-constrained hybrid flowshop problem, Comput. Ind. Eng., 169 (2022), 108200. https://doi.org/10.1016/j.cie.2022.108200 doi: 10.1016/j.cie.2022.108200
[32]	J. Mou, P. Duan, L. Gao, X. Liu, J. Li, An effective hybrid collaborative algorithm for energy-efficient distributed permutation flow-shop inverse scheduling, Future Gener. Comput. Syst., 128 (2022), 521–537. https://doi.org/10.1016/j.future.2021.10.003 doi: 10.1016/j.future.2021.10.003
[33]	Y. Pan, K. Gao, Z. Li, N. Wu, Solving biobjective distributed flow-shop scheduling problems with lot-streaming using an improved Jaya algorithm, IEEE T. Cybern., 53 (2022), 3818–3828. https://doi.org/10.1109/TCYB.2022.3164165 doi: 10.1109/TCYB.2022.3164165
[34]	S. Wang, L. Wang, An estimation of distribution algorithm-based memetic algorithm for the distributed assembly permutation flow-shop scheduling problem, IEEE Trans. Syst. Man Cybernet.: Syst., 46 (2016), 139–149. https://doi.org/10.1109/TSMC.2015.2416127 doi: 10.1109/TSMC.2015.2416127
[35]	J. Deng, L. Wang, S. Wang, X. Zheng, A competitive memetic algorithm for the distributed two-stage assembly flow-shop scheduling problem, Int. J. Prod. Res., 54 (2016), 3561–3577. https://doi.org/10.1080/00207543.2015.1084063 doi: 10.1080/00207543.2015.1084063
[36]	J. Lin, Z. Wang, X. Li, A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem, Swarm Evol. Comput., 36 (2017), 124–135. https://doi.org/10.1016/j.swevo.2017.04.007 doi: 10.1016/j.swevo.2017.04.007
[37]	J. Lin, S. Zhang, An effective hybrid biogeography-based optimization algorithm for the distributed assembly permutation flow-shop scheduling problem, Comput. Ind. Eng., 97 (2016), 128–136. https://doi.org/10.1016/j.cie.2016.05.005 doi: 10.1016/j.cie.2016.05.005
[38]	Z. Q. Zhang, B. Qian, R. Hu, H. P. Jin, L. Wang, A matrix-cube-based estimation of distribution algorithm for the distributed assembly permutation flow-shop scheduling problem, Swarm Evol. Comput., 60 (2021). https://doi.org/10.1016/j.swevo.2020.100785 doi: 10.1016/j.swevo.2020.100785
[39]	D. Ferone, S. Hatami, E. M. Gonzalez-Neira, A. A. Juan, P. Festa, A biased-randomized iterated local search for the distributed assembly permutation flow-shop problem, Int. Trans. Oper. Res., 27 (2020), 1368–1391. https://doi.org/10.1111/itor.12719 doi: 10.1111/itor.12719
[40]	H. Sang, Q. Pan, J. Li, P. Wang, Y. Han, K. Gao, et al., Effective invasive weed optimization algorithms for distributed assembly permutation flowshop problem with total flowtime criterion, Swarm Evol. Comput., 44 (2019), 64–73. https://doi.org/10.1016/j.swevo.2018.12.001 doi: 10.1016/j.swevo.2018.12.001
[41]	Y. Huang, Q. Pan, J. Huang, P. N. Suganthan, L. Gao, An improved iterated greedy algorithm for the distributed assembly permutation flowshop scheduling problem, Comput. Ind. Eng., 152 (2021), 107021. https://doi.org/10.1016/j.cie.2020.107021 doi: 10.1016/j.cie.2020.107021
[42]	Y. H. Yang, X. Li, A knowledge-driven constructive heuristic algorithm for the distributed assembly blocking flow shop scheduling problem, Expert Syst. Appl., 202 (2022), 117269. https://doi.org/10.1016/j.eswa.2022.117269 doi: 10.1016/j.eswa.2022.117269
[43]	Z. S. Shao, W. S. Shao, D. C. Pi, Effective constructive heuristic and metaheuristic for the distributed assembly blocking flow-shop scheduling problem, Appl. Intell., 50 (2020), 4647–4669. https://doi.org/10.1007/s10489-020-01809-x doi: 10.1007/s10489-020-01809-x
[44]	F. Zhao, L. Zhang, J. Cao, J. Tang, A cooperative water wave optimization algorithm with reinforcement learning for the distributed assembly no-idle flowshop scheduling problem, Comput. Ind. Eng., 153 (2021), 107082. https://doi.org/10.1016/j.cie.2020.107082 doi: 10.1016/j.cie.2020.107082
[45]	H. B. Song, J. Lin, A genetic programming hyper-heuristic for the distributed assembly permutation flow-shop scheduling problem with sequence dependent setup times, Swarm Evol. Comput., 60 (2021), 100807. https://doi.org/10.1016/j.swevo.2020.100807 doi: 10.1016/j.swevo.2020.100807
[46]	F. Q. Zhao, J. L. Zhao, L. Wang, J. X. Tang, An optimal block knowledge driven backtracking search algorithm for distributed assembly No-wait flow shop scheduling problem, Appl. Soft Comput., 112 (2021), 107750. https://doi.org/10.1016/j.asoc.2021.107750 doi: 10.1016/j.asoc.2021.107750
[47]	J. C. Cai, D. M. Lei, J. Wang, L. Wang, A novel shuffled frog-leaping algorithm with reinforcement learning for distributed assembly hybrid flow shop scheduling, Int. J. Prod. Res., (2022), 1233–1251. https://doi.org/10.1080/00207543.2022.2031331 doi: 10.1080/00207543.2022.2031331
[48]	M. Li, B. Su, D. M. Lei, A novel imperialist competitive algorithm for fuzzy distributed assembly flow shop scheduling, J. Intell. Fuzzy Syst., 40 (2021), 4545–4561. https://doi.org/10.3233/JIFS-201391 doi: 10.3233/JIFS-201391
[49]	J. G. Zheng, Y. L. Wang, A hybrid bat algorithm for solving the three-stage distributed assembly permutation flowshop scheduling problem, Appl. Sci., 11 (2021), 10102. https://doi.org/10.3390/app112110102 doi: 10.3390/app112110102
[50]	F. Q. Zhao, X. T. Hu, L. Wang, T. P. Xu, N. N. Zhu, N. N. Zhu, A reinforcement learning-driven brain storm optimisation algorithm for multi-objective energy-efficient distributed assembly no-wait flow shop scheduling problem, Int. J. Prod. Res., 61 (2022), 2854–2872. https://doi.org/10.1080/00207543.2022.2070786 doi: 10.1080/00207543.2022.2070786
[51]	Z. Q. Zhang, R. Hu, B. Qian, H. P. Jin, L. Wang, J. B. Yang, A matrix cube-based estimation of distribution algorithm for the energy-efficient distributed assembly permutation flow-shop scheduling problem, Expert Syst. Appl., 194 (2022), 116484. https://doi.org/10.1016/j.eswa.2021.116484 doi: 10.1016/j.eswa.2021.116484
[52]	Y. Huang, Q. Pan, L. Gao, Z. Miao, C. Peng, A two-phase evolutionary algorithm for multi-objective distributed assembly permutation flowshop scheduling problem, Swarm Evol. Comput., 74 (2022), 101128. https://doi.org/10.1016/j.swevo.2022.101128 doi: 10.1016/j.swevo.2022.101128
[53]	G. H. Zhang, K. Y. Xing, F. Cao, Scheduling distributed flowshops with flexible assembly and set-up time to minimise makespan, Int. J. Prod. Res., 56 (2018), 3226–3244. https://doi.org/10.1080/00207543.2017.1401241 doi: 10.1080/00207543.2017.1401241
[54]	K. Ying, P. Pourhejazy, C. Cheng, R. Syu, Supply chain-oriented permutation flowshop scheduling considering flexible assembly and setup times, Int. J. Prod. Res., 61 (2020), 258–281. https://doi.org/10.1080/00207543.2020.1842938 doi: 10.1080/00207543.2020.1842938
[55]	G. H. Zhang, K. Y. Xing, G. Y. Zhang, Z. X. He, Memetic algorithm with meta-Lamarckian learning and simplex search for distributed flexible assembly permutation flowshop scheduling problem, IEEE Access, 8 (2020), 96115–96128. https://doi.org/10.1109/ACCESS.2020.2996305 doi: 10.1109/ACCESS.2020.2996305
[56]	S. Yang, Z. Xu, The distributed assembly permutation flowshop scheduling problem with flexible assembly and batch delivery, Int. J. Prod. Res., 59 (2021), 4053–4071. https://doi.org/10.1080/00207543.2020.1757174 doi: 10.1080/00207543.2020.1757174
[57]	Z. Zhao, M. Zhou, S. Liu, Iterated greedy algorithms for flow-shop scheduling problems: A tutorial, IEEE Trans. Autom. Sci. Eng., 19 (2022), 1941–1959. https://doi.org/10.1109/TASE.2021.3062994 doi: 10.1109/TASE.2021.3062994
[58]	S. Hatami, R. Ruiz, C. Andrés-Romano, Heuristics and metaheuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup times, Int. J. Prod. Econ., 169 (2015), 76–88. https://doi.org/10.1016/j.ijpe.2015.07.027 doi: 10.1016/j.ijpe.2015.07.027

Reader Comments

Your name:*

Email:*
© 2025 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)