New Valid Inequalities for a Multi-echelon Multi-item Lot-Sizing Problem with Returns and Lost Sales

Franco Quezada, Céline Gicquel, Safia Kedad-SidhoumICCL 2021 · DOI

TL;DR

This paper introduces a new set of mathematical inequalities to improve the efficiency of planning production for complex remanufacturing systems that handle multiple product types, production stages, and account for lost sales. By incorporating these novel inequalities into a specialized algorithm, the authors demonstrate significant improvements in solving these challenging optimization problems compared to existing methods.

What Problem Does This Paper Address?

In today's industrial landscape, companies face increasing pressure to adopt sustainable practices. Remanufacturing, the process of transforming used products into like-new ones, is a key strategy for reducing waste and conserving resources. However, planning production for remanufacturing systems is complex. These systems often involve multiple stages (disassembly, refurbishment, reassembly), handle various product types, and must contend with fluctuating customer demand and the availability of used products. Furthermore, if demand cannot be met due to insufficient supply or quality of returned items, companies incur penalties for lost sales.

Existing mathematical models for these systems, while powerful, can become computationally intractable for larger or more complex scenarios. This is often due to the inherent difficulty in finding optimal solutions for multi-echelon lot-sizing problems. The authors identify a specific gap: previous approaches for remanufacturing lot-sizing often simplified the problem by assuming uncapacitated production or by not fully accounting for the constraints imposed by the limited availability of returned products at each stage. This paper aims to bridge this gap by developing new mathematical tools to better represent and solve these complex remanufacturing planning problems.

Methods

The core contribution of this paper lies in the development of a new family of valid inequalities. These inequalities are designed to strengthen the mathematical formulation of the multi-echelon, multi-item lot-sizing problem with returns and lost sales. The authors build upon existing "single-echelon (k, U) inequalities" but extend them to account for the specific constraints of remanufacturing, particularly the limited availability of returned products at each production echelon.

They propose a customized branch-and-cut algorithm that incorporates these new (l, k, U) inequalities. This algorithm works by iteratively refining a lower bound on the optimal solution. At each step, it solves a linear relaxation of the problem and, if violated, adds one of the new inequalities to the model. This process is repeated until an optimal solution is found or a time limit is reached. The authors also demonstrate that their proposed inequalities are at least as strong as previously known ones, meaning they provide tighter bounds and potentially lead to faster convergence.

Datasets

The authors generated two sets of instances for their computational experiments.

  • Set 1: T = 25 periods, I = 10 parts.
  • Set 2: T = 35 periods, I = 10 parts.

For each set, they created 480 instances by systematically varying parameters such as the setup-holding cost ratio (f/h), production-holding cost ratio (g/h), and returns-demand quantity ratio (r/d). This systematic generation ensures a comprehensive evaluation of their algorithm across a range of realistic scenarios.

Key Insights and Ideas

  • The critical role of returns availability: The paper highlights that simply assuming unlimited production capacity is insufficient for remanufacturing. The actual availability of returned products and their quality significantly constrains production, and new inequalities are needed to capture this.
  • Generalizing existing inequalities: The authors successfully generalize existing lot-sizing inequalities (k, U) to a more powerful form (l, k, U) that better reflects the multi-echelon nature and return constraints of remanufacturing.
  • Algorithmic advantage: By integrating these new inequalities into a branch-and-cut framework, the authors achieve substantial improvements in both solution quality and computational time compared to standard solvers and previous specialized algorithms.
  • Trade-offs in remanufacturing: The results suggest that the effectiveness of the new inequalities can depend on the specific problem instance, particularly the ratio of demand to returns, indicating complex interplay between different factors in remanufacturing planning.

Key Results

The proposed (l, k, U) inequalities and the associated branch-and-cut algorithm demonstrated significant performance improvements:

  • Reduced Computation Time: The customized branch-and-cut algorithm using (l, k, U) inequalities reduced computation time by an average of 26% compared to the generic CPLEX solver.
  • Improved Solution Quality: The algorithm achieved a smaller MIP gap (the difference between the best lower bound and the best feasible solution found) on average, indicating better solution quality. For instance, in Set 1, the average MIP gap was reduced from 0.06% (CPX) to 0.03% ((l, k, U)).
  • Outperformance of Previous Methods: The new algorithm consistently outperformed both the generic CPLEX solver and a previously published branch-and-cut algorithm that used less general (k, U) inequalities.
  • Instance-Specific Performance: The benefits of the (l, k, U) inequalities were most pronounced when the demand-to-returns ratio was low (r/d = 1 or 2), suggesting their particular relevance in scenarios where returns are a more significant bottleneck.

Limitations and Future Work

  • Heuristic Separation: The paper acknowledges that an exact separation algorithm for the (l, k, U) inequalities was not implemented, and a heuristic approach was used. Developing an exact separation algorithm could further enhance performance.
  • Capacitated Lot-Sizing: The current work focuses on uncapacitated production. Extending the proposed inequalities to capacitated lot-sizing problems, which are more realistic, is a promising avenue.
  • Other Complicating Features: The authors suggest exploring the applicability of these inequalities to lot-sizing problems with additional complexities like backlogging, safety stocks, or minimum production levels.
  • Stochastic Version: The paper mentions that the current study focuses on the deterministic variant of the problem. Extending the inequalities and algorithms to handle the stochastic version (where parameters are uncertain) is a significant future research direction.
  • Instance Size: While improvements were shown, the paper notes that further computational experiments are needed to assess the scalability to even larger instances.

Summary updated

BibTeX
@inproceedings{quezada2021new,
  author = {Franco Quezada and Céline Gicquel and Safia Kedad-Sidhoum},
  title = {{New Valid Inequalities for a Multi-echelon Multi-item Lot-Sizing Problem with Returns and Lost Sales}},
  booktitle = {ICCL},
  year = {2021},
  doi = {10.1007/978-3-030-87672-2\_13},
}
Figure