
-
Previous Article
Optimal portfolio selection with life insurance under subjective survival belief and habit formation
- JIMO Home
- This Issue
-
Next Article
Generalization of hyperbolic smoothing approach for non-smooth and non-Lipschitz functions
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) |
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.
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. |
[2] |
D. Eppstein, Finding the k shortest paths, SIAM Journal on Computing, 28 (1999), 652–673.
doi: 10.1137/S0097539795290477. |
[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. |
[4] |
C. S. Guazzelli and C. B. Cunha, Exploring k-best solutions to enrich network design decision-making, Omega, 78 (2018), 139–164. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[12] |
S. Van Hoesel, Model and algorithms for single item lot sizing problems, Ph.D thesis, Erasmus University in Rotterdam, 1991. |
[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. |
[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. |
[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. |
[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. |
[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. |
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. |
[2] |
D. Eppstein, Finding the k shortest paths, SIAM Journal on Computing, 28 (1999), 652–673.
doi: 10.1137/S0097539795290477. |
[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. |
[4] |
C. S. Guazzelli and C. B. Cunha, Exploring k-best solutions to enrich network design decision-making, Omega, 78 (2018), 139–164. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[12] |
S. Van Hoesel, Model and algorithms for single item lot sizing problems, Ph.D thesis, Erasmus University in Rotterdam, 1991. |
[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. |
[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. |
[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. |
[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. |
[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. |


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 |
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 |
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 |
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 |
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 |
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 |
Optimal Cost | Resource Consump. | PA time(s) | DP time(s) | |||
25 | 720672 | 351344 | 707712 | 0.00 | 0.64 | |
650354 | 351822 | 614810 | 0.00 | 0.50 | ||
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 | 1366251 | 1506134 | 1330674 | 0.00 | 4.96 | |
1224202 | 1506831 | 1210488 | 0.00 | 4.70 | ||
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 | 2468624 | 5181363 | 2457749 | 0.00 | 57.08 | |
2204089 | 5182719 | 2203037 | 0.02 | 48.74 | ||
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 |
Optimal Cost | Resource Consump. | PA time(s) | DP time(s) | |||
25 | 720672 | 351344 | 707712 | 0.00 | 0.64 | |
650354 | 351822 | 614810 | 0.00 | 0.50 | ||
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 | 1366251 | 1506134 | 1330674 | 0.00 | 4.96 | |
1224202 | 1506831 | 1210488 | 0.00 | 4.70 | ||
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 | 2468624 | 5181363 | 2457749 | 0.00 | 57.08 | |
2204089 | 5182719 | 2203037 | 0.02 | 48.74 | ||
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 and 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 and 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 and 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 and 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 and Management Optimization, 2022, 18 (3) : 1891-1913. 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 and 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 and 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 and Management Optimization, 2014, 10 (4) : 1147-1168. doi: 10.3934/jimo.2014.10.1147 |
[9] |
Dragos-Patru Covei, Elena Cristina Canepa, Traian A. Pirvu. Stochastic production planning with regime switching. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022013 |
[10] |
Qing Yang, Shiji Song, Cheng Wu. Inventory policies for a partially observed supply capacity model. Journal of Industrial and Management Optimization, 2013, 9 (1) : 13-30. doi: 10.3934/jimo.2013.9.13 |
[11] |
Onur Kaya, Halit Bayer. Pricing and lot-sizing decisions for perishable products when demand changes by freshness. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3113-3129. doi: 10.3934/jimo.2020110 |
[12] |
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 and Management Optimization, 2016, 12 (3) : 1091-1119. doi: 10.3934/jimo.2016.12.1091 |
[13] |
Dieter Armbruster, Michael Herty, Xinping Wang, Lindu Zhao. Integrating release and dispatch policies in production models. Networks and Heterogeneous Media, 2015, 10 (3) : 511-526. doi: 10.3934/nhm.2015.10.511 |
[14] |
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 and Management Optimization, 2017, 13 (1) : 413-428. doi: 10.3934/jimo.2016024 |
[15] |
Josef Hofbauer, Sylvain Sorin. Best response dynamics for continuous zero--sum games. Discrete and Continuous Dynamical Systems - B, 2006, 6 (1) : 215-224. doi: 10.3934/dcdsb.2006.6.215 |
[16] |
Chenyin Wang, Yaodong Ni, Xiangfeng Yang. The inventory replenishment policy in an uncertain production-inventory-routing system. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021196 |
[17] |
Shuren Liu, Qiying Hu, Yifan Xu. Optimal inventory control with fixed ordering cost for selling by internet auctions. Journal of Industrial and Management Optimization, 2012, 8 (1) : 19-40. doi: 10.3934/jimo.2012.8.19 |
[18] |
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 |
[19] |
Marek Galewski, Renata Wieteska. Multiple periodic solutions to a discrete $p^{(k)}$ - Laplacian problem. Discrete and Continuous Dynamical Systems - B, 2014, 19 (8) : 2535-2547. doi: 10.3934/dcdsb.2014.19.2535 |
[20] |
Tanka Nath Dhamala. A survey on models and algorithms for discrete evacuation planning network problems. Journal of Industrial and Management Optimization, 2015, 11 (1) : 265-289. doi: 10.3934/jimo.2015.11.265 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]