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

摘要

It is well known that the cμ-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 cμ) 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 cμ-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.