Two-class constrained optimization with applications to queueing control

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.