Effective Algorithms for the Economic Lot-Sizing Problem with Bounded Inventory and Linear Fixed-Charge Cost Structure
Efficient algorithms for the economic lot-sizing problem with storage capacity are proposed. On the one hand, for the cost structure consisting of general linear holding and ordering costs and fixed setup costs, an <inline-formula><math display="inline"><semantics><mro...
Main Authors: | , , , |
---|---|
Format: | Article |
Language: | English |
Published: |
MDPI AG
2021-03-01
|
Series: | Mathematics |
Subjects: | |
Online Access: | https://www.mdpi.com/2227-7390/9/6/689 |
_version_ | 1797540285764337664 |
---|---|
author | José M. Gutiérrez Beatriz Abdul-Jalbar Joaquín Sicilia Inmaculada Rodríguez-Martín |
author_facet | José M. Gutiérrez Beatriz Abdul-Jalbar Joaquín Sicilia Inmaculada Rodríguez-Martín |
author_sort | José M. Gutiérrez |
collection | DOAJ |
description | Efficient algorithms for the economic lot-sizing problem with storage capacity are proposed. On the one hand, for the cost structure consisting of general linear holding and ordering costs and fixed setup costs, an <inline-formula><math display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mfenced><mrow><msup><mi>T</mi><mn>2</mn></msup></mrow></mfenced></mrow></semantics></math></inline-formula> dynamic programming algorithm is introduced, where <inline-formula><math display="inline"><semantics><mi>T</mi></semantics></math></inline-formula> is the number of time periods. The new approach induces an accurate partition of the planning horizon, discarding most of the infeasible solutions. Moreover, although there are several algorithms based on dynamic programming in the literature also running in quadratic time, even considering more general cost structures and assumptions, the new solution uses a geometric technique to speed up the algorithm for a class of subproblems generated by dynamic programming, which can now be solved in linearithmic time. To be precise, the computational results show that the average occurrence percentage of this class of subproblems ranges between 13% and 45%, depending on both the total number of periods and the percentage of storage capacity availability. Furthermore, this percentage significantly increases from 13% to 35% as the capacity availability decreases. This reveals that the usage of the geometric technique is predominant under restrictive storage capacities. Specifically, when the percentage of capacity availability is below 50%, the average running times are on average 100 times faster than those when this percentage is above 50%. On the other hand, an <inline-formula><math display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mfenced><mi>T</mi></mfenced></mrow></semantics></math></inline-formula> on-line array searching method in Monge arrays can be used when the costs are non-speculative costs. |
first_indexed | 2024-03-10T12:58:50Z |
format | Article |
id | doaj.art-41c37ba4af1742768fe8df8a71ac97a1 |
institution | Directory Open Access Journal |
issn | 2227-7390 |
language | English |
last_indexed | 2024-03-10T12:58:50Z |
publishDate | 2021-03-01 |
publisher | MDPI AG |
record_format | Article |
series | Mathematics |
spelling | doaj.art-41c37ba4af1742768fe8df8a71ac97a12023-11-21T11:40:40ZengMDPI AGMathematics2227-73902021-03-019668910.3390/math9060689Effective Algorithms for the Economic Lot-Sizing Problem with Bounded Inventory and Linear Fixed-Charge Cost StructureJosé M. Gutiérrez0Beatriz Abdul-Jalbar1Joaquín Sicilia2Inmaculada Rodríguez-Martín3Departamento Matemáticas, Estadística e Investigación Operativa, Universidad de La Laguna, 38200 Santa Cruz de Tenerife, SpainDepartamento Matemáticas, Estadística e Investigación Operativa, Universidad de La Laguna, 38200 Santa Cruz de Tenerife, SpainDepartamento Matemáticas, Estadística e Investigación Operativa, Universidad de La Laguna, 38200 Santa Cruz de Tenerife, SpainDepartamento Matemáticas, Estadística e Investigación Operativa, Universidad de La Laguna, 38200 Santa Cruz de Tenerife, SpainEfficient algorithms for the economic lot-sizing problem with storage capacity are proposed. On the one hand, for the cost structure consisting of general linear holding and ordering costs and fixed setup costs, an <inline-formula><math display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mfenced><mrow><msup><mi>T</mi><mn>2</mn></msup></mrow></mfenced></mrow></semantics></math></inline-formula> dynamic programming algorithm is introduced, where <inline-formula><math display="inline"><semantics><mi>T</mi></semantics></math></inline-formula> is the number of time periods. The new approach induces an accurate partition of the planning horizon, discarding most of the infeasible solutions. Moreover, although there are several algorithms based on dynamic programming in the literature also running in quadratic time, even considering more general cost structures and assumptions, the new solution uses a geometric technique to speed up the algorithm for a class of subproblems generated by dynamic programming, which can now be solved in linearithmic time. To be precise, the computational results show that the average occurrence percentage of this class of subproblems ranges between 13% and 45%, depending on both the total number of periods and the percentage of storage capacity availability. Furthermore, this percentage significantly increases from 13% to 35% as the capacity availability decreases. This reveals that the usage of the geometric technique is predominant under restrictive storage capacities. Specifically, when the percentage of capacity availability is below 50%, the average running times are on average 100 times faster than those when this percentage is above 50%. On the other hand, an <inline-formula><math display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mfenced><mi>T</mi></mfenced></mrow></semantics></math></inline-formula> on-line array searching method in Monge arrays can be used when the costs are non-speculative costs.https://www.mdpi.com/2227-7390/9/6/689lot-sizingdynamic programminggeometric techniqueMonge arrays |
spellingShingle | José M. Gutiérrez Beatriz Abdul-Jalbar Joaquín Sicilia Inmaculada Rodríguez-Martín Effective Algorithms for the Economic Lot-Sizing Problem with Bounded Inventory and Linear Fixed-Charge Cost Structure Mathematics lot-sizing dynamic programming geometric technique Monge arrays |
title | Effective Algorithms for the Economic Lot-Sizing Problem with Bounded Inventory and Linear Fixed-Charge Cost Structure |
title_full | Effective Algorithms for the Economic Lot-Sizing Problem with Bounded Inventory and Linear Fixed-Charge Cost Structure |
title_fullStr | Effective Algorithms for the Economic Lot-Sizing Problem with Bounded Inventory and Linear Fixed-Charge Cost Structure |
title_full_unstemmed | Effective Algorithms for the Economic Lot-Sizing Problem with Bounded Inventory and Linear Fixed-Charge Cost Structure |
title_short | Effective Algorithms for the Economic Lot-Sizing Problem with Bounded Inventory and Linear Fixed-Charge Cost Structure |
title_sort | effective algorithms for the economic lot sizing problem with bounded inventory and linear fixed charge cost structure |
topic | lot-sizing dynamic programming geometric technique Monge arrays |
url | https://www.mdpi.com/2227-7390/9/6/689 |
work_keys_str_mv | AT josemgutierrez effectivealgorithmsfortheeconomiclotsizingproblemwithboundedinventoryandlinearfixedchargecoststructure AT beatrizabduljalbar effectivealgorithmsfortheeconomiclotsizingproblemwithboundedinventoryandlinearfixedchargecoststructure AT joaquinsicilia effectivealgorithmsfortheeconomiclotsizingproblemwithboundedinventoryandlinearfixedchargecoststructure AT inmaculadarodriguezmartin effectivealgorithmsfortheeconomiclotsizingproblemwithboundedinventoryandlinearfixedchargecoststructure |