Local search methods for the cumulative flow shop scheduling problem
Loading...
Files
Published Version
Appendix A. Supplementary Data
Date
2026-07-01
Authors
Missaoui, Ahmed
Neufeld, Janis S.
O’Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier Ltd
Published Version
Abstract
Scheduling problems are typically studied under the assumption that each resource can process only one job at a time. However, in many real-world settings, resources are capable of processing multiple jobs simultaneously, leading to cumulative scheduling problems, where each resource can process several jobs up to a specified capacity. While cumulative scheduling has been investigated in job shops and parallel-machine contexts, it remains unexplored in flow shop environments. In this work, we introduce the cumulative flow shop scheduling problem as a generalization of the classical flow shop. We propose a mixed-integer programming formulation along with two metaheuristic approaches – an iterated local search algorithm and an iterated greedy algorithm – designed to minimize total flow time. Both methods incorporate problem-specific features, such as an adapted initial solution and a rescheduling mechanism to improve resource utilization. With this, they demonstrate strong performance in a comprehensive computational study. Additionally, we analyze trade-offs between total flow time and resource utilization, and investigate how varying job sizes and resource capacities affect outcomes. Our findings provide actionable managerial insights and open new avenues for research on cumulative scheduling problems.
Description
Keywords
Cumulative scheduling , Flow shop scheduling , Machine capacity , Metaheuristics , Multiple objectives , [ComputerScience]
Citation
Missaoui, A, Neufeld, J S & O’Sullivan, B 2026, 'Local search methods for the cumulative flow shop scheduling problem', Operations Research Perspectives, vol. 17, 100403, pp. 1-16. https://doi.org/10.1016/j.orp.2026.100403