Single machine multi-product capacitated lot sizing with sequence-dependent setups

Bernardo Almada‐Lobo, Diego Klabjan, Maria Antónia Carravilla, José Fernando OliveiraInternational Journal of Production Research 2007 · DOI

TL;DR

This paper tackles the complex problem of production planning in industries like glass manufacturing, where switching between products incurs significant time and cost that depend on the specific products being switched. The authors introduce two novel mathematical models to optimize this process, including a more efficient one that can handle a large number of constraints, and a practical heuristic to find good solutions quickly.

What Problem Does This Paper Address?

The core challenge addressed is the "capacitated lot-sizing problem" (CLSP) with an added layer of complexity: "sequence-dependent setup times and costs." In many manufacturing settings, especially those with continuous production lines that need to be reconfigured for different products (like glass containers), the time and cost to switch from producing product A to product B are not constant. They depend on whether you're switching from A to B, or B to A, and can be substantial. Furthermore, in the glass industry, this setup process can even involve discarding material, leading to energy waste.

A key aspect is "setup carryover," where a setup initiated at the end of one production period can carry over to the beginning of the next, potentially saving time and cost. Existing CLSP models often simplify these aspects, either by assuming constant setup times or by not fully accounting for setup carryover. This paper aims to provide more accurate and efficient models for this realistic scenario, particularly for single-machine environments.

Methods

The paper introduces two novel mixed-integer linear programming (MILP) formulations for the single-machine, multi-product capacitated lot-sizing problem with sequence-dependent setups and setup carryover.

  • Formulation F₁ (Compact): This formulation uses a polynomial number of constraints. It's designed to be more straightforward but potentially less "tight" in its linear programming relaxation.
  • Formulation F₂ (Stronger): This formulation uses an exponential number of constraints, making it impractical to solve directly. However, it offers a stronger linear programming relaxation, meaning its solution is closer to the true optimal integer solution. The authors provide a polynomial-time separation algorithm to generate these constraints as needed, making the model solvable in practice.

Additionally, the paper proposes a five-step heuristic to find good feasible solutions for large-scale problems where exact methods might be too slow. This heuristic focuses on:

  1. Initial lot-for-lot loading.
  2. Sequencing and capacity adjustment (eliminating overtime).
  3. Reducing setup costs by anticipating productions.
  4. Reducing holding costs by postponing productions.
  5. Improving adjacent period links by eliminating empty setups.

Datasets

The paper does not introduce new datasets. Instead, it uses an instance generator described in Section 2.1.1, which is based on parameters from Haase and Kimms [2000]. This generator creates random instances with varying numbers of products (N), periods (T), and capacity utilization levels (Cut), and a parameter θ that relates setup costs to setup times. The authors compare their models and heuristic against existing benchmarks using these generated instances.

Key Insights and Ideas

  • Setup Carryover is Crucial: The paper highlights that accurately modeling setup carryover is essential for realistic production planning, especially in industries with long setup times, as it can significantly impact efficiency and capacity utilization.
  • Trade-off Between Formulation Strength and Complexity: The authors demonstrate a clear trade-off. Formulation F₂ is mathematically stronger (leading to better lower bounds for the LP relaxation) but has an exponential number of constraints. F₁ is more compact but less strong. The development of a separation algorithm for F₂ bridges this gap, allowing for the benefits of a strong formulation without the prohibitive constraint count.
  • Heuristic Effectiveness for Tight Capacities: The proposed five-step heuristic is shown to be effective not only in finding good quality solutions but also in generating feasible solutions, even for highly constrained scenarios where finding any solution is difficult. This is attributed to the flexibility of its capacity-adjustment steps.
  • Improved Performance Over Existing Models: The paper provides strong evidence that their proposed formulations and heuristic outperform existing methods, particularly in terms of computational efficiency and solution quality (lower integrality gaps).

Key Results

  • Formulation Strength: Theorem 1 proves that formulation F₂ is at least as strong as F₁ in terms of their linear programming relaxations. Computational experiments (Figure 5) confirm that F₂LP (with added valid inequalities) provides significantly better lower bounds than F₁LP.
  • Computational Efficiency: Formulation F₁ is shown to be more efficient than the Gupta and Magnusson [2005] model, with performance improving as the number of periods increases (Figure 4).
  • Valid Inequalities Impact: The addition of (l, S) and (Wt) valid inequalities significantly strengthens the F₂ formulation, reducing the integrality gap. The impact of these cuts is more pronounced with a larger number of periods.
  • Heuristic Performance: The heuristic consistently finds feasible solutions and produces results with a relatively small gap (average gap around 6-15% for relevant parameters) between the lower bound and the heuristic's upper bound. The heuristic's running times are very fast (under 0.4 seconds).

Limitations and Future Work

  • Single Machine Focus: The presented models are for a single machine. The authors mention that extending the model to multiple machines is straightforward but not explored in this paper.
  • Deterministic Demand: The models assume deterministic demand. Future work could incorporate stochastic demand.
  • Heuristic Improvements: While the heuristic is effective, there's always room for improvement. The paper suggests that its simplicity makes it a good candidate for integration into more complex heuristics or metaheuristics.
  • Polyhedral Structure: The authors suggest further research into exploiting the polyhedral structure of the problem to develop even stronger valid inequalities.
  • Comparison with Other Heuristics: While the heuristic is compared to lower bounds, a more extensive comparison with other state-of-the-art heuristics for similar problems could be beneficial.

Summary updated

Abstract

In production planning in the glass container industry, machine-dependent setup times and costs are incurred for switch overs from one product to another. The resulting multi-item capacitated lot-sizing problem has sequence-dependent setup times and costs. We present two novel linear mixed-integer programming formulations for this problem, incorporating all the necessary features of setup carryovers. The compact formulation has polynomially many constraints, whereas the stronger formulation uses an exponential number of constraints that can be separated in polynomial time. We also present a five-step heuristic that is effective both in finding a feasible solution (even for tightly capacitated instances) and in producing good solutions to these problems. We report computational experiments.
BibTeX
@article{almadalobo2007single,
  author = {Bernardo Almada‐Lobo and Diego Klabjan and Maria Antónia Carravilla and José Fernando Oliveira},
  title = {{Single machine multi-product capacitated lot sizing with sequence-dependent setups}},
  journal = {International Journal of Production Research},
  year = {2007},
  doi = {10.1080/00207540601094465},
}
Figure