A Robust Iterated Greedy Algorithm for Distributed Flow Shop Scheduling with Uncertain Inter-Factory Transportation Times

Fatemeh Zahra Montazeri; Maryam  Daneshmand-Mehr

doi:10.31181/sa202586

Authors

Fatemeh Zahra Montazeri Department of Industrial Engineering, La.C., Islamic Azad University, Lahijan, Iran. Author https://orcid.org/0000-0001-5439-2167
Maryam Daneshmand-Mehr Department of Industrial Engineering, La.C., Islamic Azad University, Lahijan, Iran. Author https://orcid.org/0000-0001-6926-9161

DOI:

https://doi.org/10.31181/sa202586

Keywords:

Distributed flow shop scheduling, Inter-factory transportation, Robust optimization, Iterated greedy algorithm, Uncertainty, Scheduling

Abstract

This study investigates the Distributed Flow Shop Scheduling Problem with Inter-Factory Transportation (DFSPT) under uncertain transportation times. In real-world manufacturing systems, the duration of inter-factory transfers is subject to fluctuations caused by various factors, including traffic congestion, adverse weather conditions, and logistical constraints. To model such variations, a comprehensive robust optimization framework based on the uncertainty budget approach is developed, which incorporates transportation time deviations without requiring any probabilistic distribution assumptions. Within this framework, the robust DFSPT model is formulated as a mixed-integer linear programming (MILP) model, where specific protection levels are defined for each job and machine. Furthermore, to address large-scale instances, the greedy iterative algorithm introduced by Becker et al. (2025) is extended by replacing the deterministic scheduling evaluation mechanism with a worst-case makespan estimation approach based on critical path analysis under uncertain conditions. Computational experiments conducted on 900 benchmark instances demonstrate that the proposed approach can reduce the worst-case production time by up to 15.3% compared with deterministic models that neglect uncertainty effects, while imposing only a 4.2% average increase in nominal production time. Therefore, the proposed methodology provides an effective and practical decision-support tool for managing risks arising from uncertainty in inter-factory transportation and enhancing scheduling decisions in multi-factory manufacturing networks.

References

Becker, T., Neufeld, J., & Buscher, U. (2025). The distributed flow shop scheduling problem with inter-factory transportation. European Journal of Operational Research, 322(1), 39–55. https://doi.org/10.1016/j.ejor.2024.10.026

Naderi, B., & Ruiz, R. (2010). The distributed permutation flowshop scheduling problem. Computers Operations Research, 37(4), 754–768. https://doi.org/10.1016/j.cor.2009.06.019

Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117–129. https://doi.org/10.1287/moor.1.2.117

Gao, J., & Chen, R. (2011). A hybrid genetic algorithm for the distributed permutation flowshop scheduling problem. International Journal of Computational Intelligence Systems, 4(4), 497–508. https://doi.org/10.1080/18756891.2011.9727808

Gao, J., Chen, R., & Deng, W. (2013). An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem. International Journal of Production Research, 51(3), 641–651. https://doi.org/10.1080/00207543.2011.644819

Lin, S. W., Ying, K. C., & Huang, C. Y. (2013). Minimising makespan in distributed permutation flowshops using a modified iterated greedy algorithm. International Journal of Production Research, 51(16), 5029–5038. https://doi.org/10.1080/00207543.2013.790571

Ruiz, R., Pan, Q. K., & Naderi, B. (2019). Iterated Greedy methods for the distributed permutation flowshop scheduling problem. Omega, 83, 213–222. https://doi.org/10.1016/j.omega.2018.03.004

Pan, Q. K., Gao, L., Wang, L., Liang, J., & Li, X. Y. (2019). Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem. Expert systems with applications, 124, 309-324. https://doi.org/10.1016/j.eswa.2019.01.062

Ren, J. F., Ye, C. M., & Li, Y. (2021). A new solution to distributed permutation flow shop scheduling problem based on NASH Q-Learning. Advances in Production Engineering Management, 16(3), 269–284. https://doi.org/10.14743/apem2021.3.399

Bargaoui, H., Driss, O. B., & Ghédira, K. (2017). A novel chemical reaction optimization for the distributed permutation flowshop scheduling problem with makespan criterion. Computers industrial Engineering, 111, 239–250. https://doi.org/10.1016/j.cie.2017.07.020

Ribas, I., Companys, R., & Tort-Martorell, X. (2017). Efficient heuristics for the parallel blocking flow shop scheduling problem. Expert Systems with Applications, 74, 41–54. https://doi.org/10.1016/j.eswa.2017.01.006

Shao, W., Pi, D., & Shao, Z. (2017). Optimization of makespan for the distributed no-wait flow shop scheduling problem with iterated greedy algorithms. Knowledge-Based Systems, 137, 163–181. https://doi.org/10.1016/j.knosys.2017.09.026

Guo, H., Sang, H., Zhang, B., Meng, L., & Liu, L. (2022). An effective metaheuristic with a differential flight strategy for the distributed permutation flowshop scheduling problem with sequence-dependent setup times. Knowledge-Based Systems, 242, 108328. https://doi.org/10.1016/j.knosys.2022.108328

Li, H., Li, X., & Gao, L. (2021). A discrete artificial bee colony algorithm for the distributed heterogeneous no-wait flowshop scheduling problem. Applied Soft Computing, 100, 106946. https://doi.org/10.1016/j.asoc.2020.106946

Cai, S., Yang, K., & Liu, K. (2018). Multi-objective optimization of the distributed permutation flow shop scheduling problem with transportation and eligibility constraints. Journal of The Operations Research Society of China, 6(3), 391–416. https://doi.org/10.1007/s40305-017-0165-3%0A%0A

Hou, Y., Fu, Y., Gao, K., Zhang, H., & Sadollah, A. (2022). Modelling and optimization of integrated distributed flow shop scheduling and distribution problems with time windows. Expert Systems with Applications, 187, 115827. https://doi.org/10.1016/j.eswa.2021.115827

Fu, Y., Hou, Y., Chen, Z., Pu, X., Gao, K., & Sadollah, A. (2022). Modelling and scheduling integration of distributed production and distribution problems via black widow optimization. Swarm and Evolutionary Computation, 68, 101015. https://doi.org/10.1016/j.swevo.2021.101015

Schulz, S., Schönheit, M., & Neufeld, J. S. (2022). Multi-objective carbon-efficient scheduling in distributed permutation flow shops under consideration of transportation efforts. Journal of Cleaner Production, 365, 132551. https://doi.org/10.1016/j.jclepro.2022.132551

Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53. https://doi.org/10.1287/opre.1030.0065

Juvin, C., Houssin, L., & pierre-lopez. (2025). Flow-shop and job-shop robust scheduling problems with budgeted uncertainty. European Journal of Operational Research, 326(1), 54–68. https://doi.org/10.1016/j.ejor.2025.04.012

Goren, S., & Sabuncuoglu, I. (2008). Robustness and stability measures for scheduling: single-machine environment. IIE Transactions, 40(1), 66–83. https://doi.org/10.1080/07408170701283198

Naderi, B., Ruiz, R., & Roshanaei, V. (2023). Mixed-integer programming vs. constraint programming for shop scheduling problems: new results and outlook. INFORMS Journal on Computing, 35(4), 817–843. https://doi.org/10.1287/ijoc.2023.1287

Wang, Z., Han, Z., Zhao, J., & Wang, W. (2024). Distributed robust scheduling optimization for energy system of steel industry considering prediction uncertainties. Information Sciences, 666, 120431. https://doi.org/10.1016/j.ins.2024.120431

Liu, Z., Mao, H., Sa, G., Liu, H., & Tan, J. (2024). Dynamic job-shop scheduling using graph reinforcement learning with auxiliary strategy. Journal of Manufacturing Systems, 73, 1–18. https://doi.org/10.1016/j.jmsy.2024.01.002