Dynamic programming approximation algorithms for the capacitated lot-sizing problem

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

This paper provides a new idea for approximating the inventory cost function to be used in a truncated dynamic program for solving the capacitated lot-sizing problem. The proposed method combines dynamic programming with regression, data fitting, and approximation techniques to estimate the inventory cost function at each stage of the dynamic program. The effectiveness of the proposed method is analyzed on various types of the capacitated lot-sizing problem instances with different cost and capacity characteristics. Computational results show that approximation approaches could significantly decrease the computational time required by the dynamic program and the integer program for solving different types of the capacitated lot-sizing problem instances. Furthermore, in most cases, the proposed approximate dynamic programming approaches can accurately capture the optimal solution of the problem with consistent computational performance over different instances.

Original languageEnglish (US)
Pages (from-to)231-259
Number of pages29
JournalJournal of Global Optimization
Volume65
Issue number2
DOIs
StatePublished - Jun 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics

Keywords

  • Approximate dynamic programming
  • Approximation algorithms
  • Capacitated lot-sizing
  • Data fitting
  • Mixed-integer programming
  • Production and inventory control

Fingerprint Dive into the research topics of 'Dynamic programming approximation algorithms for the capacitated lot-sizing problem'. Together they form a unique fingerprint.

Cite this