Approximate dynamic programming for dynamic capacity allocation with multiple priority levels

Abstract

This article considers a quite general dynamic capacity allocation problem. There is a fixed amount of daily processing capacity. On each day, jobs of different priorities arrive randomly and a decision has to made about which jobs should be scheduled on which days. Waiting jobs incur a holding cost that is a function of their priority levels. The objective is to minimize the total expected cost over a finite planning horizon. The problem is formulated as a dynamic program, but this formulation is computationally difficult as it involves a high-dimensional state vector. To address this difficulty, an approximate dynamic programming approach is used that decomposes the dynamic programming formulation by the different days in the planning horizon to construct separable approximations to the value functions. Value function approximations are used for two purposes. First, it is shown that the value function approximations can be used to obtain a lower bound on the optimal total expected cost. Second, the value function approximations can be used to make the job scheduling decisions over time. Computational experiments indicate that the job scheduling decisions made by the proposed approach perform significantly better than a variety of benchmark strategies.

Keywords:

• Approximate dynamic programming
• capacity allocation
• scheduling

Acknowledgements

The authors thank the associate editor and two anonymous referees whose suggestions substantially improved the article. The work of the second author was partially supported by the National Science Foundation under grant CMMI 0825004.