A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem
DOI:
https://doi.org/10.11121/ijocta.01.2021.00945Keywords:
Capacitated Lot-Sizing, Random Demand, Inventory, Mixed Integer Programming, Fix and OptimizeAbstract
This study addresses the stochastic multi-item capacitated lot-sizing problem. Here, it is assumed that all items are produced on a single production resource and unmet demands are backlogged. The literature shows that the deterministic version of this problem is NP-Hard. We consider the case where period demands are time-varying random variables. The objective is to determine the minimum expected cost production plan so as to meet stochastic period demands over the planning horizon. We extend the mixed integer programming formulation introduced in the literature to capture the problem under consideration. Further, we propose a fix-and-optimize heuristic building on an item-period oriented decomposition scheme. We then conduct a numerical study to evaluate the performance of the proposed heuristic as compared to the heuristic introduced by Tempelmeier and Hilger [16]. The results clearly show that the proposed fix-and-optimize heuristic arises as both cost-efficient and time-efficient solution approach as compared to the benchmark heuristic.
Downloads
References
Axsäter, S. (2015). Inventory control. Vol. 225. Springer.
Ramya, R., Rajendran, C., Ziegler, H., Mohapatra, S., Ganesh, K. (2019). Capacitated Lot Sizing Problems in Process Industries. Springer.
Wagner, H. M., Whitin, T. M. (1958). Dynamic version of the economic lot size model. Management science, 5(1), 89-96.
Florian, M., Lenstra, J. K., Rinnooy Kan, A. H. G. (1980). Deterministic production planning: Algorithms and complexity. Management science, 26(7), 669-679.
Bitran, G. R., Yanasse, H. H. (1982). Computational complexity of the capacitated lot size problem. Management Science, 28(10), 1174-1186.
Karimi, B., Ghomi, S. F., Wilson, J. M. (2003). The capacitated lot sizing problem: a review of models and algorithms. Omega, 31(5), 365-378.
Robinson, P., Narayanan, A., Sahin, F. (2009). Coordinated deterministic dynamic demand lot-sizing problem: A review of models and algorithms. Omega, 37(1), 3-15.
Buschkühl, L., Sahling, F., Helber, S., Tempelmeier, H. (2010). Dynamic capacitated lot-sizing problems: a classification and review of solution approaches. Or Spectrum, 32(2), 231-261.
Brahimi, N., Absi, N., Dauzère-Pérès, S., Nordli, A. (2017). Single-item dynamic lot-sizing problems: An updated survey. European Journal of Operational Research, 263(3), 838-863.
Hu, Z., Hu, G. (2016). A two-stage stochastic programming model for lot-sizing and scheduling under uncertainty. International Journal of Production Economics, 180, 198-207.
Bookbinder, J. H., Tan, J. Y. (1988). Strategies for the probabilistic lot-sizing problem with service-level constraints. Management Science, 34(9), 1096-1108.
Tempelmeier, H. (2011). A column generation heuristic for dynamic capacitated lot sizing with random demand under a fill rate constraint. Omega, 39(6), 627-633.
Tempelmeier, H., Herpers, S. (2010). ABC $beta$--a heuristic for dynamic capacitated lot sizing with random demand under a fill rate constraint. International Journal of Production Research, 48(17), 5181-5193.
Helber, S., Sahling, F., Schimmelpfeng, K. (2013). Dynamic capacitated lot sizing with random demand and dynamic safety stocks. OR Spectrum, 35(1), 75-105.
Helber, S., Sahling, F. (2010). A fix-and-optimize approach for the multi-level capacitated lot sizing problem. International Journal of Production Economics, 123(2), 247-256.
Tempelmeier, H., Hilger, T. (2015). Linear programming models for a stochastic dynamic capacitated lot sizing problem. Computers & Operations Research, 59, 119-125.
De Smet, N., Minner, S., Aghezzaf, E. H., Desmet, B. (2020). A linearisation approach to the stochastic dynamic capacitated lot sizing problem with sequence-dependent changeovers. International Journal of Production Research, 58(16), 4980-5005.
Choudhary, D., Shankar, R., Tiwari, M. K., Purohit, A. K. (2016). VMI versus information sharing: an analysis under static uncertainty strategy with fill rate constraints. International Journal of Production Research, 54(13), 3978-3993.
Hilger, T., Sahling, F., Tempelmeier, H. (2016). Capacitated dynamic production and remanufacturing planning under demand and return uncertainty. OR Spectrum, 38(4), 849-876.
Koca, E., Yaman, H., Aktürk, M. S. (2015). Stochastic lot sizing problem with controllable processing times. Omega, 53, 1-10.
Liu, K., Zhang, Z. H. (2018). Capacitated disassembly scheduling under stochastic yield and demand. European Journal of Operational Research, 269(1), 244-257.
Pauls-Worm, K. G., Hendrix, E. M., Alcoba, A. G., Haijema, R. (2016). Order quantities for perishable inventory control with non-stationary demand and a fill rate constraint. International Journal of Production Economics, 181, 238-246.
Tunc, H (2019). The capacitated stochastic lot sizing problem with convex processing time compression cost. Working paper.
Tunc, H., Kilic, O. A., Tarim, S. A., Eksioglu, B. (2013). A simple approach for assessing the cost of system nervousness. International Journal of Production Economics, 141(2), 619-625.
Li, L., Song, S., Wu, C., Wang, R. (2017). Fix-and-optimize and variable neighborhood search approaches for stochastic multi-item capacitated lot-sizing problems. Mathematical Problems in Engineering, 2017.
Liang, J., Wang, Y., Zhang, Z. H., Sun, Y. (2019). Energy efficient production planning and scheduling problem with processing technology selection. Computers & Industrial Engineering, 132, 260-270.
Meistering, M., Stadtler, H. (2017). Stabilized?Cycle Strategy for Capacitated Lot Sizing with Multiple Products: Fill?Rate Constraints in Rolling Schedules. Production and Operations Management, 26(12), 2247-2265.
Tavaghof-Gigloo, D., Minner, S. (2020). Planning approaches for stochastic capacitated lot-sizing with service level constraints. International Journal of Production Research.
Tunc, H., Kilic, O. A., Tarim, S. A., Eksioglu, B. (2014). A reformulation for the stochastic lot sizing problem with service-level constraints. Operations Research Letters, 42(2), 161-165.
Porteus, E. L. (2002). Foundations of stochastic inventory theory. Stanford University Press.
Silver, E. A., Pyke, D. F., Peterson, R. (1998). Inventory management and production planning and scheduling. Vol. 3. New York: Wiley.
Tarim, S. A., Kingsman, B. G. (2006). Modelling and computing $(R_n, S_n)$ policies for inventory systems with non-stationary stochastic demand. European Journal of Operational Research, 174(1), 581-599.
Tunc, H., Kilic, O. A., Tarim, S. A., Eksioglu, B. (2016). The stochastic lot sizing problem with piecewise linear concave ordering costs. Computers & Operations Research, 65, 104-110.
Tunc, H., Kilic, O. A., Tarim, S. A., Rossi, R. (2018). An extended mixed-integer programming formulation and dynamic cut generation approach for the stochastic lot-sizing problem. INFORMS Journal on Computing, 30(3), 492-506.
Frenzen, C. L., Sasao, T., Butler, J. T. (2010). On the number of segments needed in a piecewise linear approximation. Journal of Computational and Applied mathematics, 234(2), 437-446.
Gavrilovic, M. M. (1975). Optimal approximation of convex curves by functions which are piecewise linear. Journal of Mathematical Analysis and Applications, 52(2), 260-282.
Rossi, R., Tarim, S. A., Prestwich, S., Hnich, B. (2014). Piecewise linear lower and upper bounds for the standard normal first order loss function. Applied Mathematics and Computation, 231, 489-502.
Sahling, F., Buschkühl, L., Tempelmeier, H., Helber, S. (2009). Solving a multi-level capacitated lot sizing problem with multi-period setup carry-over via a fix-and-optimize heuristic. Computers & Operations Research, 36(9), 2546-2553.
Pochet, Y., Wolsey, L. A. (2006). Production planning by mixed integer programming. Springer Science & Business Media.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2020 Huseyin Tunc, M. Edib Gurkan
This work is licensed under a Creative Commons Attribution 4.0 International License.
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.
