Advances in Engineering Advances in Engineering features breaking research judged by Advances in Engineering advisory team to be of key importance in the Engineering field. Papers are selected from over 10,000 published each week from most peer reviewed journals.
Computers & Operations Research, Volume 39, Issue 10, October 2012, Pages 2323-2336
Yasin Gocgun, Archis Ghate
Sauder School of Business, University of British Columbia, Vancouver, Canada
Industrial and Systems Engineering, University of Washington, Seattle, USA
Abstract
Diverse applications in manufacturing, logistics, health care, telecommunications, and computing require that renewable resources be dynamically scheduled to handle distinct classes of job service requests arriving randomly over slotted time. These dynamic stochastic resource scheduling problems are analytically and computationally intractable even when the number of job classes is relatively small. In this paper, we formally introduce two types of problems called allocation and advancedscheduling, and formulate their Markov decision process (MDP) models. We establish that these MDPs are “weakly coupled” and exploit this structural property to develop an approximate dynamic programming method that uses Lagrangianrelaxation and constraintgeneration to efficiently make good scheduling decisions. In fact, our method is presented for a general class of large-scale weakly coupled MDPs that we precisely define. Extensive computational experiments on hundreds of randomly generated test problems reveal that Lagrangian decisions outperform myopic decisions with a statistically significant margin. The relative benefit of Lagrangian decisions is much higher for advancedscheduling than for allocationscheduling.
