Multilevel Lot-Sizing with Inventory Bounds
Hark-Chin Hwang, Wilco van den Heuvel, Albert P. M. Wagelmans
INFORMS Journal on Computing · 2023 · Volume 35 · Issue 6
Abstract
We consider a single-item multilevel lot-sizing problem with a serial structure where one of the levels has an inventory capacity (the bottleneck level). We propose a novel dynamic programming algorithm combining Zangwill’s approach for the uncapacitated problem and the basis-path approach for the production capacitated problem. Under reasonable assumptions on the cost parameters the time complexity of the algorithm is 𝒪 ( 𝐿 𝑇 6 ) O ( L T 6 ) with L the number of levels in the supply chain and T the length of the planning horizon. Computational tests show that our algorithm is significantly faster than the commercial solver C plex applied to a standard formulation and can solve reasonably sized instances up to 48 periods and 12 levels in a few minutes. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the National Research Foundation of Korea (NRF) funded by the Ministry of Education [Grant 2014R1A1A2058513].
Keywords
inventory bound, multilevel lot-sizing, dynamic programming, inventory-production: deterministic
Enable JavaScript for citation tools and additional paper interactions.