Improved exact algorithms to economic lot-sizing with piecewise linear production costs

Jinwen Ou

European Journal of Operational Research, 2017, vol. 256, issue 3, 777-784

Abstract: In this article we study a classical single-item economic lot-sizing problem, where production cost functions are assumed to be piecewise linear. The lot-sizing problem is fundamental in lot-sizing research, and it is applicable to a wide range of production planning models. The intractability of the problem is related to the value of m, the number of different breakpoints of the production cost functions. When m is arbitrary, the problem is known to be NP-hard (Florian, Lenstra & Rinnooy Kan, 1980). However, if m is fixed, then it can be solved in polynomial time (Koca, Yaman & Akturk, 2014). So far, the most efficient algorithm to solve the problem has a complexity of O(T2m+3), where T is the number of periods in the planning horizon (Koca et al., 2014). In this article we present an improved exact algorithm for solving the problem, where the complexity is reduced to O(Tm+2·logT). As such it also improves upon the computational efficiency of solving some existing lot-sizing problems which are important special cases of our model. In order to achieve a more efficient implementation, our algorithm makes use of a specific data structure, named range minimum query (RMQ).

Keywords: Dynamic programming; Economic lot-sizing; Algorithm design; Range minimum query (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716304611
Full text for ScienceDirect subscribers only

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:eee:ejores:v:256:y:2017:i:3:p:777-784

DOI: 10.1016/j.ejor.2016.06.040

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().