Approximate dynamic programming for dynamic capacity allocation with multiple priority levels
Authors:
- 30 November 2010
- journal article
- research article
- Published by Taylor & Francis in IIE Transactions
- Vol. 43 (2) , 129-142
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
This publication has 11 references indexed in Scilit:
- A New Dynamic Programming Decomposition Method for the Network Revenue Management Problem with Customer Choice BehaviorProduction and Operations Management, 2010
- An Approximate Dynamic Programming Approach to Network Revenue Management with Customer ChoiceTransportation Science, 2009
- Using Lagrangian Relaxation to Compute Capacity-Dependent Bid Prices in Network Revenue ManagementOperations Research, 2009
- Computing protection level policies for dynamic capacity allocation problems by using stochastic approximation methodsIIE Transactions, 2009
- Dynamic Multipriority Patient Scheduling for a Diagnostic ResourceOperations Research, 2008
- Revenue Management for a Primary-Care Clinic in the Presence of Patient ChoiceOperations Research, 2008
- Relaxations of Weakly Coupled Stochastic Dynamic ProgramsOperations Research, 2008
- Approximate Dynamic Programming2007
- Reservation Planning for Elective Surgery Under Uncertain Demand for Emergency SurgeryManagement Science, 1996
- Stochastic programs over trees with random arc capacitiesNetworks, 1994