Multiple item economic lot sizing problem with inventory dependent demand

Abstract

We consider a multiple item Economic Lot Sizing problem where the demands for items depend on their stock quantities. The objective is to find a production plan such that the resulting stock levels (and hence demands) maximize total profit over a finite planning horizon. The single item version of this problem has been studied in the literature, and a polynomial time algorithm has been proposed when there are no bounds on production. It has also been proven that the single item version is NP -hard even when there are constant (i.e., time-invariant) finite capacities on production. We extend this single item model by considering multiple items and production capacities. We propose a Lagrangian relaxation method to find an initial solution to the problem. This solution is a hybrid solution obtained by combining two distinct solutions generated in the process of solving the Lagrangian dual problem. Starting with this initial solution, we then implement a Tabu Search algorithm to find better solutions. The performance of the proposed solution method is compared with the performance of a standard commercial software that works on a mixed integer programming formulation of the problem. We show that our solution approach finds better solutions within a predetermined time limit in general.

Keywords

Economic lot-sizing / Inventory dependent demand / Lagrangian relaxation / Tabu search algorithm

Funding

The work was supported by the Scientific and National Research Council of Turkey (TÜBİTAK) under grant no. 119M278.

Declaration of competing interest

The authors declare that they have no conflict of interest regarding the publication of this article.

References

[1] Koschat M A. Store inventory can affect demand: Empirical evidence from magazine retailing. J Retail. 2008; 84(2):165-179.

[2] Chuang C-H, Zhao Y. Demand stimulation in finished-goods inventory management: Empirical evidence from general motors dealerships. Int J Prod Econ. 2019;208:208-220.

[3] Balakrishnan A, Pangburn M S, Stavrulaki E. Stack them high, let ‘em fly: Lot-sizing policies when inventories stimulate demand. Manag Sci. 2004; 50(5):630-644.

[4] Önal M, Albey E. Economic lot sizing problem with inventory dependent demand. Optim Lett. 2020;14:2087-2106.

[5] Kunreuther H, Richard J F. Optimal pricing and inventory decisions for non-seasonal items. Econometrica. 1971;39:173-175.

[6] Rosenberg D. Optimal price-inventory decisions: Profit vs. roii. IIE txn. 1991; 21(1):17-22.

[7] Burwell T H, Dave D S, Fitzpatrick K E, Roy M R. An inventory model with planned shortage and price dependent demand. Decision Sciences, 1991; 22(5):1187-1191.

[8] Kumari M, De P K. An eoq model for deteriorating items analyzing retailer’s optimal strategy under trade credit and return policy with non-linear demand and resalable returns. An International Journal of Optimization and Control: Theories and Applications. 2022; 2(1):73-82.

[9] Urban T L. Inventory models with the demand rate dependent on stock and shortage levels. Int J Prod Econ. 1995; 40(1):21-28.

[10] Soni H, Shah N H. Optimal ordering policy for stock-dependent demandunder progressive payment scheme. European Journal of Operational Research. 2008;185:91-100.

[11] Pando V, San-José L A, García-Laguna J, Sicilia J. An economic lot-size model with non-linear holding cost hinging on time and quantity. International Journal of Production Economics. 2013; 145(1):294-303.

[12] Giri B C, Pal S, Chaudhuri K S. An inventory model for deteriorating items with stock-dependent demand rate. Eur J Oper Res. 1996;95:604-610.

[13] Teng J-T, Krommyda I-P, Skouri K, Lou K-R. A comprehensive extension of optimal ordering policy for stock-dependent demand under progressive payment scheme. Eur J Oper Res. 2011;215:97-104.

[14] Pervin M, Roy S K, Weber G W. Multi-item deteriorating two-echelon inventory model with price- and stock-dependent demand: A trade-credit policy. J Ind Manag Optim. 2019;15:1345-1373.

[15] Zhang S, Cao L, Lu Z. An eoq inventory model for deteriorating items with controllable deterioration rate under stock-dependent demand rate and non-linear holding cost. J Ind Manag Optim. 2022;18:4231-4263.

[16] Urban T L., Baker R C. Optimal ordering and pricing policies in a single-period environment with multivariate demand and markdowns. Eur J Oper Res. 1997;103:573-583.

[17] Datta T K, Paul K. An inventory system with stock dependent, price sensitive demand rates. Prod Plan Cont. 2001;12:13-20.

[18] Teng, J T, Chang C. Economic production quantity models for deteriorating items with price- and stock-dependent demand. Computers and Operations Research. 2005;32:297-308.

[19] Lu L, Zhang J, Tang W. Optimal dynamic pricing and replenishment policy for perishable items with inventory-level-dependent demand. Int J Syst Sci. 2016; 47(6):1480-1494.

[20] Hsieh T-P, Dye C-Y. Optimal dynamic pricing for deteriorating items with reference price effects when inventories stimulate demand. Eur J Oper Res. 2017; 262(1):136-150.

[21] Tiwari S, Jaggi C K, Bhunia A K, Shaikh A A, Goh M. Two-warehouse inventory model for non-instantaneous deteriorating items with stock-dependent demand and inflation using particle swarm optimization. Ann Oper Res. 2017;254:401-423.

[22] Pervin M, Roy S K, Weber G W. Deteriorating inventory with preservation technology under price- and stock-sensitive demand. J Ind Manag Optim. 2020;16:1585-1612.

[23] Feng L, Chan Y-L, Cárdenas-Barrón L E. Pricing and lot-sizing polices for perishable goods when the demand depends on selling price, displayed stocks, and expiration date. International Journal of Production Economics. 2017;185:11-20.

[24] Wu J, Teng J-T, Chan Y-L. Inventory policies for perishable products with expiration dates and advance-cash-credit payment schemes. Int J Syst Sci: Oper Logist. 2018;5:310-326.

[25] Li R, Teng, J-T. Pricing and lot-sizing decisions for perishable goods when demand depends on selling price, reference price, product freshness, and displayed stocks. Eur J Oper Res. 2018;270:1099-1108.

[26] Sebatjane M, Adetunji O. Optimal lot-sizing and shipment decisions in a three-echelon supply chain for growing items with inventory level- and expiration date-dependent demand. Appl Math Model. 2021;90:1204-1225.

[27] Shi R, You C. Joint dynamic pricing and freshness-keeping effort strategy for perishable products with price-, freshness-, and stock-dependent demand. J Ind Manag Optim. 2023;19:6572-6592.

[28] Wagner H M, Whitin T M. Dynamic version of the economic lot size model. Manag Sci. 1958;5:89-96.

[29] Florian M, Klein M. Deterministic production planning with concave costs and capacity constraints. Manag Sci. 1971;18:12-20.

[30] Bitran G R, Yanasse H H. Computational complexity of the capacitated lot sizing problem. Manag Sci. 1982;18:1174-1186.

[31] Hoesel van CP M, Wagelmans A. An o (t) 3 algorithm for the economic lot-sizing problem with constant capacities. Manag Sci. 1996;42:142-150.

[32] Fan J, Ou J. On dynamic lot sizing with bounded inventory for a perishable product. Omega. 2023;119:102895.

[33] Önal M, van den Heuvel W, Dereli M M, Albey E. Economic lot sizing problem with tank scheduling. Eur J Oper Res. 2023; 308(1):166-182.

[34] Dziuba D, Almeder C. New construction heuristic for capacitated lot sizing problems. Eur J Oper Res. 2023; 311(3):906-920.

[35] Absi N, van den Heuvel W, Dauzère-Pérès S. Complexity analysis of integrated dynamic lot sizing and maintenance planning problems. Eur J Oper Res. 2024; 318(1):100-109.

[36] Akbalik A, Gicquel C, Penz B, Rapine C. Lot sizing with capacity adjustment using on-site green and grid electricity. Omega. 2025;133:103260.

[37] Kunreuther H, Schrage L. Joint pricing and inventory decisions for constant priced items. Manag Sci. 1973;7:732-738.

[38] Heuvel van den W, Wagelmans AP M. A polynomial time algorithm for a deterministic joint pricing and inventory model. Eur J Oper Res. 2006; 170(2):463-480.

[39] Geunes J, Romeijn H, Taaffe K. Requirements planning with pricing and order selection flexibility. Operations Research. 2006;54:394-401.

[40] Geunes J, Merzifonluoglu Y, Romeijn H. Capacitated procurement planning with price-sensitive demand and general concave-revenue functions. Eur J Oper Res. 2009;54:390-405.

[41] Terzi M, Yalaoui A, Ouazene Y, Yalaoui F. Integrated lot-sizing and pricing problem under cross-price demand model. IFAC-PapersOnLine. 2022; 55(10):2372-2377. 10th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2022.

[42] Önal M, Romeijn H E. Two-echelon requirements planning with pricing decisions. J Ind Manag Optim. 2009; 5(4):767-781.

[43] Önal M, Romeijn, H E. Multi-item capacitated lot-sizing problems with setup times and pricing decisions. Wiley InterScience. 2010; 57(2):172-187.

[44] Wu X, Gong Y Y, Xu H, Chu C, Zhang J. Dynamic lot-sizing models with pricing for new products. Eur J Oper Res. 2017;260:81-92.

[45] Couzon P, Ouazene Y, Yalaoui F. Joint optimization of dynamic pricing and lot-sizing decisions with nonlinear demands: Theoretical and computational analysis. Comput Oper Res. 2020;115:104862.

[46] Fisher M L. The lagrangian relaxation method for solving integer programming problems. Manag Sci. 1981;27:1861-1871.

[47] Absi N, Kedad-Sidhoum S. The multi-item capacitated lot-sizing problem with safety stocks and demand shortage costs. Comput Oper Res. 2009;36:2926-2936.

[48] Zhang Z-H, Jiang H, Pan X. A lagrangian relaxation based approach for the capacitated lot sizing problem in closed-loop supply chain. Int J Prod Econ. 2012; 140(1):249-255.

[49] Diaby M, Bahl H C, Karwan M H, Zionts S. A lagrangian relaxation approach for very-large-scale capacitated lot-sizing. Manag Sci. 2012;38:1329-1340.

[50] Süral H, Denizel M, Wassenhove LN V. Lagrangean relaxation based heuristics for lot sizing with setup times. Eur J Oper Res. 2009; 194(1):51-63.

[51] Ali S, Gupta O K. Lagrangian relaxation procedure for the capacitated dynamic lot sizing problem. In 13 th AIMS Int J Manag. 2005;9:51-63.

[52] Cai J, Huang Y, Diao C, Jin Z. Joint optimization of empty container repositioning and inventory control applying dynamic programming and simulated annealing. Appl Soft Comput. 2024;167:112452.

[53] Xie J, Gao L, Li X, Gui L. A hybrid genetic tabu search algorithm for distributed job-shop scheduling problems. Swarm Evol Comput. 2024;90:101670.

[54] Yao Y, Gui L, Li X, Gao L. Tabu search based on novel neighborhood structures for solving job shop scheduling problem integrating finite transportation resources. Robot Comput-Integr Manuf. 2024;89:102782.

[55] Qian L, Melachrinoudis E. An integrated neural combinatorial tabu search for optimizing school bus scheduling with bell time. Transp Res Part C Emerg. 2024;164:104662.

[56] Xiao D, Li J, Zhang Z, Gu Z, Fu Y, Niu J. Optimization of personnel evacuation routes for sudden nuclear accidents based on hybrid genetic-grey wolf optimizer algorithm. Nucl Eng Technol. 2024;103223.

[57] Rosati R M, Schaerf A. Multi-neighborhood simulated annealing for the capacitated dispersion problem. Expert Syst Appl. 2024;255:124484.

[58] Niroumandrad N, Lahrichi N, Lodi A. Learning tabu search algorithms: A scheduling application. Comput Oper Res. 2024;170:106751.

[59] Ban H-B, Pham D-H. A multi-population multi-tasking tabu search with variable neighborhood search algorithm to solve post-disaster clustered repairman problem with priorities. Appl Soft Comput. 2025;170:112655.

[60] Hao L, Zou Z, Liang X. Solving multi-objective energy-saving flexible job shop scheduling problem by hybrid search genetic algorithm. Comput Ind Eng. 2025;110829.

[61] Shi K, Yang L, Wu Z, Jiang B, Gao Q. Multi-robot dynamic path planning with priority based on simulated annealing. J Franklin Inst. 2025; 362(1):107396.

[62] Chen X, Li J, Wang Z, Li J, Gao K. A genetic programming based cooperative evolutionary algorithm for flexible job shop with crane transportation and setup times. Appl Soft Comput. 2025;169:112614.

[63] Dong X, Ma L, Zhao X, Shan Y, Wang J, Xu Z. Hybrid genetic algorithm with wiener process for multi-scale colored balanced traveling salesman problem. Expert Syst Appl. 2025;262:125610.

[64] Wang H-K, Yang T-Y, Wang Y-H, Wu C-L. Hybrid dispatching and genetic algorithm for the surface mount technology scheduling problem in semiconductor factories. Int J Prod Econ. 2025;280:109500.

[65] Zhang H, Lv S, Xin D, Jin H. A genetic algorithm enhanced with neighborhood structure for general flexible job shop scheduling with parallel batch processing machine. Expert Syst Appl. 2025;265:125888.

[66] Moreno F, Forcael E, Orozco F, Baesler F, Agdas D. Fixed start method for repetitive project scheduling with simulated annealing. Heliyon. 2025; 11(2):41741.

[67] Sharma H, Galván E, Mooney P. A parallel genetic algorithm for multi-criteria path routing on complex real-world road networks. Appl Soft Comput. 2025;170:112559.

[68] Chandrashekhar M, Dhal P. Multi-objective economic and emission dispatch problems using hybrid honey bee simulated annealing. Meas: Sens. 2024;32:101065.

[69] Bektur G, Aslan H K. Artificial bee colony algorithm for operating room scheduling problem with dedicated/flexible resources and cooperative operations. Int J Optim Control: Theor Appl (IJOCTA). 2024; 14(3):193-207.

[70] Özdamar L, Barbarosoğlu G. Hybrid heuristics for the multi-stage capacitated lot sizing and loading problem. J Oper Res Soc. 1999;50:810-825.

[71] Ajmera R. A review of applications of genetic algorithms in lot sizing. J Intell Manuf. 2010;21:575-590.

[72] Gopalakrishnan M, Ding K, Bourjolly J-M, Mohan S. A tabu-search heuristic for the capacitated lot-sizing problem with set-up carryover. Manag Sci. 2001;47:851-863.

[73] Piñeyro P, Viera O. The economic lot-sizing problem with remanufacturing: analysis and an improved algorithm. J Reman. 2015; 5(12):1-13.

[74] Kuik R, Salomon M, Wassenhove LN V, Maes J. Linear programming, simulated annealing and tabu search heuristics for lot sizing in bottleneck assembly systems. IIE Transactions. 1993; 25(1):62-72.

[75] Hindi K. Solving the single-item, capacitated dynamic lot-sizing problem with startup and reservation costs by tabu search. Comput Ind Eng. 1995; 28(4):701-707.

[76] Kimms A. Competitive methods for multi-level lot sizing and scheduling: tabu search and randomized regrets. Int J Prod Res. 1996; 34(8):2279-2298.

[77] Hindi K S. Solving the clsp by a tabu search heuristic. J Oper Res Soc. 1996; 47(1):151-161.

[78] Mohan G, Ding K, Bourjolly j-m, Mohan S. A tabu-search heuristic for the capacitated lot-sizing problem with set-up carryover. Management Science. 2001;47:851-863.

[79] Hung Y-F, Chen C-P, Chuang S-C, Hung M-H. Using tabu search with ranking candidate list to solve production planning problems with setups. Computers & Industrial Engineering. 2003;45:615-634.

[80] Taş D Stokastik süreler İçeren kapasite kısıtlı parti büyüklüğü belirleme problemi. Avrupa Bilim ve Teknoloji Dergisi. 2019;16:441-453.

[81] Glover F. Tabu search - part 1. ORSA Journal on Computing. 1989;1:190-206.

[82] Glover F. Tabu search - part 2. ORSA Journal on Computing. 1990;2:4-32.

[83] Held M, Wolfe P, Crowder H P. Validation of sub-gradient optimization. Math Program. 1974;6:62-88.

[84] Walpole R E, Myers R H, Myers S L, Ye K. Probability & statistics for engineers and scientists. Pearson Education, 9th edition. 2011

[85] Michelucci U. Fundamental Mathematical Concepts for Machine Learning in Science. Springer. 2024;

[86] Turan M E, Cetin T. Analyzing the effect of sewer network size on optimization algorithms’ performance in sewer system optimization. Water. 2024; 16(6).

[87] Amaral AR S. A mixed-integer programming formulation for optimizing the double row layout problem. Optimization Methods and Software. 2024; 39(6):1428-1444.