Approximate dynamic programming algorithms for production-planning problems

Abstract

The capacitated lot-sizing problem (CLSP) is a core problem for successfully reducing overall costs in any production process. The exact approaches proposed for solving the CLSP are based on two major methods: mixed-integer programming and dynamic programming. This thesis provides a new idea for approximating the inventory cost function to be used in a truncated dynamic program for solving the CLSP. In the proposed method, by using only a partial dynamic process, the inventory cost function is approximated, and then the resulting approximate cost function is used as a value function in each stage of the approximate dynamic program. In this thesis, six different algorithms are developed for the CLSP, based on three different types of approximate dynamic programming approaches. The general methodology combines dynamic programming with data fitting and approximation techniques to estimate the inventory cost function at each stage of the dynamic program. Furthermore, three main algorithmic frameworks to compute a piecewise linear approximate inventory cost function for the CLSP are provided. The first approach integrates regression models into an approximate dynamic program. The second approach uses the information obtained by a partial dynamic process to approximate the piecewise linear inventory cost function. The third approach uses slope-check and bisection techniques to locate the breakpoints of the piecewise linear function in order to approximate the inventory cost function for the CLSP. The effectiveness of the proposed methods are analyzed on various types of CLSP instances with different cost and capacity characteristics. Computational results show that approximation approaches could considerably decrease the computational time required by the dynamic program and the integer program for different CLSP instances. Furthermore, in most cases, some of the proposed approaches can accurately capture the optimal solution of the problem.