An efficient algorithm for the 2-level capacitated lot-sizing problem with identical capacities at both levels

Guillaume Goisque and Christophe Rapine

European Journal of Operational Research, 2017, vol. 261, issue 3, 918-928

Abstract: We present a polynomial time algorithm for solving the 2-level production-in-series lot-sizing problem with capacities at both levels. At each level, we consider a fixed setup cost together with linear production and holding costs. We assume that capacities are stationary and identical at both levels. We introduce a new cost structure, called path non-speculative, generalizing the classical non-speculative cost structure. We show that under this cost structure the problem can be solved in time complexity O(T5), where T is the number of periods of the planning horizon. When the cost structure follows the classical non-speculative motives, the time complexity is reduced to O(T3).

Keywords: Combinatorial optimization; Capacitated lot sizing; Two-echelon; Dynamic programming; Non-speculative motives (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717301467
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:261:y:2017:i:3:p:918-928

DOI: 10.1016/j.ejor.2017.02.024

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