TL;DR
This paper introduces two novel continuous-time mathematical models for scheduling complex batch production plants with sequence-dependent changeovers. These models offer improved performance and flexibility compared to existing methods, particularly for single-stage problems and when minimizing total earliness, providing valuable tools for optimizing industrial operations.
What Problem Does This Paper Address?
Scheduling production in batch plants is a complex optimization challenge, especially when the time it takes to switch between producing different products (changeover time) depends on the sequence of products. This "sequence-dependent changeover" adds significant complexity to planning. The authors tackle the problem of short-term scheduling for multistage, multiproduct batch plants, where each production stage might have multiple equipment units, and the order of products processed on a unit matters for the time required for cleaning and setup. Existing models often struggle with this complexity, either by oversimplifying the problem or by becoming computationally intractable. This paper aims to develop more efficient and accurate models that can handle these sequence-dependent changeovers effectively.
Methods
The core contribution of this paper is the development of two new multiple-time grid, continuous-time mixed integer linear programming (MILP) models. These models are extensions of previous work but introduce novel ways to handle sequence-dependent changeovers:
- CT4I (Four-Index Model): This model explicitly treats changeover tasks as model variables. It uses four-index binary variables to represent task execution, leading to a more versatile model that can efficiently handle various objective functions (cost, earliness, makespan). While it generates larger mathematical problems, it shows better performance in single-stage scenarios.
- CT3I (Three-Index Model): This model implicitly handles changeovers through model constraints. It uses three-index binary variables and modifies constraints to account for changeover times. This approach results in smaller models and is better suited for multistage problems, though it has some limitations in handling diverse objective functions.
Both models combine processing and changeover tasks into a single set, aiming to reduce model size and degeneracy. The paper also compares these new models against other established approaches, including continuous-time models with global precedence variables (SV), discrete-time (DT) models, and constraint programming (CP) models.
Datasets
The authors evaluated their models using 39 example problems. These problems were largely based on data from previous studies by Castro and Grossmann (2006) and Castro and Grossmann (2005). Changeover times were generated randomly, up to 60% of the average processing time for the units.
Key Insights and Ideas
- Explicit vs. Implicit Changeover Handling: The paper highlights a fundamental trade-off: explicitly modeling changeovers (CT4I) offers greater flexibility for objective functions but leads to larger models. Implicitly handling them (CT3I) results in smaller models, better for multistage problems, but with some objective function limitations.
- Multiple Time Grids are Key: The use of multiple time grids, one for each equipment unit, is crucial for efficiently handling tasks that can fit into a single time interval, a significant improvement over single time grid approaches.
- CT4I's Surprising Efficiency: Despite generating more binary variables, the CT4I model (explicit changeover handling) often outperformed its 3-index counterpart (CT3I) in single-stage problems due to tighter timing constraints and a lower integrality gap.
- Global Precedence Variables (SV) as a Strong Performer: The SV model, which doesn't rely on explicit time grids, consistently finds good solutions quickly, making it a strong contender, especially for multistage problems, though it can sometimes cut off optimal solutions.
- CP Excels in Makespan Minimization: Constraint programming (CP) models emerged as the best overall performer for makespan minimization, finding optimal solutions efficiently.
Key Results
- CT4I and CT3I: Both new models showed strong performance, particularly CT4I in single-stage problems and for total earliness minimization. CT4I was found to be slightly better than CT3I in many cases, despite its larger size.
- Comparison with Other Models:
- For total cost minimization, CT4I and CT3I were competitive, with CT4I often outperforming CT3I. The hybrid MILP/CP model was the best for single-stage problems.
- For total earliness minimization, CT4I was the best performer, solving most problems to optimality.
- For makespan minimization, the CP model was the best overall performer, followed by SV.
- Multistage Problems: As the number of stages increased, the performance of the multiple time grid models generally decreased, and feasibility became more challenging. The SV model was identified as the best approach for multistage problems overall, despite its potential to miss optimal solutions in specific cases.
Limitations and Future Work
- Multistage Performance Degradation: The authors note that the performance of their new multiple time grid models decreases with an increasing number of stages, and feasibility can be compromised.
- SV's Limitation: The global precedence sequencing (SV) model, while efficient, has a limitation where it can cut off the optimal solution in exceptional cases involving sequence-dependent changeovers.
- Future Work: The authors suggest that decomposition techniques based on the global precedence sequencing variables model could be applied for solving large-scale, real-world industrial problems, where guaranteed optimality might be less critical than finding good solutions quickly. They also plan to investigate the application of these models to industrial problems.
Summary updated