An improved iterated greedy algorithm for scheduling distributed permutation flowshop problems with weighted total completion time criterion

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

doi:10.3934/math.20251256

AIMS Mathematics

2025, Volume 10, Issue 12: 28524-28555. doi: 10.3934/math.20251256

Previous Article Next Article

Research article Special Issues

An improved iterated greedy algorithm for scheduling distributed permutation flowshop problems with weighted total completion time criterion

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

Received: 23 October 2025 Revised: 23 November 2025 Accepted: 26 November 2025 Published: 03 December 2025
MSC : 68T40, 68W20

In this paper, distributed permutation flowshop problems with a weighted total completion time criterion (DPFSP-WTC) were addressed to minimize the completion time of all factories. First, the completion time of all factories were converted to a single one by a novel strategy, and a mixed integer programming model was developed. Second, an improved iterated greedy (IIG) algorithm was proposed. Based on features of the concerned problems, a simple heuristic is designed to improve the quality of initialization solutions. A local search operation was developed to improve the convergence performance of the proposed algorithm. Finally, numerous experiments were carried out for solving 720 instances with different scales. The proposed IIG was compared with five state-of-the-art algorithms. The comparisons and discussions showed that the proposed IIG has superior performance compared to its peers.
- distributed permutation flowshop scheduling,
- iterated greedy algorithm,
- makespan,
- weighted total completion time
Citation: Yuan-Zhen Li, Lei-Lei Meng, Biao Zhang. An improved iterated greedy algorithm for scheduling distributed permutation flowshop problems with weighted total completion time criterion[J]. AIMS Mathematics, 2025, 10(12): 28524-28555. doi: 10.3934/math.20251256

Related Papers:

Abstract

In this paper, distributed permutation flowshop problems with a weighted total completion time criterion (DPFSP-WTC) were addressed to minimize the completion time of all factories. First, the completion time of all factories were converted to a single one by a novel strategy, and a mixed integer programming model was developed. Second, an improved iterated greedy (IIG) algorithm was proposed. Based on features of the concerned problems, a simple heuristic is designed to improve the quality of initialization solutions. A local search operation was developed to improve the convergence performance of the proposed algorithm. Finally, numerous experiments were carried out for solving 720 instances with different scales. The proposed IIG was compared with five state-of-the-art algorithms. The comparisons and discussions showed that the proposed IIG has superior performance compared to its peers.

References

[1]	K. Gao, Y. Huang, A. Sadollah, L. Wang, A review of energy-efficient scheduling in intelligent production systems, Complex Intell. Syst., 6 (2020), 237–249. https://doi.org/10.1007/s40747-019-00122-6 doi: 10.1007/s40747-019-00122-6
[2]	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, Knowl. Based Syst., 239 (2022) 108036. https://doi.org/10.1016/j.knosys.2021.108036 doi: 10.1016/j.knosys.2021.108036
[3]	L. Meng, W. Cheng, C. Zhang, K. Gao, B. Zhang, Y. Ren, Novel CP models and CP-assisted meta-heuristic algorithm for flexible job shop scheduling benchmark problem with multi-AGV, IEEE Trans. Syst. Man Cybern. Syst., 55 (2025), 8455–8468. https://doi.org/10.1109/TSMC.2025.3604355 doi: 10.1109/TSMC.2025.3604355
[4]	K. Z. Gao, Z. M. He, Y. Huang, P. Y. Duan, P. N. Suganthan, A survey on meta-heuristics for solving disassembly line balancing, planning and scheduling problems in remanufacturing, Swarm Evol. Comput., 57 (2020), 100719. https://doi.org/10.1016/j.swevo.2020.100719 doi: 10.1016/j.swevo.2020.100719
[5]	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
[6]	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
[7]	Q. Pan, L. Gao, L. Wang, J. Liang, X. Li, Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem, Expert Syst. Appl., 124 (2019), 309–324. https://doi.org/10.1016/j.eswa.2019.01.062 doi: 10.1016/j.eswa.2019.01.062
[8]	V. Fernandez-Viagas, P. Perez-Gonzalez, J. M. Framinan, The distributed permutation flow shop to minimise the total flowtime, Comput. Ind. Eng., 118 (2018), 464–477. https://doi.org/10.1016/j.cie.2018.03.014 doi: 10.1016/j.cie.2018.03.014
[9]	A. Khare, S. Agrawal, Effective heuristics and metaheuristics to minimise total tardiness for the distributed permutation flowshop scheduling problem, Int. J. Prod. Res., 59 (2021), 7266–7282. https://doi.org/10.1080/00207543.2020.1837982 doi: 10.1080/00207543.2020.1837982
[10]	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
[11]	Y. Xu, L. Wang, S. Wang, M. Liu, An effective hybrid immune algorithm for solving the distributed permutation flow-shop scheduling problem, Eng. Optimiz., 46 (2014), 1269–1283. https://doi.org/10.1080/0305215X.2013.827673 doi: 10.1080/0305215X.2013.827673
[12]	S. W. Lin, K. C. Ying, C. Y. Huang, Minimising makespan in distributed permutation flowshops using a modified iterated greedy algorithm, Int. J. Prod. Res., 51 (2013), 5029–5038. https://doi.org/10.1080/00207543.2013.790571 doi: 10.1080/00207543.2013.790571
[13]	V. Fernandez-Viagas, J. M. Framinan, A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem, Int. J. Prod. Res., 53 (2014), 1111–1123. https://doi.org/10.1080/00207543.2014.948578 doi: 10.1080/00207543.2014.948578
[14]	R. Ruiz, Q. Pan, B. Naderi, Iterated Greedy methods for the distributed permutation flowshop scheduling problem, Omega, 83 (2019), 213–222. https://doi.org/10.1016/j.omega.2018.03.004 doi: 10.1016/j.omega.2018.03.004
[15]	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
[16]	H. Bargaoui, O. B. 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
[17]	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
[18]	N. B. Rad, J. Behnamian, Recent trends in distributed production network scheduling problem, Artif. Intell. Rev., 55 (2022), 2945–2995. https://doi.org/10.1007/s10462-021-10081-5 doi: 10.1007/s10462-021-10081-5
[19]	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
[20]	J. Pempera, C. Smutnicki, R. Wojcik, Minimizing the cycle time in the distributed flow shop scheduling problem, IFAC Pap., 54 (2021), 1081–1086. https://doi.org/10.1016/j.ifacol.2021.08.203 doi: 10.1016/j.ifacol.2021.08.203
[21]	K. Ying, S. Lin, C. Cheng, C. He, Iterated reference greedy algorithm for solving distributed no-idle permutation flowshop scheduling problems, Comput. Ind. Eng., 110 (2017), 413–423. https://doi.org/10.1016/j.cie.2017.06.025 doi: 10.1016/j.cie.2017.06.025
[22]	K. Ying, S. Lin, Minimizing makespan in distributed blocking flowshops using hybrid iterated greedy algorithms, IEEE Access, 5 (2017), 15694–15705. https://doi.org/10.1109/ACCESS.2017.2732738 doi: 10.1109/ACCESS.2017.2732738
[23]	G. Zhang, K. Xing, F. Cao, Discrete differential evolution algorithm for distributed blocking flowshop scheduling with makespan criterion, Eng. Appl. Artif. Intell., 76 (2018), 96–107. https://doi.org/10.1016/j.engappai.2018.09.005 doi: 10.1016/j.engappai.2018.09.005
[24]	K. Karabulut, D. Kizilay, M. F. Tasgetiren, L. Gao, L. Kandiller, An evolution strategy approach for the distributed blocking flowshop scheduling problem, Comput. Ind. Eng., 163 (2022), 107832. https://doi.org/10.1016/j.cie.2021.107832 doi: 10.1016/j.cie.2021.107832
[25]	W. Shao, D. Pi, Z. Shao, Optimization of makespan for the distributed no-wait flow shop scheduling problem with iterated greedy algorithms, Knowl. Based Syst., 137 (2017), 163–181. https://doi.org/10.1016/j.knosys.2017.09.026 doi: 10.1016/j.knosys.2017.09.026
[26]	N. N. Zhu, F. Q. Zhao, L. Wang, R. Q. Ding, T. P. Xu, Jonrinaldi, A discrete learning fruit fly algorithm based on knowledge for the distributed no-wait flow shop scheduling with due windows, Expert Syst. Appl., 198 (2022), 116921. https://doi.org/10.1016/j.eswa.2022.116921 doi: 10.1016/j.eswa.2022.116921
[27]	T. Meng, Q. Pan, L. Wang, A distributed permutation flowshop scheduling problem with the customer order constraint, Knowl. Based Syst., 184 (2019), 104894. https://doi.org/10.1016/j.knosys.2019.104894 doi: 10.1016/j.knosys.2019.104894
[28]	A. M. Fathollahi-Fard, L. Woodward, O. Akhrif, A distributed permutation flow-shop considering sustainability criteria and real-time scheduling, J. Ind. Inf. Integr., 39 (2024), 100598. https://doi.org/10.1016/j.jii.2024.100598 doi: 10.1016/j.jii.2024.100598
[29]	A. M. Fathollahi-Fard, L. Woodward, O. Akhrif, A scenario-based robust optimization model for the sustainable distributed permutation flow-shop scheduling problem, Ann. Oper. Res., 2024. https://doi.org/10.1007/s10479-024-05940-7 doi: 10.1007/s10479-024-05940-7
[30]	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
[31]	J. Wang, L. Wang, A knowledge-based cooperative algorithm for energy-efficient scheduling of distributed flow-shop, IEEE Trans. Syst. Man Cybern. Syst., 50 (2020), 1805–1819. https://doi.org/10.1109/TSMC.2017.2788879 doi: 10.1109/TSMC.2017.2788879
[32]	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
[33]	X. Zhang, X. Liu, A. Cichon, G. Królczyk, Z. Li, Scheduling of energy-efficient distributed blocking flowshop using pareto-based estimation of distribution algorithm, Expert Syst. Appl., 200 (2022), 116910. https://doi.org/10.1016/j.eswa.2022.116910 doi: 10.1016/j.eswa.2022.116910
[34]	J. Deng, L. Wang, C. Wu, J. Wang, X. Zheng, A competitive memetic algorithm for carbon-efficient scheduling of distributed flow-shop, In: Intelligent computing theories and application, Cham: Springer, 977 (2016), 476–488. https://doi.org/10.1007/978-3-319-42291-6_48
[35]	Y. Fu, G. Tian, A. M. Fathollahi-Fard, A. Ahmadi, C. Zhang, Stochastic multi-objective modelling and optimization of an energy-conscious distributed permutation flow shop scheduling problem with the total tardiness constraint, J. Clean. Prod., 226 (2019), 515–525. https://doi.org/10.1016/j.jclepro.2019.04.046 doi: 10.1016/j.jclepro.2019.04.046
[36]	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
[37]	A. M. Fathollahi-Fard, L. Woodward, O. Akhrif, Sustainable distributed permutation flow-shop scheduling model based on a triple bottom line concept, J. Ind. Inf. Integr., 24 (2021) 100233. https://doi.org/10.1016/j.jii.2021.100233 doi: 10.1016/j.jii.2021.100233
[38]	J. Deng, L. Wang, A competitive memetic algorithm for multi-objective distributed permutation flow shop scheduling problem, Swarm Evol. Comput., 32 (2017), 121–131. https://doi.org/10.1016/j.swevo.2016.06.002 doi: 10.1016/j.swevo.2016.06.002
[39]	Q. H. Liu, X. Y. Li, L. Gao, G. C. Wang, A multiobjective memetic algorithm for integrated process planning and scheduling problem in distributed heterogeneous manufacturing systems, Memetic Comp., 14 (2022), 193–209. https://doi.org/10.1007/s12293-022-00364-x doi: 10.1007/s12293-022-00364-x
[40]	K. Allali, S. Aqil, J. Belabid, Distributed no-wait flow shop problem with sequence dependent setup time: Optimization of makespan and maximum tardiness, Simul. Model. Pract. Theory, 116 (2022), 102455. https://doi.org/10.1016/j.simpat.2021.102455 doi: 10.1016/j.simpat.2021.102455
[41]	A. P. Rifai, S. T. W. Mara, A. Sudiarso, Multi-objective distributed reentrant permutation flow shop scheduling with sequence-dependent setup time, Expert Syst. Appl., 183 (2021), 115339. https://doi.org/10.1016/j.eswa.2021.115339 doi: 10.1016/j.eswa.2021.115339
[42]	W. Q. Zhang, C. Li, M. S. Gen, W. D. Yang, Z. W. Zhang, G. H. Zhang, Multiobjective particle swarm optimization with direction search and differential evolution for distributed flow-shop scheduling problem, Math. Biosci. Eng., 19 (2022), 8833–8865. https://doi.org/10.3934/mbe.2022410 doi: 10.3934/mbe.2022410
[43]	A. M. Fathollahi-Fard, P. Wu, G. Tian, D. Yu, T. Zhang, J. Yang, et al., An efficient multi-objective adaptive large neighborhood search algorithm for solving a disassembly line balancing model considering idle rate, smoothness, labor cost, and energy consumption, Expert Syst. Appl., 250 (2024), 123908. https://doi.org/10.1016/j.eswa.2024.123908 doi: 10.1016/j.eswa.2024.123908
[44]	M. E. Baysal, A. Sarucan, K. Buyukozkan, O. Engin, Artificial bee colony algorithm for solving multi-objective distributed fuzzy permutation flow shop problem, J. Intell. Fuzzy Syst., 42 (2022), 439–449. https://doi.org/10.3233/JIFS-219202 doi: 10.3233/JIFS-219202
[45]	K. Gao, F. Yang, M. Zhou, Q. Pan, P. N. Suganthan, Flexible job-shop rescheduling for new job insertion by using discrete Jaya algorithm, IEEE Trans. Cybern., 49 (2019), 1944–1955. https://doi.org/10.1109/TCYB.2018.2817240 doi: 10.1109/TCYB.2018.2817240
[46]	Y. Pan, K. Gao, Z. Li, N. Wu, Solving biobjective distributed flow-shop scheduling problems with lot-streaming using an improved Jaya algorithm, IEEE Trans. Cybern., 53 (2023), 3818–3828. https://doi.org/10.1109/TCYB.2022.3164165 doi: 10.1109/TCYB.2022.3164165
[47]	R. Ruiz, T. Stützle, A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, Eur. J. Oper. Res., 177 (2007), 2033–2049. https://doi.org/10.1016/j.ejor.2005.12.009 doi: 10.1016/j.ejor.2005.12.009
[48]	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
[49]	Y. X. Pan, K. Z. Gao, Z. W. Li, N. Q. Wu, Improved Meta-Heuristics for solving distributed lot-streaming permutation flow shop scheduling problems, IEEE Trans. Autom. Sci. Eng., 20 (2023), 361–371. https://doi.org/10.1109/TASE.2022.3151648 doi: 10.1109/TASE.2022.3151648

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)