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

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² 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.