Comparisons of service disciplines in a tandem queueing network with real time constraints

In this paper the authors study the extremal properties of the stationary customer lag times in tandem G/GI/1 networks under different service disciplines in terms of convex and increasing convex orderings. Each customer carries a reference time with it and the lag time is defined to be the difference between the time that the customer departs from the system and its reference time. The authors show that among the class of work conserving non-preemptive service disciplines that are service time independent, the service discipline that schedules customers with the smallest reference times (SR) and the service discipline that schedules the customer with the largest reference time (LR) provide the minima and maxima respectively. If they restrict themselves to the subsets of these disciplines that do not use reference times but do use arrival times in making scheduling decisions, then the first in first out (FIFO) and last come first serve (LCFS) service disciplines provide the minima and maxima respectively. The authors also present similar results for G/M/1 queue when preemptions are allowed and for the class of service disciplines that are not work conserving.