Scheduling Flexible Servers with Convex Delay Costs: Heavy- Traffic Optimality of the Generalized cmu-Rule

We consider a queueing system with multi-type customers and flexible (multi-skilled) servers that work in parallel. Let mu_ij denote the service rate of type i customers by server j (the reciprocal of an average service time); mu_ij= 0 indicates that server j can not serve type i. We analyze the system in heavy traffic [10], seeking to minimize either queueing or waiting costs. To this end, assume that the queue of type i incurs a queueing cost at rate C_i(Q_i), which is an increasing convex function C_i(.) of the queue length Q_i. Then, we show that a simple generalized cmu-rule [19] minimizes queueing costs, asymptotically, over essentially all scheduling disciplines, preemptive or non-preemptive. Specifically, when becoming idle at time t, server j chooses for service the longest-waiting type i customers from the subset argmax_i C'_i(Q_i(t)) mu_ij . (C'_i is the derivative of C_i.) Alternatively, each type i customer could incur a waiting cost C_i(W_i), where W_i is its sojourn time. Then, waiting costs are asymptotically minimized by serving type i from the subset argmax_i C'_i(W_i(t)) mu_ij , where W_i(t) is the head-of-the-line waiting time in queue i at time t.