Lagrangian relaxation and constraint generation for allocation and advanced scheduling

Gocgun Y., Ghate A.

Computers and Operations Research, vol.39, no.10, pp.2323-2336, 2012 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 39 Issue: 10
  • Publication Date: 2012
  • Doi Number: 10.1016/j.cor.2011.11.017
  • Journal Name: Computers and Operations Research
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.2323-2336
  • Keywords: Approximate dynamic programming, Resource allocation, Scheduling
  • Istanbul Medipol University Affiliated: No


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 advanced scheduling, 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 Lagrangian relaxation and constraint generation 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 advanced scheduling than for allocation scheduling. © 2011 Elsevier Ltd. All rights reserved.