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

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.