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

Avishai Mandelbaum () and Alexander L. Stolyar ()
Additional contact information
Avishai Mandelbaum: Industrial Engineering and Management, Technion, Haifa 32000, Israel
Alexander L. Stolyar: Bell Laboratories, Lucent Technologies, Murray Hill, New Jersey 07974

Operations Research, 2004, vol. 52, issue 6, 836-855

Abstract: 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 i )μ ij , 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.

Keywords: queues; diffusion models; networks; optimization; production/scheduling; sequencing/stochastic; networks; stochastic (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (75)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1040.0152 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:52:y:2004:i:6:p:836-855

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().