528. A graph-based algorithm for the non-stationary lot-sizing problem with penalty scheme
Invited abstract in session MA-30: Lot-sizing models, stream Advanced Lot Sizing and Inventory Strategies .
Monday, 8:30-10:00Room: Maurice Keyworth 1.05
Authors (first author is the speaker)
| 1. | Xiyuan Ma
|
| Management Science and Business Economics, Univeristy of Edinburgh Business School | |
| 2. | Roberto Rossi
|
| Business School, University of Edinburgh | |
| 3. | Thomas Archibald
|
| Business School, University of Edinburgh |
Abstract
We introduce a graph-based algorithm for solving single-item, single-location inventory lot-sizing problems under non-stationary stochastic demand using the (Rt, St) policy and a penalty cost scheme.
The proposed method relaxes the original mixed-integer linear programming model by eliminating non-negative order quantity constraints and formulating it as a shortest-path problem on a weighted directed acyclic graph. A repetitive augmentation procedure is proposed to resolve any infeasibility in the solution. This procedure consists of three stages: (1) filtration, (2) repeated augmentation by redirecting, reconnecting, and duplicating between newly introduced and existing nodes to adjust the graph and eliminate negative replenishment orders, and (3) re-optimising.
The effectiveness and computational efficiency of the proposed approach are assessed through extensive experiments on 1,620 test instances across various demand patterns and parameter settings. The results show that 195 instances required augmentation, mainly those with high penalty costs, low fixed ordering costs, large demand variability, and extended planning horizons. The efficiency of the algorithm for instances with extended planning horizon scenarios demonstrates its suitability for use in real-world scenarios.
Keywords
- Inventory
- Production and Inventory Systems
- Programming, Mixed-Integer
Status: accepted
Back to the list of papers