Effective Algorithms for the Economic Lot-Sizing Problem with Bounded Inventory and Linear Fixed-Charge Cost Structure

José M. Gutiérrez, Beatriz Abdul-Jalbar, Joaquín Sicilia and Inmaculada Rodríguez-Martín
Additional contact information
José M. Gutiérrez: Departamento Matemáticas, Estadística e Investigación Operativa, Universidad de La Laguna, 38200 Santa Cruz de Tenerife, Spain
Beatriz Abdul-Jalbar: Departamento Matemáticas, Estadística e Investigación Operativa, Universidad de La Laguna, 38200 Santa Cruz de Tenerife, Spain
Joaquín Sicilia: Departamento Matemáticas, Estadística e Investigación Operativa, Universidad de La Laguna, 38200 Santa Cruz de Tenerife, Spain
Inmaculada Rodríguez-Martín: Departamento Matemáticas, Estadística e Investigación Operativa, Universidad de La Laguna, 38200 Santa Cruz de Tenerife, Spain

Mathematics, 2021, vol. 9, issue 6, 1-21

Abstract: 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 O T 2 dynamic programming algorithm is introduced, where T 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 O T on-line array searching method in Monge arrays can be used when the costs are non-speculative costs.

Keywords: lot-sizing; dynamic programming; geometric technique; Monge arrays (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/6/689/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/6/689/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:6:p:689-:d:522594

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().