Minimization of Total Tardiness in Flow Shop with Sequence Dependent Setup Times and Operator Constraints Using Particle Swarm Optimization

Naeimi Sadigh, Alireza; Zarei, Azim; Ebrahimi, Mehdi; Meftahi, Mohammad

doi:10.22054/jims.2026.91849.3021

Minimization of Total Tardiness in Flow Shop with Sequence Dependent Setup Times and Operator Constraints Using Particle Swarm Optimization

Document Type : Research Paper

Authors

Alireza Naeimi Sadigh ¹

Azim Zarei ²

Mehdi Ebrahimi ³

Mohammad Meftahi ³

¹ Department of Computer Science, Faculty of Mathematics, Statistics and Computer Science, Semnan, Semnan, Iran

² Department of Business Administration, Faculty of Economics, Management and Administrative Sciences, Semnan, Semnan, Iran

³ Department of Industrial Management, Faculty of Economics, Management and Administrative Sciences, Semnan, Semnan, Iran

https://doi.org/10.22054/jims.2026.91849.3021

Abstract

The flow shop scheduling problem with sequence-dependent setup times and operator constraints represents a complex and practically relevant production planning challenge due to the simultaneous integration of sequencing, timing, and human resource allocation decisions, making its exact solution computationally intractable for medium- and large-scale instances. This study proposed an integrated modeling and solution framework aimed at minimizing total order tardiness while jointly incorporating key operational constraints, including technological precedence, machine non-overlapping, sequence-dependent setup times (satisfying the triangle inequality), and multi-skilled operator capacity limitations. In this regard, a mixed-integer linear programming (MILP) model was first developed to explicitly capture sequencing, scheduling, and operator assignment decisions within a unified structure. Given the computational complexity of the model and the inefficiency of exact methods for real-world scales, an approximate solution approach based on Particle Swarm Optimization (PSO) was designed; to accommodate the combinatorial structure of the problem, a continuous encoding mechanism combined with a constructive decoder (based on FIFO logic) was implemented to enforce key constraints during solution evaluation. The performance of the proposed algorithm was evaluated through an industrial case study, a comparative benchmark against a Genetic Algorithm (GA), and multiple independent runs with different random seeds, assessing key performance indicators such as the best objective value, mean and standard deviation of results, computational time, and convergence behavior. Results demonstrated that the proposed PSO achieved high-quality and stable solutions with acceptable computational effort, exhibiting significant superiority over the benchmark algorithm in terms of average solution quality, stability, and runtime; furthermore, sensitivity analysis of parameters and problem dimensions indicated that stronger exploration enhances robustness and solution quality at the cost of longer runtime, whereas exploitative settings accelerate convergence but reduce solution quality. Overall, combining precise operational constraint modeling with flexible metaheuristic algorithms provided an efficient approach for solving complex scheduling problems in real-world production environments and can serve as an effective decision-support tool in production management.
Introduction
Production scheduling in multi-stage manufacturing systems represents a fundamental operational challenge that directly impacts delivery reliability, customer service levels, resource utilization, and tardiness-related financial penalties. In modern process and assembly industries such as the chemical, food, and detergent manufacturing sectors, production efficiency depends heavily not only on processing times but also on sequence-dependent setup operations resulting from line washouts, tooling adjustments, and material transitions. Concurrently, human resources serve as critical shared constraints across production stations, where operations cannot proceed without the presence of a dedicated, skilled operator. Classical flow shop models frequently overlook operator limitations or treat setup durations as negligible, leading to unrealistic schedules, unexpected bottlenecks, and significant delivery delays. To bridge this gap, this study investigated a permutation flow shop scheduling problem with sequence-dependent setup times (satisfying the triangle inequality) and multi-skilled operator constraints, aimed at minimizing total order tardiness. By integrating human workforce dynamics with technical workstation constraints, this research provided a comprehensive decision-making framework to balance order sequencing, setup overheads, and labor allocation.
Methodology
The study initially developed a rigorous Mixed-Integer Linear Programming formulation that unifies order sequencing, machine precedence, non-overlapping constraints, sequence-dependent transitions, and dedicated operator commitments across both setup and processing phases. Given the NP-hard nature of the problem and the computational intractability of exact solvers for industrial-scale instances, an approximate optimization approach based on Particle Swarm Optimization was developed. To effectively map the continuous search space of the swarm algorithm into discrete combinatorial schedules, a dual random-key continuous encoding mechanism was utilized to govern both job sequence permutations and operator-to-operation assignments. A constructive simulation decoder incorporating a first-in, first-out priority dispatching rule resolved operator contention dynamically and enforced all technological and resource constraints during solution evaluation. The proposed framework was validated using real-world industrial data from a detergent manufacturing facility involving multi-station lines, sequence-dependent changeovers, and constrained multi-skilled operators. Furthermore, the algorithm was evaluated through comparative benchmarking against a Genetic Algorithm with an identical decoding mechanism, multi-seed statistical replications, and systematic sensitivity analyses across algorithm hyperparameters and problem dimensions.
Findings
Computational experiments demonstrated the superior performance, stability, and computational efficiency of the proposed Particle Swarm Optimization algorithm. In the industrial case study, both metaheuristics identified the minimum tardiness objective of 24.6 hours; however, the proposed Particle Swarm Optimization framework achieved statistically superior average tardiness (25.27 versus 26.85), significantly lower standard deviation (1.43 versus 2.15), and reduced computational runtime (3.26 seconds versus 4.18 seconds) compared to the Genetic Algorithm. Convergence trajectory analyses indicated rapid search progression within the first fifty iterations, effectively avoiding premature stagnation through dynamic inertia control and perturbation mechanisms. Sensitivity analysis demonstrated that explorative configurations with larger swarm sizes enhanced solution robustness and consistency, whereas overly exploitative settings accelerate convergence at the expense of solution quality. In addition, scalability assessments across medium-scale (20 jobs, 5 machines) and large-scale (50 jobs, 10 machines) problem instances confirmed that the proposed framework delivered high-quality schedules within reasonable computational time frames when iteration limits are calibrated to problem scale.
Discussion and Conclusion
The findings underlined that achieving optimal delivery performance in modern production lines requires the synchronized optimization of machine schedules, sequence-dependent changeovers, and human labor assignments. Treating operator constraints independently from sequencing decisions leads to suboptimal or practically unfeasible production schedules. The developed framework served as an effective decision-support tool for operations managers, enabling them to evaluate operational trade-offs between delivery commitments, labor availability, and setup losses under varying production scenarios. Methodologically, coupling a continuous swarm intelligence algorithm with a constraint-aware constructive decoder proved to be an adaptable and robust approach for handling complex shop-floor constraints without altering the core optimization engine. Future research can extend this framework by incorporating stochastic processing and setup times through robust or fuzzy optimization, developing hybrid metaheuristic variants, and addressing multi-objective criteria such as energy efficiency and carbon emissions.

Keywords

Flow Shop Scheduling

Particle Swarm Optimization PSO

Metaheuristic Algorithms

Subjects

Industrial management

1. Allahverdi, A., Gupta, J. N., & Aldowaisan, T. (1999). A review of scheduling research involving setup considerations. Omega, 27(2), 219–239. https://doi.org/10.1016/S0305-0483(98)00042-5

2. Costa, A., Cappadonna, F. A., & Fichera, S. (2014). Joint optimization of a flow-shop group scheduling with sequence-dependent set-up times and skilled workforce assignment. International Journal of Production Research, 52(9), 2696–2728. https://doi.org/10.1080/00207543.2013.867088

3. Costa, A., Fernandez-Viagas, V., & Framinan, J. M. (2020). Solving the hybrid flow shop scheduling problem with limited human resource constraint. Computers & Industrial Engineering, 146, 106545. https://doi.org/10.1016/j.cie.2020.106545

4. de Athayde Prata, B., de Abreu, L. R., & Fernandez-Viagas, V. (2025). A systematic review of permutation flow shop scheduling with due-date-related objectives. Computers & Operations Research, 106989. https://doi.org/10.1016/j.cor.2024.106989

5. Elissaouy, O., & Allali, K. (2024). Minimizing the maximum tardiness for a permutation flow shop problem under the constraint of sequence independent setup time. RAIRO-Operations Research, 58(1), 373–395. https://doi.org/10.1051/ro/2023005

6. Geng, J. C., Cui, Z., & Gu, X. S. (2016). Scatter search based particle swarm optimization algorithm for earliness/tardiness flowshop scheduling with uncertainty. International Journal of Automation and Computing, 13(3), 285–295. https://doi.org/10.1007/s11633-015-0938-3

7. Geurtsen, M., Adan, J., & Akçay, A. (2023). Integrated maintenance and production scheduling for unrelated parallel machines with setup times. Flexible Services and Manufacturing Journal. https://doi.org/10.1007/s10696-023-09483-2

8. Han, J. H., & Lee, J. Y. (2023). Scheduling for a flow shop with waiting time constraints and missing operations in semiconductor manufacturing. Engineering Optimization, 55(10), 1742–1759. https://doi.org/10.1080/0305215X.2022.2106754

9. Hayat, I., Tariq, A., Shahzad, W., Masud, M., Ahmed, S., Ali, M. U., & Zafar, A. (2023). Hybridization of particle swarm optimization with variable neighborhood search and simulated annealing for improved handling of the permutation flow-shop scheduling problem. Systems, 11(5), 221. https://doi.org/10.3390/systems11050221

10. Kress, D., Müller, D., & Nossack, J. (2019). A worker constrained flexible job shop scheduling problem with sequence-dependent setup times. OR Spectrum, 41(1), 179–217. https://doi.org/10.1007/s00291-018-0537-7

11. Mlekusch, J., & Hartl, R. F. (2025). The dual-resource-constrained re-entrant flexible flow shop: A constraint programming approach and a hybrid genetic algorithm. International Journal of Production Research, 63(5), 1803–1824. https://doi.org/10.1080/00207543.2024.2301123

12. Mousavi, S. M., & Shahnazari-Shahrezaei, P. (2023). Minimizing the makespan and total tardiness in hybrid flow shop scheduling with sequence-dependent setup times. Management and Production Engineering Review, 14(1), 13–24. https://doi.org/10.24425/mper.2023.146035

13. Mraihi, T., Driss, O. B., & El-Haouzi, H. B. (2024). Distributed permutation flow shop scheduling problem with worker flexibility: Review, trends and model proposition. Expert Systems with Applications, 238, 121947. https://doi.org/10.1016/j.eswa.2023.121947

14. Ouchiekh, R., Fri, M., Touil, A., & Echchatbi, A. (2021). Total weighted tardiness in the permutation flow shop under uncertainty. IFAC-PapersOnLine, 54(1), 1174–1180. https://doi.org/10.1016/j.ifacol.2021.08.139

15. Pinedo, M. (2022). Scheduling: Theory, algorithms, and systems (6th ed.). Springer. https://doi.org/10.1007/978-3-030-87000-8

16. Rahman, H. F., Janardhanan, M. N., Chuen, L. P., & Ponnambalam, S. G. (2021). Flowshop scheduling with sequence-dependent setup times and batch delivery in supply chain. Computers & Industrial Engineering, 158, 107378. https://doi.org/10.1016/j.cie.2021.107378

17. Silva, A. F., Valente, J. M., & Schaller, J. E. (2022). Metaheuristics for the permutation flowshop problem with a weighted quadratic tardiness objective. Computers & Operations Research, 140, 105691. https://doi.org/10.1016/j.cor.2021.105691

18. Utama, D. M., Umamy, S. Z., & Al-Imron, C. N. (2024). No-wait flow shop scheduling problem: A systematic literature review and bibliometric analysis. RAIRO-Operations Research, 58(2), 1281–1313. https://doi.org/10.1051/ro/2024008

19. Ying, K. C., Pourhejazy, P., & Lin, Z. R. (2025). Scheduling with sequence-dependent setup times in short-term production planning: A main path analysis-based review. Operations Research Perspectives, 100340. https://doi.org/10.1016/j.orp.2024.100340

1. Behnamian, J., & Afsar, A. (2010). Optimization of the sum of lateness and energy penalties in the scheduling problem of heterogeneous parallel machines using memetic algorithms. Industrial Management Studies, 18(58), 29–57. https://doi.org/10.22054/jims.2020.24828.1856 [In Persian]

2. Dabiri, M. R., Yazdani, M., Naderi, B., & Haleh, H. (1400). Mathematical model and meta-heuristic algorithm for the hybrid shop flow scheduling problem with dual limited resources and considering job backlogs. Industrial Management Studies, 19(60), 237–284. https://doi.org/10.22054/jims.2021.48976.2425 [In Persian]

3. Mosayeb Motlagh, M., Azimi, P., & Amiri, M. (1402). Optimization of multi-product production lines with a simulation and multi-objective programming approach. Industrial Management Studies, 21(68), 75–120. https://doi.org/10.22054/jims.2019.30723.2015 [In Persian]

4. Yazdani, M. (2019). Metaheuristic algorithms for the scheduling problem of two-stage assembly shop flow considering machine setup times. Industrial Management Studies, 18(58), 307–335. https://doi.org/10.22054/jims.2020.47551.2394 [In Persian]