Local search methods for the cumulative flow shop scheduling problem

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.