American Institute of Mathematical Sciences

Advanced
doi: 10.3934/jimo.2021102

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

Antonio Sedeño-Noda 1,, and  José M. Gutiérrez 1,

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 Published  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.

Keywords: The economic lot sizing problem, zero-inventory-ordering policies, K best solutions, production planning, graph algorithms.
Mathematics Subject Classification: Primary: 90C27, 90B05; Secondary: 65K05, 90C35.
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:
[1]

A. Aggarwal and J. K. Park, Improved algorithms for economic lot size problems, Oper. Res., 41 (1993), 549-571.  doi: 10.1287/opre.41.3.549.  Google Scholar

[2]

D. Eppstein, Finding the k shortest paths, SIAM Journal on Computing, 28 (1999), 652–673. doi: 10.1137/S0097539795290477.  Google Scholar

[3]

A. Federgruen and M. Tzur, Simple forward algorithm to solve general dynamic lot sizing models with n periods in 0(nlogn) or 0(n) time, Management Science, 37 (1991), 909–925. doi: 10.1002/1520-6750(199306)40:4<459::AID-NAV3220400404>3.0.CO;2-8.  Google Scholar

[4]

C. S. Guazzelli and C. B. Cunha, Exploring k-best solutions to enrich network design decision-making, Omega, 78 (2018), 139–164. Google Scholar

[5]

M. J. R. Helmrich, R. Jans, W. Van Den Heuvel and A. P. M. Wagelmans, The economic lot-sizing problem with an emission capacity constraint, European Journal of Operational Research, 241 (2015), 50-62.  doi: 10.1016/j.ejor.2014.06.030.  Google Scholar

[6]

D. S. Johnson, M. Yannakakis and C. H. Papadimitriou, On generating all maximal independent sets, Information Processing Letters, 27 (1988), 119-123.  doi: 10.1016/0020-0190(88)90065-8.  Google Scholar

[7]

R. M. Karp, A characterization of the minimum cycle mean in a digraph, Discrete Mathematics, 23 (1978), 309-311.  doi: 10.1016/0012-365X(78)90011-0.  Google Scholar

[8]

M. M. B. Pascoal and A. Sedeño-Noda, Enumerating K best paths in length order in DAGs, European Journal of Operational Research, 221 (2012), 308-316.  doi: 10.1016/j.ejor.2012.04.001.  Google Scholar

[9]

H. E. Romeijn, D. R. Morales and W. Van Den Heuvel, Computational complexity of finding Pareto efficient outcomes for biobjective lot-sizing models, Naval Research Logistics, 61 (2014), 386–402. doi: 10.1002/nav.21590.  Google Scholar

[10]

A. Sedeño-Noda, Ranking one million simple paths in road networks, Asia-Pacific Journal of Operational Research, 33 (2016), 5, 1650042-1. doi: 10.1142/S0217595916500421.  Google Scholar

[11]

A. Sedeño-Noda and S. Alonso-Rodríguez, An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem, Applied Mathematics and Computation, 265 (2015), 602-618. doi: 10.1016/j.amc.2015.05.109.  Google Scholar

[12]

S. Van Hoesel, Model and algorithms for single item lot sizing problems, Ph.D thesis, Erasmus University in Rotterdam, 1991. Google Scholar

[13]

S. Van Hoesel and A. Wagelmans, Sensitivity analysis of the economic lot-sizing problem, Discrete Applied Mathematics, 45 (1993), 291-312. doi: 10.1016/0166-218X(93)90016-H.  Google Scholar

[14]

H. M. Wagner and T.M. Whitin, Dynamic version of the economic lot size model, Management Science, 5 (1958), 89–96. doi: 10.1287/mnsc.5.1.89.  Google Scholar

[15]

A. Wagelmans, S. Van Hoesel and A. Kolen, Economic lot sizing: An O(nlogn) algorithm that runs in linear time in the Wagner-Whitin case, Oper. Res., 40 (1992), S145–S156. doi: 10.1287/opre.40.1.S145.  Google Scholar

[16]

H. Wagner, A postcript to dynamic problems in the theory of the firm, Naval Research Logistics Quarterly, 7 (1960), 7-12.  doi: 10.1002/nav.3800050106.  Google Scholar

[17]

W. I. Zangwill, A deterministic multi-period production scheduling model with backlogging, Management Science, 13 (1966), 105-119.  doi: 10.1287/mnsc.13.1.105.  Google Scholar

show all references

References:
[1]

A. Aggarwal and J. K. Park, Improved algorithms for economic lot size problems, Oper. Res., 41 (1993), 549-571.  doi: 10.1287/opre.41.3.549.  Google Scholar

[2]

D. Eppstein, Finding the k shortest paths, SIAM Journal on Computing, 28 (1999), 652–673. doi: 10.1137/S0097539795290477.  Google Scholar

[3]

A. Federgruen and M. Tzur, Simple forward algorithm to solve general dynamic lot sizing models with n periods in 0(nlogn) or 0(n) time, Management Science, 37 (1991), 909–925. doi: 10.1002/1520-6750(199306)40:4<459::AID-NAV3220400404>3.0.CO;2-8.  Google Scholar

[4]

C. S. Guazzelli and C. B. Cunha, Exploring k-best solutions to enrich network design decision-making, Omega, 78 (2018), 139–164. Google Scholar

[5]

M. J. R. Helmrich, R. Jans, W. Van Den Heuvel and A. P. M. Wagelmans, The economic lot-sizing problem with an emission capacity constraint, European Journal of Operational Research, 241 (2015), 50-62.  doi: 10.1016/j.ejor.2014.06.030.  Google Scholar

[6]

D. S. Johnson, M. Yannakakis and C. H. Papadimitriou, On generating all maximal independent sets, Information Processing Letters, 27 (1988), 119-123.  doi: 10.1016/0020-0190(88)90065-8.  Google Scholar

[7]

R. M. Karp, A characterization of the minimum cycle mean in a digraph, Discrete Mathematics, 23 (1978), 309-311.  doi: 10.1016/0012-365X(78)90011-0.  Google Scholar

[8]

M. M. B. Pascoal and A. Sedeño-Noda, Enumerating K best paths in length order in DAGs, European Journal of Operational Research, 221 (2012), 308-316.  doi: 10.1016/j.ejor.2012.04.001.  Google Scholar

[9]

H. E. Romeijn, D. R. Morales and W. Van Den Heuvel, Computational complexity of finding Pareto efficient outcomes for biobjective lot-sizing models, Naval Research Logistics, 61 (2014), 386–402. doi: 10.1002/nav.21590.  Google Scholar

[10]

A. Sedeño-Noda, Ranking one million simple paths in road networks, Asia-Pacific Journal of Operational Research, 33 (2016), 5, 1650042-1. doi: 10.1142/S0217595916500421.  Google Scholar

[11]

A. Sedeño-Noda and S. Alonso-Rodríguez, An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem, Applied Mathematics and Computation, 265 (2015), 602-618. doi: 10.1016/j.amc.2015.05.109.  Google Scholar

[12]

S. Van Hoesel, Model and algorithms for single item lot sizing problems, Ph.D thesis, Erasmus University in Rotterdam, 1991. Google Scholar

[13]

S. Van Hoesel and A. Wagelmans, Sensitivity analysis of the economic lot-sizing problem, Discrete Applied Mathematics, 45 (1993), 291-312. doi: 10.1016/0166-218X(93)90016-H.  Google Scholar

[14]

H. M. Wagner and T.M. Whitin, Dynamic version of the economic lot size model, Management Science, 5 (1958), 89–96. doi: 10.1287/mnsc.5.1.89.  Google Scholar

[15]

A. Wagelmans, S. Van Hoesel and A. Kolen, Economic lot sizing: An O(nlogn) algorithm that runs in linear time in the Wagner-Whitin case, Oper. Res., 40 (1992), S145–S156. doi: 10.1287/opre.40.1.S145.  Google Scholar

[16]

H. Wagner, A postcript to dynamic problems in the theory of the firm, Naval Research Logistics Quarterly, 7 (1960), 7-12.  doi: 10.1002/nav.3800050106.  Google Scholar

[17]

W. I. Zangwill, A deterministic multi-period production scheduling model with backlogging, Management Science, 13 (1966), 105-119.  doi: 10.1287/mnsc.13.1.105.  Google Scholar

Figure 1.  Shortest path trees for the ELSP instance
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Shortest paths in graph H
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  CPU times vs. $ c(P^K )-c(P^1) $ for $ K $ = 1.000.000
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  CPU times vs. $ c(P^K )-c(P^1) $ for $ K $ = 10.000.000
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  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
Table Options

Download as excel

$ 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
Table 2.  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
Table Options

Download as excel

$ 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
Table 3.  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
Table Options

Download as excel

$ 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
Table 4.  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
Table Options

Download as excel

$ 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, 2020  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  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]

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
[19]

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
[20]

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

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (21)
  • HTML views (51)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences