A graph-based algorithm for the non-stationary lot-sizing problem with penalty scheme
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912096965361664 |
|---|---|
| author | Ma, Xiyuan Rossi, Roberto Archibald, Thomas |
| author_facet | Ma, Xiyuan Rossi, Roberto Archibald, Thomas |
| contents | This paper introduces a graph-based algorithm for solving single-item, single-location inventory lot-sizing problems under non-stationary stochastic demand using the $(R_t, S_t)$ policy and a penalty cost scheme. The proposed method relaxes the original mixed-integer linear programming (MILP) 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_23480 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A graph-based algorithm for the non-stationary lot-sizing problem with penalty scheme Ma, Xiyuan Rossi, Roberto Archibald, Thomas Optimization and Control This paper introduces a graph-based algorithm for solving single-item, single-location inventory lot-sizing problems under non-stationary stochastic demand using the $(R_t, S_t)$ policy and a penalty cost scheme. The proposed method relaxes the original mixed-integer linear programming (MILP) 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. |
| title | A graph-based algorithm for the non-stationary lot-sizing problem with penalty scheme |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2410.23480 |