Stochastic Scheduling in in-Forest Networks

In this paper we study the extremal properties of several scheduling policies in an in-forest network consisting of multiserver queues. Each customer has a due date, and we assume that service times at the different queues form mutually independent sequences of independent and identically distributed random variables independent of the arrival times and due dates. Furthermore, the network is assumed to consist of a mixture of nodes, some of which permit only non-preemptive service policies whereas the others permit preemptive resume policies. In the case of non-preemptive queues, service times may be generally distributed if there is only one server; otherwise the service times are required to be increasing in likelihood ratio (ILR). In the case of preemptive queues, service times are restricted to exponential distributions. Using stochastic majorizations and partial orders on permutations, we establish that, within the class of work conserving service policies, the stochastically smallest due date (SSDD) and the stochastically largest due date (SLDD) policies minimize and maximize, respectively, the vector of the customer latenesses of the first n customers in the sense of the Schur-convex order and some weaker orders, provided the due dates are comparable in some stochastic sense. It then follows that the first come-first served (FCFS) and the last come-first served (LCFS) policies minimize and maximize, respectively, the vector of the response times of the first n customers in the sense of the Schur-convex order. We also show that the FCFS and LCFS policies minimize and maximize, respectively, the vector of customer end-to-end delays in the sense of the strong stochastic order. Extensions to the class of non-idling policies and to the stationary regime are also given.