Asymptotically Optimal Routing and Servive Rate Allocation in a Multiserver Queueing System

J. George Shanthikumar and Susan H. Xu
Additional contact information
J. George Shanthikumar: University of California at Berkeley, Berkeley, California
Susan H. Xu: The Pennsylvania State University, University Park, Pennsylvania

Operations Research, 1997, vol. 45, issue 3, 464-469

Abstract: We consider a single stage queueing system with c heterogeneous servers. Customers arrive at this system according to a renewal process with mean 1/λ and squared coefficient of variation (scv) C a 2 . An incoming customer is routed to server i with probability θ i , ∑ i =1 c θ i = 1. The service times at server i are i.i.d random variables with mean 1/μ i , and scv C s i 2 . The holding cost rate of queue i is h i per customer, i = 1, 2, …, c . The problems of interest are twofold: (a) for a fixed service rate allocation μ i , ∑ i =1 c μ i = μ, find the routing probabilities, θ i *, ∑ i =1 c θ i * = 1, that minimize the average total holding cost; and (b) for fixed routing probabilities θ i , ∑ i =1 c θ i , and total service rate μ, find the service rate allocation μ i * = μδ i *, ∑ i =1 c δ i * = 1, that minimizes the average total holding cost of the system. For each problem, we characterize the optimal policy under heavy traffic conditions. We also derive the routing probabilities, θ̂ i (proportions δ̂ i ), i = 1, …, c , that are strongly asymptotically optimal. That is, the difference between the average total holding costs under θ̂ i , i = 1, …, c , and θ i *, i = 1, …, c (δ̂ i , i = 1, …, c , and δ i *, i = 1, …, c ) is bounded by a fixed constant independent of the routing probabilities (proportions) and the arrival rate. In addition, we discuss the necessity and sufficiency of the accurate knowledge of the means and scvs of the interarrival and service times m obtaining asymptotically optimal policies.

Keywords: queues; approximations; limit theorems; optimization; probability; stochastic model; applications (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.3.464 (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:45:y:1997:i:3:p:464-469

Access Statistics for this article

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