Multilevel Lot Sizing with Setup Times and Multiple Constrained Resources: Internally Rolling Schedules with Lot-Sizing Windows

TLDR

The paper proposes a time‑oriented decomposition heuristic to solve dynamic multi‑item multilevel lot‑sizing problems with constrained resources and setup times. The heuristic decomposes the problem into sequential submodels over rolling windows, each formulated as a mixed‑integer linear program using a Simple Plant Location representation and solved with standard MIP solvers while considering capacities over the full horizon. Computational experiments demonstrate that the heuristic yields higher solution quality than a well‑known special‑purpose heuristic.

Abstract

In this paper a new time-oriented decomposition heuristic is proposed to solve the dynamic multi-item multilevel lot-sizing problem in general product structures with single and multiple constrained resources as well as setup times. While lot-sizing decisions are made sequentially within an internally rolling planning interval (or lot-sizing window), capacities are always considered over the entire planning horizon. For each submodel a model formulation based on the “Simple Plant Location” representation is developed. These mixed-integer linear submodels are solved by standard mathematical programming software even for relatively large test instances. Extensive computational tests show that the heuristic proposed provides a better solution quality than a well-known special purpose heuristic.