Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized cμ-rule
成果类型：
Article
署名作者：
Mandelbaum, A; Stolyar, AL
署名单位：
Technion Israel Institute of Technology; Alcatel-Lucent; Lucent Technologies; AT&T
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1040.0152
发表日期：
2004
页码：
836-855
关键词：
摘要：
We consider a queueing system with multitype customers and flexible (multiskilled) servers that work in parallel. If Q(i) is the queue length of type i customers, this queue incurs cost at the rate of C-i(Q(i)), where C-i((.)) is increasing and convex. We analyze the system in heavy traffic (Harrison and Lopez 1999) and show that a very simple generalized cmu-rule (Van Mieghem 1995) minimizes both instantaneous and cumulative queueing costs, asymptotically, over essentially all scheduling disciplines, preemptive or non-preemptive. This rule aims at myopically maximizing the rate of decrease of the instantaneous cost at all times, which translates into the following: when becoming free, server j chooses for service a type i customer such that i is an element of arg max(i) C-i'(Q(i))mu(ij), where mu(ij) is the average service rate of type i customers by server j. An analogous version of the generalized cmu-rude asymptotically minimizes delay costs. To this end, let the cost incurred by a type i customer be an increasing convex function C-i(D) of its sojourn time D. Then, server j always chooses for service a customer for which the value of C-i'(D)mu(ij) is maximal, where D and i are the customer's sojourn time and type, respectively.