M/G/c Queueing Systems with Multiple Customer Classes: Characterization and Control of Achievable Performance Under Nonpreemptive Priority Rules
研究多类顾客的M/G/c排队系统，刻画了在非抢占工作守恒优先规则下可达的期望等待时间向量集合，并给出高效优化方法，对排队系统设计者有用。
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.