Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized cμ-rule

Avishai Mandelbaum, Aleksandr Stolyar

Research output: Contribution to journalArticlepeer-review


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 cμ-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 ε arg max i C′ i(Q iij, where μ ij is the average service rate of type i customers by server j. An analogous version of the generalized cμ-rule 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)μ ij is maximal, where D and i are the customer's sojourn time and type, respectively.

Original languageEnglish (US)
Pages (from-to)836-855
Number of pages20
JournalOperations Research
Issue number6
StatePublished - Nov 1 2004
Externally publishedYes


  • Networks: stochastic
  • Production/scheduling: sequencing/stochastic
  • Queues: diffusion models, networks, optimization

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized cμ-rule'. Together they form a unique fingerprint.

Cite this