Dynamic programming approximation algorithms for the capacitated lot-sizing problem

No Thumbnail Available
Issue Date
2016-06
Authors
Buyuktahtakin, Esra
Liu, Ning
Advisor
Citation

Buyuktahtakin, I. Esra; Liu, Ning. 2016. Dynamic programming approximation algorithms for the capacitated lot-sizing problem. Journal of Global Optimization, vol. 65:no. 2:pp 231–259

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.

Table of Content
Description
Click on the DOI link to access the article (may not be free).
publication.page.dc.relation.uri