A dynamic programming approach for the two-product capacitated lot-sizing problem with concave costs

Kevin A. Bunn and José A. Ventura

European Journal of Operational Research, 2023, vol. 307, issue 1, 116-129

Abstract: In this paper, we analyze a two-product multi-period dynamic lot-sizing problem with a fixed capacity constraint in each period. Each product has a known demand in each period that must be satisfied over a finite planning horizon. The aim of this problem is to minimize the overall cost of placing orders and carrying inventory across all periods. The structure of an optimal solution is analyzed with respect to a type of period called regeneration period, which is a period where the inventory of one or both products reach zero. We show that there is an optimal arrangement of placing orders between consecutive regeneration periods. We propose a pseudo-polynomial algorithm to solve the two-product problem. First, we show how the optimal ordering pattern between two consecutive regeneration periods can be solved using a shortest path problem. Then, we explain how the optimal locations for regeneration periods can be found by solving a shortest path problem on a different network, where each arc corresponds to the shortest path in a subproblem network. We then show how this approach can be scaled up to a three-product problem and generalize this technique to any number of products, as long as it is small.

Keywords: Production planning; Capacitated lot sizing; Multiple products; Dynamic demand; Pseudo-polynomial algorithm (search for similar items in EconPapers)
Date: 2023
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/S0377221722006683
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:307:y:2023:i:1:p:116-129

DOI: 10.1016/j.ejor.2022.08.026

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