M/G/c Queueing Systems with Multiple Customer Classes: Characterization and Control of Achievable Performance Under Nonpreemptive Priority Rules

A. Federgruen and H. Groenevelt
Additional contact information
A. Federgruen: Graduate School of Business, Columbia University, New York, New York 10027
H. Groenevelt: Simon School of Business Administration, University of Rochester, Rochester, New York 14627

Management Science, 1988, vol. 34, issue 9, 1121-1138

Abstract: This paper considers an M/G/c queueing system serving a finite number (J) of distinct customer classes. Performance of the system, as measured by the vector of steady-state expected waiting times of the customer classes (the performance vector), may be controlled by adopting an appropriate priority discipline. We show that the performance space, the set of performance vectors which are achievable under some nonpreemptive work conserving priority rule, is a polyhedron described by 2 J - 1 inequalities. The special (polymatroidal) structure of this polyhedron, nevertheless, allows for efficient (O(J 2 log J)) procedures to minimize any convex (separable) function of the performance vector. Linear objectives are shown to be minimized by absolute priority rules, thus generalizing a well-known result for M/G/1 systems. We also show that each point in the performance space may be achieved by a unique, generalized dynamic priority rule, specified by J - 1 parameters, which may be determined by the recursive solution of J - 1 single variable quadratic equations. This class of rules contains the absolute priority rules and the (pure) dynamic rules as special cases. Our results are accurate up to one, extremely accurate, approximation and completely exact for M/G/1 and M/M/c systems as well as in heavy traffic.

Keywords: queueing systems; nonpreemptive priority rules; customer classes (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.34.9.1121 (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:ormnsc:v:34:y:1988:i:9:p:1121-1138

Access Statistics for this article

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