The authors consider a multiclass GI/G/1 queueing system, operating under an arbitrary work-conserving scheduling policy ;. They derive an invariance relation for the Cesaro sums of waiting times under ;, which does not require the existence of limits of the Cesaro sums. This allows the authors to include important classes in the set of admissible policies such as time-dependent and adaptive policies. For these classes of policies, ergodicity is not known a priori and may not even exist. Therefore, the classical invariance relations that involve statistical averages do not hold. For an M/G/1 system, the authors derive inequalities involving the Cesaro sums of waiting times that further characterize the achievable performance region of the system.
