Two-class constrained optimization with applications to queueing control

Cory Girard, Linda V. Green, Mark E. Lewis, Jingui Xie

Research output: Contribution to journalArticlepeer-review


Constrained Markov decision process (CMDP) is a methodology that has not seen wide applications in the literature, but is a more natural specification for modeling preferences in modern service systems. In this paper we present a general framework for solving two-class CMDPs. In particular, we show that CMDPs can be solved by using the Lagrangian dual to specify a particular unconstrained problem. If an appropriate Lagrange multiplier can be discerned, structural results can be exploited to solve the original CMDP with the appropriate structure. We show that for two queues in parallel or two queues in series, the framework leads to simple threshold-like optimal policies. The results in each case are used to develop heuristics for analogous problems with abandonments with applications to health care, call centers, and manufacturing systems. The efficacy of the heuristics is verified in each case via a detailed numerical study.

Original languageEnglish
Pages (from-to)397-422
Number of pages26
JournalNaval Research Logistics
Issue number5
StatePublished - Aug 2023
Externally publishedYes


  • constrained Markov decision processes
  • modeling preferences
  • two class CMDP


Dive into the research topics of 'Two-class constrained optimization with applications to queueing control'. Together they form a unique fingerprint.

Cite this