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

Full description

Bibliographic Details
Main Authors: José M. Gutiérrez, Beatriz Abdul-Jalbar, Joaquín Sicilia, Inmaculada Rodríguez-Martín
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