# American Institute of Mathematical Sciences

doi: 10.3934/jimo.2021102
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## Solving a constrained economic lot size problem by ranking efficient production policies

 1 Departamento de Matemáticas, Estadística e Investigación Operativa, Universidad de La Laguna, CP 38271 - La Laguna, Tenerife (Spain)

* Corresponding author: Antonio Sedeño-Noda

Received  October 2020 Revised  March 2021 Early access May 2021

Fund Project: The first author is supported by the grant MTM2016-74877-P from the Ministerio de Economía y Competitividad

We address the problem of finding the $K$ best Zero-Inventory-Ordering (ZIO) policies of an Economic Lot-Sizing Problem (ELSP) with $n$ time periods. To this end, we initially focus on devising an efficient algorithm to determine the Second Best ZIO policy. Based on both this latter algorithm and recent results from the state-of-the-art literature, we propose a solution method to compute the remaining $K$ Best ZIO policies in $O(n(K+n))$ time and $O(K+n^2 )$ space. One claimed advantage of this approach is that it would efficiently solve a family of ELS problems, which includes a basic knapsack type constraint. A computational experiment is carried out to test the performance of the new algorithm $K$-ZIO and Constrained-ZIO for different values of $K$ and $n$. For the particular case when the left-hand side coefficients in that constraint are equal, we provide an $O(n^3 )$ solution method.

Citation: Antonio Sedeño-Noda, José M. Gutiérrez. Solving a constrained economic lot size problem by ranking efficient production policies. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2021102
##### References:

show all references

##### References:
Shortest path trees for the ELSP instance
Shortest paths in graph H
CPU times vs. $c(P^K )-c(P^1)$ for $K$ = 1.000.000
CPU times vs. $c(P^K )-c(P^1)$ for $K$ = 10.000.000
Input data and the values of $G(i)$, $F(i-1)$, $Succ(i)$ and $Pred(i)$
 $i$ $d_{in}$ $f_i$ $c_i$ $G(i)$ $Succ(i)$ $F(i-1)$ $Pred(i)$ 1 630 85 12 4724 3 0 1 2 561 102 11 3858 4 913 1 3 532 102 10 3463 5 1261 1 4 496 101 9 3041 5 1693 1 5 435 98 8 2391 8 2333 3 6 374 114 7 1859 8 2892 4 7 348 105 6 1634 8 3126 4 8 314 86 5 1325 10 3399 5 9 247 119 4 935 11 3820 8 10 202 110 3 679 11 4045 8 11 135 98 2 368 13 4356 10 12 56 114 1 170 13 4593 10 13 0 13 4724 11
 $i$ $d_{in}$ $f_i$ $c_i$ $G(i)$ $Succ(i)$ $F(i-1)$ $Pred(i)$ 1 630 85 12 4724 3 0 1 2 561 102 11 3858 4 913 1 3 532 102 10 3463 5 1261 1 4 496 101 9 3041 5 1693 1 5 435 98 8 2391 8 2333 3 6 374 114 7 1859 8 2892 4 7 348 105 6 1634 8 3126 4 8 314 86 5 1325 10 3399 5 9 247 119 4 935 11 3820 8 10 202 110 3 679 11 4045 8 11 135 98 2 368 13 4356 10 12 56 114 1 170 13 4593 10 13 0 13 4724 11
Values of $SF(i-1)$, $sPred(i)$ and $R(i)$ for the example in Table 1
 $i$ $G(i)$ $Succ(i)$ $F(i-1)$ $Pred(i)$ $SF(i-1)$ $sPred(i)$ $R(i)$ 1 4724 3 0 1 2 3858 4 913 1 3 3463 5 1261 1 1334 2 4797 4 3041 5 1693 1 1723 3 5 2391 8 2333 3 2343 4 4734 6 1859 8 2892 4 2919 5 7 1634 8 3126 4 3127 5 8 1325 10 3399 5 3426 6 4751 9 935 11 3820 8 3837 7 10 679 11 4045 8 4107 7 4786 11 368 13 4356 10 4380 8 4748 12 170 13 4593 10 4612 11 13 0 13 4724 11 4761 10 4761
 $i$ $G(i)$ $Succ(i)$ $F(i-1)$ $Pred(i)$ $SF(i-1)$ $sPred(i)$ $R(i)$ 1 4724 3 0 1 2 3858 4 913 1 3 3463 5 1261 1 1334 2 4797 4 3041 5 1693 1 1723 3 5 2391 8 2333 3 2343 4 4734 6 1859 8 2892 4 2919 5 7 1634 8 3126 4 3127 5 8 1325 10 3399 5 3426 6 4751 9 935 11 3820 8 3837 7 10 679 11 4045 8 4107 7 4786 11 368 13 4356 10 4380 8 4748 12 170 13 4593 10 4612 11 13 0 13 4724 11 4761 10 4761
Average running times (in seconds) for each pair $(n, K)$
 $K$ $n$ 10,000 100,000 1,000,000 10,000,000 25 0 0.033 0.419 5.474 50 0.004 0.053 0.532 5.621 100 0.006 0.061 0.714 7.391 Mean 0.003 0.049 0.555 6.162
 $K$ $n$ 10,000 100,000 1,000,000 10,000,000 25 0 0.033 0.419 5.474 50 0.004 0.053 0.532 5.621 100 0.006 0.061 0.714 7.391 Mean 0.003 0.049 0.555 6.162
Experiment results for each pair $(n, R)$
 $n$ $R$ Optimal Cost Resource Consump. PA time(s) DP time(s) 25 $C(P1)=$ 351014 720672 351344 707712 0.00 0.64 $MaxR=$ 790991 650354 351822 614810 0.00 0.50 $MinR=$ 87809 580036 352354 555182 0.00 0.43 509718 353197 502609 0.00 0.44 439400 354195 434312 0.00 0.34 369081 356091 363770 0.00 0.30 298763 359051 296180 0.00 0.26 228445 365764 225688 0.00 0.20 158127 376905 149418 0.00 0.15 50 $C(P1)=$ 1505508 1366251 1506134 1330674 0.00 4.96 $MaxR=$ 1508301 1224202 1506831 1210488 0.00 4.70 $MinR=$ 87809 1082153 1507974 1081825 0.00 3.87 940104 1509988 939444 0.01 3.40 798055 1512701 797902 0.02 2.73 656005 1517148 653103 0.02 2.20 513956 1525302 511455 0.02 1.61 371907 1544098 370770 0.03 1.05 229858 1571338 225693 0.01 0.69 100 $C(P1)=$ 5180639 2468624 5181363 2457749 0.00 57.08 $MaxR=$ 2733159 2204089 5182719 2203037 0.02 48.74 $MinR=$ 87809 1939554 5184763 1937453 0.08 43.48 1675019 5188282 1662572 0.16 37.67 1410484 5193502 1408381 0.24 30.42 1145949 5206379 1145394 0.41 23.21 881414 5226838 880005 0.61 16.78 616879 5261660 616134 0.71 10.34 352344 5344062 347168 0.50 4.18
 $n$ $R$ Optimal Cost Resource Consump. PA time(s) DP time(s) 25 $C(P1)=$ 351014 720672 351344 707712 0.00 0.64 $MaxR=$ 790991 650354 351822 614810 0.00 0.50 $MinR=$ 87809 580036 352354 555182 0.00 0.43 509718 353197 502609 0.00 0.44 439400 354195 434312 0.00 0.34 369081 356091 363770 0.00 0.30 298763 359051 296180 0.00 0.26 228445 365764 225688 0.00 0.20 158127 376905 149418 0.00 0.15 50 $C(P1)=$ 1505508 1366251 1506134 1330674 0.00 4.96 $MaxR=$ 1508301 1224202 1506831 1210488 0.00 4.70 $MinR=$ 87809 1082153 1507974 1081825 0.00 3.87 940104 1509988 939444 0.01 3.40 798055 1512701 797902 0.02 2.73 656005 1517148 653103 0.02 2.20 513956 1525302 511455 0.02 1.61 371907 1544098 370770 0.03 1.05 229858 1571338 225693 0.01 0.69 100 $C(P1)=$ 5180639 2468624 5181363 2457749 0.00 57.08 $MaxR=$ 2733159 2204089 5182719 2203037 0.02 48.74 $MinR=$ 87809 1939554 5184763 1937453 0.08 43.48 1675019 5188282 1662572 0.16 37.67 1410484 5193502 1408381 0.24 30.42 1145949 5206379 1145394 0.41 23.21 881414 5226838 880005 0.61 16.78 616879 5261660 616134 0.71 10.34 352344 5344062 347168 0.50 4.18
 [1] Pedro Piñeyro, Omar Viera. Inventory policies for the economic lot-sizing problem with remanufacturing and final disposal options. Journal of Industrial & Management Optimization, 2009, 5 (2) : 217-238. doi: 10.3934/jimo.2009.5.217 [2] Min Tang, Fuying Jing, Xiangrui Chao. A dynamic lot sizing model with production-or-outsourcing decision under minimum production quantities. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2389-2406. doi: 10.3934/jimo.2019059 [3] Ming-Jong Yao, Shih-Chieh Chen, Yu-Jen Chang. A common cycle approach for solving the economic lot and inspection scheduling problem. Journal of Industrial & Management Optimization, 2012, 8 (1) : 141-162. doi: 10.3934/jimo.2012.8.141 [4] Yu-Jen Chang, Ming-Jong Yao. New heuristics for solving the economic lot scheduling problem with reworks. Journal of Industrial & Management Optimization, 2011, 7 (1) : 229-251. doi: 10.3934/jimo.2011.7.229 [5] Sumon Sarkar, Bibhas C. Giri. Optimal lot-sizing policy for a failure prone production system with investment in process quality improvement and lead time variance reduction. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021048 [6] Tien-Yu Lin, Bhaba R. Sarker, Chien-Jui Lin. An optimal setup cost reduction and lot size for economic production quantity model with imperfect quality and quantity discounts. Journal of Industrial & Management Optimization, 2021, 17 (1) : 467-484. doi: 10.3934/jimo.2020043 [7] Jia Shu, Zhengyi Li, Weijun Zhong. A market selection and inventory ordering problem under demand uncertainty. Journal of Industrial & Management Optimization, 2011, 7 (2) : 425-434. doi: 10.3934/jimo.2011.7.425 [8] Xiaoming Yan, Minghui Zhang, Ke Liu, Yong Wang. Optimal ordering policies and sourcing strategies with supply disruption. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1147-1168. doi: 10.3934/jimo.2014.10.1147 [9] Qing Yang, Shiji Song, Cheng Wu. Inventory policies for a partially observed supply capacity model. Journal of Industrial & Management Optimization, 2013, 9 (1) : 13-30. doi: 10.3934/jimo.2013.9.13 [10] Mohsen Lashgari, Ata Allah Taleizadeh, Shib Sankar Sana. An inventory control problem for deteriorating items with back-ordering and financial considerations under two levels of trade credit linked to order quantity. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1091-1119. doi: 10.3934/jimo.2016.12.1091 [11] Onur Kaya, Halit Bayer. Pricing and lot-sizing decisions for perishable products when demand changes by freshness. Journal of Industrial & Management Optimization, 2021, 17 (6) : 3113-3129. doi: 10.3934/jimo.2020110 [12] Dieter Armbruster, Michael Herty, Xinping Wang, Lindu Zhao. Integrating release and dispatch policies in production models. Networks & Heterogeneous Media, 2015, 10 (3) : 511-526. doi: 10.3934/nhm.2015.10.511 [13] Lalida Deeratanasrikul, Shinji Mizuno. Multiple-stage multiple-machine capacitated lot-sizing and scheduling with sequence-dependent setup: A case study in the wheel industry. Journal of Industrial & Management Optimization, 2017, 13 (1) : 413-428. doi: 10.3934/jimo.2016024 [14] Josef Hofbauer, Sylvain Sorin. Best response dynamics for continuous zero--sum games. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 215-224. doi: 10.3934/dcdsb.2006.6.215 [15] Shuren Liu, Qiying Hu, Yifan Xu. Optimal inventory control with fixed ordering cost for selling by internet auctions. Journal of Industrial & Management Optimization, 2012, 8 (1) : 19-40. doi: 10.3934/jimo.2012.8.19 [16] Thomas R. Cameron, Sebastian Charmot, Jonad Pulaj. On the linear ordering problem and the rankability of data. Foundations of Data Science, 2021, 3 (2) : 133-149. doi: 10.3934/fods.2021010 [17] Marek Galewski, Renata Wieteska. Multiple periodic solutions to a discrete $p^{(k)}$ - Laplacian problem. Discrete & Continuous Dynamical Systems - B, 2014, 19 (8) : 2535-2547. doi: 10.3934/dcdsb.2014.19.2535 [18] Tanka Nath Dhamala. A survey on models and algorithms for discrete evacuation planning network problems. Journal of Industrial & Management Optimization, 2015, 11 (1) : 265-289. doi: 10.3934/jimo.2015.11.265 [19] Hari Nandan Nath, Urmila Pyakurel, Tanka Nath Dhamala, Stephan Dempe. Dynamic network flow location models and algorithms for quickest evacuation planning. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2943-2970. doi: 10.3934/jimo.2020102 [20] Chih-Te Yang, Liang-Yuh Ouyang, Hsiu-Feng Yen, Kuo-Liang Lee. Joint pricing and ordering policies for deteriorating item with retail price-dependent demand in response to announced supply price increase. Journal of Industrial & Management Optimization, 2013, 9 (2) : 437-454. doi: 10.3934/jimo.2013.9.437

2020 Impact Factor: 1.801