Optimal control of a multiclass queueing system when customers can change types

Ping Cao, Jingui Xie

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


It is well known that the (Formula presented.) -rule is optimal for serving multiple types of customers to minimize the expected total waiting cost. What happens when less valuable customers (those with lower (Formula presented.)) can change to valuable ones? In this paper, we study this problem by considering two types of customers. The first type of customers is less valuable, but it may change to the second type (i.e., more valuable customers) after a random amount of time. The resulting problem is a continuous-time Markov decision process with countable state space and unbounded transition rates, which is known to be technically challenging. We first prove the existence of optimal non-idling stationary policies. Based on the smoothed rate truncation, we derive conditions under which a modified (Formula presented.) -rule remains optimal. For other cases, we develop a simple heuristic policy for serving customers. Our numerical study shows that the heuristic policy performs close to the optimal, with the worst case within 2.47 % of the optimal solution and 95 % of the examples within 1 % of the optimal solution.

Original languageEnglish
Pages (from-to)285-313
Number of pages29
JournalQueueing Systems
Issue number3-4
StatePublished - 1 Apr 2016
Externally publishedYes


  • Change in customer type
  • Markov decision process
  • Multiclass queueing system
  • Smoothed rate truncation method
  • Unbounded transition rates


Dive into the research topics of 'Optimal control of a multiclass queueing system when customers can change types'. Together they form a unique fingerprint.

Cite this