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

Abstract

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
Volume82
Issue number3-4
DOIs
StatePublished - 1 Apr 2016
Externally publishedYes

Keywords

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

Fingerprint

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