A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem

M. Edib GÜRKAN, (Karabük Üniversitesi, Yönetim Bilişim Sistemleri Bölümü, Karabük, Türkiye)
Hüseyin TUNÇ (Ankara Sosyal Bilimler Üniversitesi, İşletme Bölümü, Ankara, Türkiye)
An International Journal of Optimization and Control: Theories & Applications (IJOCTA)
4 0
Yıl: 2021 Cilt: 11 Sayı: 1 Sayfa Aralığı: 41 - 51 Metin Dili: İngilizce DOI: 10.11121/ijocta.01.2021.00945 İndeks Tarihi: 15-02-2022

A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem

Öz:
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 determin istic 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 program ming 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.
Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
  • [1] Axs¨ater, S. (2015). Inventory control. Vol. 225. Springer.
  • [2] Ramya, R., Rajendran, C., Ziegler, H., Mohapatra, S., & Ganesh, K. (2019). Capacitated Lot Sizing Problems in Process Industries. Springer.
  • [3] Wagner, H. M., & Whitin, T. M. (1958). Dynamic version of the economic lot size model. Management science, 5(1), 89-96.
  • [4] Florian, M., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1980). Deterministic production planning: Algorithms and complexity. Management science, 26(7), 669-679.
  • [5] Bitran, G. R., & Yanasse, H. H. (1982). Computational complexity of the capacitated lot size problem. Management Science, 28(10), 1174-1186.
  • [6] 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.
  • [7] 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.
  • [8] Buschk¨uhl, 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.
  • [9] Brahimi, N., Absi, N., Dauz`ere-P´er`es, S., & Nordli, A. (2017). Single-item dynamic lotsizing problems: An updated survey. European Journal of Operational Research, 263(3), 838-863.
  • [10] 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.
  • [11] Bookbinder, J. H., & Tan, J. Y. (1988). Strategies for the probabilistic lot-sizing problem with service-level constraints. Management Science, 34(9), 1096-1108.
  • [12] 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.
  • [13] Tempelmeier, H., & Herpers, S. (2010). ABC β–a heuristic for dynamic capacitated lot sizing with random demand under a fill rate constraint. International Journal of Production Research, 48(17), 5181-5193.
  • [14] Helber, S., Sahling, F., & Schimmelpfeng, K. (2013). Dynamic capacitated lot sizing with random demand and dynamic safety stocks. OR Spectrum, 35(1), 75-105.
  • [15] Helber, S., & Sahling, F. (2010). A fix-andoptimize approach for the multi-level capacitated lot sizing problem. International Journal of Production Economics, 123(2), 247- 256.
  • [16] Tempelmeier, H., & Hilger, T. (2015). Linear programming models for a stochastic dynamic capacitated lot sizing problem. Computers & Operations Research, 59, 119-125.
  • [17] De Smet, N., Minner, S., Aghezzaf, E. H., & Desmet, B. (2020). A linearisation approach to the stochastic dynamic capacitated lotsizing problem with sequence-dependent changeovers. International Journal of Production Research, 58(16), 4980-5005.
  • [18] 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.
  • [19] Hilger, T., Sahling, F., & Tempelmeier, H. (2016). Capacitated dynamic production and remanufacturing planning under demand and return uncertainty. OR Spectrum, 38(4), 849- 876.
  • [20] Koca, E., Yaman, H., & Akt¨urk, M. S. (2015). Stochastic lot sizing problem with controllable processing times. Omega, 53, 1- 10.
  • [21] Liu, K., & Zhang, Z. H. (2018). Capacitated disassembly scheduling under stochastic yield and demand. European Journal of Operational Research, 269(1), 244-257.
  • [22] Pauls-Worm, K. G., Hendrix, E. M., Alcoba, A. G., & Haijema, R. (2016). Order quantities for perishable inventory control with nonstationary demand and a fill rate constraint. International Journal of Production Economics, 181, 238-246.
  • [23] Tunc, H (2019). The capacitated stochastic lot sizing problem with convex processing time compression cost. Working paper.
  • [24] 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.
  • [25] 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.
  • [26] 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.
  • [27] 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.
  • [28] Tavaghof-Gigloo, D., & Minner, S. (2020). Planning approaches for stochastic capacitated lot-sizing with service level constraints. International Journal of Production Research.
  • [29] Tunc, H., Kilic, O. A., Tarim, S. A., & Eksioglu, B. (2014). A reformulation for the stochastic lot sizing problem with servicelevel constraints. Operations Research Letters, 42(2), 161-165.
  • [30] Porteus, E. L. (2002). Foundations of stochastic inventory theory. Stanford University Press.
  • [31] Silver, E. A., Pyke, D. F., & Peterson, R. (1998). Inventory management and production planning and scheduling. Vol. 3. New York: Wiley.
  • [32] Tarim, S. A., & Kingsman, B. G. (2006). Modelling and computing (Rn, Sn) policies for inventory systems with non-stationary stochastic demand. European Journal of Operational Research, 174(1), 581-599.
  • [33] 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.
  • [34] 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.
  • [35] 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.
  • [36] Gavrilovi´c, M. M. (1975). Optimal approximation of convex curves by functions which are piecewise linear. Journal of Mathematical Analysis and Applications, 52(2), 260-282.
  • [37] 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.
  • [38] Sahling, F., Buschk¨uhl, L., Tempelmeier, H., & Helber, S. (2009). Solving a multi-level capacitated lot sizing problem with multiperiod setup carry-over via a fix-and-optimize heuristic. Computers & Operations Research, 36(9), 2546-2553.
  • [39] Pochet, Y., & Wolsey, L. A. (2006). Production planning by mixed integer programming. Springer Science & Business Media.
APA GURKAN M, Tunc H (2021). A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem. , 41 - 51. 10.11121/ijocta.01.2021.00945
Chicago GURKAN M. Edib,Tunc Huseyin A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem. (2021): 41 - 51. 10.11121/ijocta.01.2021.00945
MLA GURKAN M. Edib,Tunc Huseyin A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem. , 2021, ss.41 - 51. 10.11121/ijocta.01.2021.00945
AMA GURKAN M,Tunc H A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem. . 2021; 41 - 51. 10.11121/ijocta.01.2021.00945
Vancouver GURKAN M,Tunc H A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem. . 2021; 41 - 51. 10.11121/ijocta.01.2021.00945
IEEE GURKAN M,Tunc H "A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem." , ss.41 - 51, 2021. 10.11121/ijocta.01.2021.00945
ISNAD GURKAN, M. Edib - Tunc, Huseyin. "A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem". (2021), 41-51. https://doi.org/10.11121/ijocta.01.2021.00945
APA GURKAN M, Tunc H (2021). A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 11(1), 41 - 51. 10.11121/ijocta.01.2021.00945
Chicago GURKAN M. Edib,Tunc Huseyin A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA) 11, no.1 (2021): 41 - 51. 10.11121/ijocta.01.2021.00945
MLA GURKAN M. Edib,Tunc Huseyin A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), vol.11, no.1, 2021, ss.41 - 51. 10.11121/ijocta.01.2021.00945
AMA GURKAN M,Tunc H A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA). 2021; 11(1): 41 - 51. 10.11121/ijocta.01.2021.00945
Vancouver GURKAN M,Tunc H A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA). 2021; 11(1): 41 - 51. 10.11121/ijocta.01.2021.00945
IEEE GURKAN M,Tunc H "A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem." An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 11, ss.41 - 51, 2021. 10.11121/ijocta.01.2021.00945
ISNAD GURKAN, M. Edib - Tunc, Huseyin. "A fix-and-optimize heuristic for the capacitated multi-item stochastic lot-sizing problem". An International Journal of Optimization and Control: Theories & Applications (IJOCTA) 11/1 (2021), 41-51. https://doi.org/10.11121/ijocta.01.2021.00945
Sayfa Oluşturulma Tarihi
23-04-2024 21:33

İLETİŞİM

TÜBİTAK ULAKBİM TR Dizin

Yüzüncüyıl, İşçi Blokları Mahallesi

Muhsin Yazıcıoğlu Caddesi No:51/C

06530 Çankaya / ANKARA +90 (312) 298 92 00

trdizin@tubitak.gov.tr

TÜBİTAK ULAKBİM Ulusal Akademik Ağ ve Bilgi Merkezi Cahit Arf Bilgi Merkezi © Tüm Hakları Saklıdır. Gizlilik Politikası Kullanım Şartları