Stochastic scheduling in In-Forest Networks

Abstract : In this paper we study the extremal properties of several scheduling policies in a queueing network consisting of multi-server queues where the topology is that of an in-forest. Associated with each customer is a due date. We assume that service times at the different queues form mutually independant sequences of independent and identically distributed random variables 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 only permit non-preemptive service policies whereas the others permit preemptive resume policies. In the case of non-preemptive queues, service times may be generally distributed provided 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 be exponentially distributed random variables. Using stochastique majorization and a partial order on permutations, we establish that, within the class of work conserving service policies, the smallest due date (SDD) and largest due date (LDD) policies minimize and maximise, respectively, the vector of the customer latenesses of the first n customers in the sense of the Schur-convex order. From this we conclude that the first come first serve (FCFS) and last come first serve (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. If due dates are only known stochastically, then we establish that the stochastic SDD and the stochastic LDD policies minimize and maximize the vector of lateness according to a weaker ordering. 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. When idling policies are under consideration, the FCFS policy is shown to be optimal for various performance metrics in the case that all queues permit preemptive resume policies and all service times are exponentially distributed. Extension of these results to the stationary regime are also given.
Type de document :
Rapport
[Research Report] RR-1719, INRIA. 1992
Liste complète des métadonnées

https://hal.inria.fr/inria-00076957
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 29 mai 2006 - 11:41:10
Dernière modification le : samedi 27 janvier 2018 - 01:31:02
Document(s) archivé(s) le : vendredi 13 mai 2011 - 22:13:46

Fichiers

Identifiants

  • HAL Id : inria-00076957, version 1

Collections

Citation

Zhen Lui, Don Towsley. Stochastic scheduling in In-Forest Networks. [Research Report] RR-1719, INRIA. 1992. 〈inria-00076957〉

Partager

Métriques

Consultations de la notice

179

Téléchargements de fichiers

59