A mixed integer programming formulation for the stochastic lot sizing problem with controllable processing times. (English) Zbl 1510.90020
Summary: In this study, we address the capacitated stochastic lot-sizing problem under \(\alpha\) service level constraints. We assume that processing times can be decreased in return for compression cost that follows a convex function. We consider this problem under the static uncertainty strategy suggesting to determine replenishment plans at the beginning of the planning horizon. We develop an extended mixed integer programming (MIP) formulation built on a predefined piecewise linear approximation. Then, we adopt the so-called dynamic cut generation approach to be able to use the proposed MIP formulation with no prior approximation of the cost function. Also, we demonstrate how to extend the dynamic cut generation approach to consider the exact inventory cost in the objective function. We show the computational performance of the proposed MIP model with the dynamic cut generation approach in an extensive numerical study where second order cone programming formulations developed in the literature are used as benchmark. The results reveal that the proposed MIP model deployed with the dynamic cut generation yields a superior computational performance as compared to the benchmark formulations especially when the order of compression cost function is higher.
MSC:
| 90B05 | Inventory, storage, reservoirs |
| 90B30 | Production models |
| 90C11 | Mixed integer programming |
| 90C15 | Stochastic programming |
References:
| [1] | Ahmed, S.; King, A. J.; Parija, G., A multi-stage stochastic integer programming approach for capacity expansion under uncertainty, J. Global Optim., 26, 3-24 (2003) · Zbl 1116.90382 |
| [2] | Akhoondi, F.; Lotfi, M., A heuristic algorithm for master production scheduling problem with controllable processing times and scenario-based demands, Int. J. Prod. Res., 54, 3659-3676 (2016) |
| [3] | Akturk, M. S.; Atamturk, A.; Gurel, S., A strong conic quadratic reformulation for machine-job assignment with controllable processing times, Oper. Res. Lett., 37, 187-191 (2009) · Zbl 1167.90518 |
| [4] | Ali, S. A.S.; Doostmohammadi, M.; Akartunalí, K.; van der Meer, R., A theoretical and computational analysis of lot-sizing in remanufacturing with separate setups, Int. J. Prod. Econ., 203, 276-285 (2018) |
| [5] | Askin, R. G., A procedure for production lot sizing with probabilistic dynamic demand, IIE Trans., 13, 132-137 (1981) |
| [6] | Atamtürk, A.; Hochbaum, D. S., Capacity acquisition, subcontracting, and lot sizing, Manage. Sci., 47, 1081-1100 (2001) · Zbl 1232.90008 |
| [7] | Axsäter, S., Inventory control,, vol. 90 (2007), Springer Science & Business Media |
| [8] | Bookbinder, J. H.; Tan, J. Y., Strategies for the probabilistic lot-sizing problem with service-level constraints, Manage. Sci., 34, 1096-1108 (1988) · Zbl 0649.90039 |
| [9] | Chen, F. Y.; Krass, D., Inventory models with minimal service level constraints, Eur. J. Oper. Res., 134, 120-140 (2001) · Zbl 0990.90002 |
| [10] | Chen, J. J.; Kao, M. J.; Lee, D.; Rutter, I.; Wagner, D., Online dynamic power management with hard real-time guarantees, Theoret. Comput. Sci., 595, 46-64 (2015) · Zbl 1328.68036 |
| [11] | Choudhary, D.; Shankar, R., The value of VMI beyond information sharing under time-varying stochastic demand, Int. J. Prod. Res., 53, 1472-1486 (2015) |
| [12] | Choudhary, D.; Shankar, R.; Tiwari, M.; Purohit, A. K., VMI versus information sharing: an analysis under static uncertainty strategy with fill rate constraints, Int. J. Prod. Res., 54, 3978-3993 (2016) |
| [13] | Duran, M. A.; Grossmann, I. E., An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 307-339 (1986) · Zbl 0619.90052 |
| [14] | Eppen, G. D.; Martin, R. K., Solving multi-item capacitated lot-sizing problems using variable redefinition, Oper. Res., 35, 832-848 (1987) · Zbl 0639.90046 |
| [15] | Frenzen, C.; Sasao, T.; Butler, J. T., On the number of segments needed in a piecewise linear approximation, J. Comput. Appl. Math., 234, 437-446 (2010) · Zbl 1190.65024 |
| [16] | Gavrilovic, M. M., Optimal approximation of convex curves by functions which are piecewise linear, J. Math. Anal. Appl., 52, 260-282 (1975) · Zbl 0317.65005 |
| [17] | Guan, Y.; Miller, A. J., Polynomial-time algorithms for stochastic uncapacitated lot-sizing problems, Oper. Res., 56, 1172-1183 (2008) · Zbl 1167.90329 |
| [18] | He, F.; Yin, Y.; Zhou, J., Integrated pricing of roads and electricity enabled by wireless power transfer, Transp. Res. Part C: Emerg. Technol., 34, 1-15 (2013) |
| [19] | Helber, S.; Sahling, F.; Schimmelpfeng, K., Dynamic capacitated lot sizing with random demand and dynamic safety stocks, OR spectrum, 35, 75-105 (2013) · Zbl 1260.90084 |
| [20] | Hilger, T.; Sahling, F.; Tempelmeier, H., Capacitated dynamic production and remanufacturing planning under demand and return uncertainty, OR spectrum, 38, 849-876 (2016) · Zbl 1352.90004 |
| [21] | Huang, K.; Küçükyavuz, S., On stochastic lot-sizing problems with random lead times, Oper. Res. Lett., 36, 303-308 (2008) · Zbl 1152.90546 |
| [22] | Jiao, W.; Zhang, J. L.; Yan, H., The stochastic lot-sizing problem with quantity discounts, Comput. Oper. Res., 80, 1-10 (2017) · Zbl 1391.90014 |
| [23] | Karagul, H. F.; Warsing, D. P.; Hodgson, T. J.; Kapadia, M. S.; Uzsoy, R., A comparison of mixed integer programming formulations of the capacitated lot-sizing problem, Int. J. Prod. Res., 56, 7064-7084 (2018) |
| [24] | Kayan, R. K.; Akturk, M. S., A new bounding mechanism for the cnc machine scheduling problems with controllable processing times, Eur. J. Oper. Res., 167, 624-643 (2005) · Zbl 1077.90528 |
| [25] | Kilic, O. A.; Tunc, H.; Tarim, S. A., Heuristic policies for the stochastic economic lot sizing problem with remanufacturing under service level constraints, Eur. J. Oper. Res., 267, 1102-1109 (2018) · Zbl 1403.90033 |
| [26] | Koca, E.; Yaman, H.; Aktürk, M., Stochastic lot sizing problem with nervousness considerations, Comput. Oper. Res., 94, 23-37 (2018) · Zbl 1391.90016 |
| [27] | Koca, E.; Yaman, H.; Aktürk, M. S., Stochastic lot sizing problem with controllable processing times, Omega, 53, 1-10 (2015) |
| [28] | Liu, K.; Zhang, Z. H., Capacitated disassembly scheduling under stochastic yield and demand, Eur. J. Oper. Res., 269, 244-257 (2018) · Zbl 1431.90074 |
| [29] | Luss, H., Operations research and capacity expansion problems: a survey, Oper. Res., 30, 907-947 (1982) · Zbl 0491.90039 |
| [30] | Meistering, M.; Stadtler, H., Stabilized-cycle strategy for capacitated lot sizing with multiple products: Fill-rate constraints in rolling schedules, Prod. Oper. Manage., 26, 2247-2265 (2017) |
| [31] | Melo, R. A.; Ribeiro, C. C., Formulations and heuristics for the multi-item uncapacitated lot-sizing problem with inventory bounds, Int. J. Prod. Res., 55, 576-592 (2017) |
| [32] | Merzifonluoğlu, Y.; Geunes, J.; Romeijn, H. E., Integrated capacity, demand, and production planning with subcontracting and overtime options, Naval Research Logistics (NRL), 54, 433-447 (2007) · Zbl 1278.90133 |
| [33] | Pauls-Worm, K. G.; Hendrix, E. M.; Alcoba, A. G.; Haijema, R., Order quantities for perishable inventory control with non-stationary demand and a fill rate constraint, Int. J. Prod. Econ., 181, 238-246 (2016) |
| [34] | van Pelt, T. D.; Fransoo, J. C., A note on “Linear programming models for a stochastic dynamic capacitated lot sizing problem”, Comput. Oper. Res., 89, 13-16 (2018) · Zbl 1391.90038 |
| [35] | Porteus, E. L., Foundations of stochastic inventory theory (2002), Stanford University Press |
| [36] | Qi, X.; Song, D. P., Minimizing fuel emissions by optimizing vessel schedules in liner shipping with uncertain port times, Transp. Res. Part E, 48, 863-880 (2012) |
| [37] | Quezada, F.; Gicquel, C.; Kedad-Sidhoum, S.; Vu, D. Q., A multi-stage stochastic integer programming approach for a multi-echelon lot-sizing problem with returns and lost sales, Comput. Oper. Res., 116, Article 104865 pp. (2020) · Zbl 1458.90238 |
| [38] | Rajagopalan, S.; Swaminathan, J. M., A coordinated production planning model with capacity expansion and inventory management, Manage. Sci., 47, 1562-1580 (2001) · Zbl 1232.90195 |
| [39] | Randa, A. C.; Doğru, M. K.; Iyigun, C.; Özen, U., Heuristic methods for the capacitated stochastic lot-sizing problem under the static-dynamic uncertainty strategy, Comput. Oper. Res., 109, 89-101 (2019) · Zbl 1458.90034 |
| [40] | Rossi, R.; Tarim, S. A.; Prestwich, S.; Hnich, B., Piecewise linear lower and upper bounds for the standard normal first order loss function, Appl. Math. Comput., 231, 489-502 (2014) · Zbl 1410.62027 |
| [41] | Scarf, H. E., Optimality of (s, S) policies in the dynamic inventory problem, (Arrow, K.; Karlin, S.; Suppes, P., Mathematical Methods In The Social Sciences (1960), Stanford University Press: Stanford University Press Stanford, CA), 196-202 · Zbl 0203.22102 |
| [42] | Silver, E., Inventory control under a probabilistic time-varying, demand pattern, IIE Trans., 10, 371-379 (1978) |
| [43] | Sox, C. R., Dynamic lot sizing with random demand and non-stationary costs, Oper. Res. Lett., 20, 155-164 (1997) · Zbl 0879.90075 |
| [44] | Tarim, S. A.; Kingsman, B. G., The stochastic dynamic production/inventory lot-sizing problem with service-level constraints, Int. J. Prod. Econ., 88, 105-119 (2004) |
| [45] | Tarim, S. A.; Kingsman, B. G., Modelling and computing \(( R^n , S^n)\) policies for inventory systems with non-stationary stochastic demand, Eur. J. Oper. Res., 174, 581-599 (2006) · Zbl 1116.90012 |
| [46] | Tempelmeier, H., On the stochastic uncapacitated dynamic single-item lotsizing problem with service level constraints, Eur. J. Oper. Res., 181, 184-194 (2007) · Zbl 1121.90015 |
| [47] | Tempelmeier, H., A column generation heuristic for dynamic capacitated lot sizing with random demand under a fill rate constraint, Omega, 39, 627-633 (2011) |
| [48] | Tempelmeier, H., Stochastic lot sizing problems, (Handbook of Stochastic Models and Analysis of Manufacturing System Operations (2013), Springer), 313-344 |
| [49] | Tempelmeier, H.; Herpers, S., Dynamic uncapacitated lot sizing with random demand under a fillrate constraint, Eur. J. Oper. Res., 212, 497-507 (2011) |
| [50] | Tempelmeier, H.; Hilger, T., Linear programming models for a stochastic dynamic capacitated lot sizing problem, Comput. Oper. Res., 59, 119-125 (2015) · Zbl 1348.90045 |
| [51] | Tunc, H.; Kilic, O. A.; Tarim, S. A.; Eksioglu, B., A simple approach for assessing the cost of system nervousness, Int. J. Prod. Econ., 141, 619-625 (2013) |
| [52] | Tunc, H.; Kilic, O. A.; Tarim, S. A.; Eksioglu, B., The stochastic lot sizing problem with piecewise linear concave ordering costs, Comput. Oper. Res., 65, 104-110 (2016) · Zbl 1349.90049 |
| [53] | Tunc, H.; Kilic, O. A.; Tarim, S. A.; Rossi, R., An extended mixed-integer programming formulation and dynamic cut generation approach for the stochastic lot-sizing problem, INFORMS J. Comput., 30, 492-506 (2018) · Zbl 1448.90013 |
| [54] | Vargas, V., An optimal solution for the stochastic version of the wagner-whitin dynamic lot-size model, Eur. J. Oper. Res., 198, 447-451 (2009) · Zbl 1163.90352 |
| [55] | Wu, T.; Liang, Z.; Zhang, C., Analytics branching and selection for the capacitated multi-item lot sizing problem with nonidentical machines, INFORMS J. Comput., 30, 236-258 (2018) · Zbl 1446.90047 |
| [56] | Xiang, Y.; Pasricha, S., Run-time management for multicore embedded systems with energy harvesting, IEEE Trans. Very Large Scale Integr. VLSI Syst., 23, 2876-2889 (2015) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
