Research Archive

M/G/c queueing systems with multiple customer classes: Characterization and control of achievable performance under nonpreemptive priority rules

Awi Federgruen, Henri Groenevelt

Publication type: Journal article

Research Archive Topic: Leadership

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 2J - 1 inequalities. The special (polymatroidal) structure of this polyhedron, nevertheless, allows for efficient (O(J2 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.


Download PDF

Citation

Federgruen, Awi, and H. Groenevelt. "M/G/c queueing systems with multiple customer classes: Characterization and control of achievable performance under nonpreemptive priority rules." Management Science 34, no. 9 (September 1988): 1121-1138.


Each author name for a Columbia Business School faculty member is linked to a faculty research page, which lists additional publications by that faculty member.

Each topic is linked to an index of publications on that topic.