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

Kevin A. Bunn, José A. Ventura

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)116-129
Number of pages14
JournalEuropean Journal of Operational Research
Volume307
Issue number1
DOIs
StatePublished - May 16 2023

All Science Journal Classification (ASJC) codes

  • Information Systems and Management
  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'A dynamic programming approach for the two-product capacitated lot-sizing problem with concave costs'. Together they form a unique fingerprint.

Cite this