A multistage stochastic capacitated discrete procurement problem with lead times, cancellation and postponement is addressed. The problem determines the procurement of a product under uncertain demand at minimal expected cost during a time horizon. The supply of the product is made through the purchase of optional distinguishable orders of fixed size with delivery time. Due to the unveiling of uncertainty over time it is possible to make cancellation and postponement corrective decisions on order procurement. These decisions involve costs and times of implementation. A model of the problem is formulated as an extension of a discrete capacitated lot-sizing problem under uncertain demand and lead times through a multi-stage stochastic mixed-integer linear optimization approach. Valid inequalities are generated, based on a conventional inequalities approach, to tighten the model formulation. Experiments are performed for several problem instances with different uncertainty information structure. Their results allow to conclude that the incorporation of a subset of the generated inequalities favor the model solution.
Keywords: Stochastic lot-sizing, multi-stage stochastic mixed-integer optimization, valid inequalities, cancellation, postponement
@article{RO_2021__55_2_861_0,
author = {Testuri, Carlos E. and Cancela, H\'ector and Albornoz, V{\'\i}ctor M.},
title = {A multistage stochastic lot-sizing problem with cancellation and postponement under uncertain demands},
journal = {RAIRO. Operations Research},
pages = {861--872},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {2},
doi = {10.1051/ro/2021042},
mrnumber = {4254331},
zbl = {1468.90024},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021042/}
}
TY - JOUR AU - Testuri, Carlos E. AU - Cancela, Héctor AU - Albornoz, Víctor M. TI - A multistage stochastic lot-sizing problem with cancellation and postponement under uncertain demands JO - RAIRO. Operations Research PY - 2021 SP - 861 EP - 872 VL - 55 IS - 2 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021042/ DO - 10.1051/ro/2021042 LA - en ID - RO_2021__55_2_861_0 ER -
%0 Journal Article %A Testuri, Carlos E. %A Cancela, Héctor %A Albornoz, Víctor M. %T A multistage stochastic lot-sizing problem with cancellation and postponement under uncertain demands %J RAIRO. Operations Research %D 2021 %P 861-872 %V 55 %N 2 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021042/ %R 10.1051/ro/2021042 %G en %F RO_2021__55_2_861_0
Testuri, Carlos E.; Cancela, Héctor; Albornoz, Víctor M. A multistage stochastic lot-sizing problem with cancellation and postponement under uncertain demands. RAIRO. Operations Research, Tome 55 (2021) no. 2, pp. 861-872. doi: 10.1051/ro/2021042
[1] and , MIP-based heuristics for multi-item capacitated lot-sizing problem with setup times and shortage costs. RAIRO:OR 41 (2007) 171–192. | MR | Zbl | Numdam | DOI
[2] , and , A multi-stage stochastic integer programming approach for capacity expansion under uncertainty. J. Glob. Optim. 26 (2003) 3–24. | MR | Zbl | DOI
[3] , and , Uncapacitated lot-sizing: the convex hull of solutions, edited by and . In: Mathematical Programming at Oberwolfach II. Springer Berlin Heidelberg, Berlin, Heidelberg (1984) 32–43. | Zbl | DOI
[4] and , Introduction to Stochastic Programming, 2nd edition. In: Springer Series in Operations Research and Financial Engineering. Springer, New York (2011). | MR | Zbl | DOI
[5] and , Computational complexity of the capacitated lot size problem. Manage. Sci. 28 (1982) 1174–1186. | MR | Zbl | DOI
[6] , , and , Single item lot sizing problems. Eur. J. Oper. Res. 168 (2006) 1–16. | MR | Zbl | DOI
[7] , Multi-item capacitated lot-sizing with demand uncertainty. Int. J. Prod. Res. 44 (2006) 2997–3022. | Zbl | DOI
[8] and , Risk aversion in multistage stochastic programming: a modeling and algorithmic perspective. Eur. J. Oper. Res. 249 (2016) 188–199. | MR | Zbl | DOI
[9] , , and , Some matheuristic algorithms for multistage stochastic optimization models with endogenous uncertainty and risk management. Eur. J. Oper. Res. 285 (2020) 988–1001. | MR | Zbl | DOI
[10] , and , AMPL: A Modeling Language for Mathematical Programming. Duxbury Press (2002).
[11] , , and , A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem. Math. Program. 105 (2006) 55–84. | MR | Zbl | DOI
[12] Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual (2018).
[13] and , A heuristic algorithm for optimal location of flow-refueling capacitated stations. Int. Trans. Oper. Res. 24 (2017) 1377–1403. | MR | Zbl | DOI
[14] and , On stochastic lot-sizing problems with random lead times. Oper. Res. Lett. 36 (2008) 303–308. | MR | Zbl | DOI
[15] and , An -time algorithm for the stochastic uncapacitated lot-sizing problem with random lead times. Oper. Res. Lett. 39 (2011) 74–77. | MR | Zbl | DOI
[16] and , Plant location, set covering and economic lot size: an -algorithm for structured problems, edited by , and . In: Numerische Methoden bei Optimierungsaufgaben Band 3: Optimierung bei graphentheoretischen und ganzzahligen Problemen. Basel, Birkhäuser (1977) 155–180. | MR | Zbl | DOI
[17] , and , A dynamic lot-sizing model with demand time windows. Manage. Sci. 47 (2001) 1384–1395. | Zbl | DOI
[18] and , A polyhedral study of the static probabilistic lot-sizing problem. Ann. Oper. Res. 261 (2018) 233–254. | MR | Zbl | DOI
[19] and , Integer and Combinatorial Optimization. John Wiley & Sons, Inc. (1988). | MR | Zbl | DOI
[20] and , Improved integer programming models for simple assembly line balancing and related problems. Int. Trans. Oper. Res. 25 (2018) 1345–1359. | MR | Zbl | DOI
[21] and , Multistage stochastic integer programs: an introduction, edited by , and . In: Online Optimization of Large Scale Systems. Springer, Berlin Heidelberg (2001) 581–600. | MR | Zbl | DOI
[22] , , and , A capacitated lot sizing problem with stochastic setup times and overtime. Eur. J. Oper. Res. 273 (2019) 146–159. | MR | Zbl | DOI
[23] , and , Modelado estocástico múltiple etapa de adquisición de combustible para la generación de electricidad bajo demanda incierta. Tech. rep. INCO RT 12-07. Instituto de Computación, Facultad de Ingeniería, Universidad de la República (2012).
[24] , and , Stochastic discrete lot-sizing with lead times for fuel supply optimization. Pesqui. Oper. 39 (2019) 37–55. | DOI
[25] , and , Undominated valid inequalities for a stochastic capacitated discrete lot-sizing problem with lead times, cancellation and postponement. In: Proceedings of the 8th International Conference on Operations Research and Enterprise Systems. SCITEPRESS Digital Library (2019) 390–397. | DOI
[26] , and , Economic lot sizing: an algorithm that runs in linear time in the Wagner-Whitin case. Oper. Res. 40 (1992) S145–S156. | MR | Zbl | DOI
[27] and , Dynamic version of the economic lot size model. Manage. Sci. 5 (1958) 89–96. | MR | Zbl | DOI
[28] , Lot-sizing with production and delivery time windows. Math. Program. 107 (2006) 471–489. | MR | Zbl | DOI
[29] , and , Stochastic modeling of fuel procurement for electricity generation with contractual terms and logistics constraints. Comput. Chem. Eng. 123 (2019) 49–63. | DOI
Cité par Sources :
