Optimal scheduling in some multi-queue single-server systems

Zhen Liu 1 Philippe Nain 1
1 MEVAL - Modeling and Performance Evaluation of Computer Systems
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In this paper we address the problem of optimal scheduling in a multi-queue single-server (MQSS) model. The server visits N queues in an arbitrary manner. Each queue is visited for a random period of time whose duration is sampled in advance. At the end of a visit period, either all customers of the attended queue leave the system (variant I), or only customers that were present in the queue upon the arrival of the server leave the system (variant II). A scheduling policy is a rule that selects the next queue to be visited by the server. When the controller has no information on the state of the system, it is shown, under homogeneous arrival assumptions- , that a cyclic policy minimizes the expected number of customers in the system. When the controller knows the number of customers in each queue, it is shown that the so-called most customers first (MCF) policy minimizes, in the sense of strong stochastic ordering, the vector of the number of customers in each queue whose components are arranged in decreasing order. These results hold for variants I and II, and are obtained under fairly weak statistical assumptions. This model has potential applications in videotex and time division multiple access systems.
Type de document :
Rapport
[Research Report] RR-1147, INRIA. 1989
Liste complète des métadonnées

https://hal.inria.fr/inria-00075412
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 18:09:56
Dernière modification le : samedi 27 janvier 2018 - 01:31:24
Document(s) archivé(s) le : mardi 12 avril 2011 - 23:00:31

Fichiers

Identifiants

  • HAL Id : inria-00075412, version 1

Collections

Citation

Zhen Liu, Philippe Nain. Optimal scheduling in some multi-queue single-server systems. [Research Report] RR-1147, INRIA. 1989. 〈inria-00075412〉

Partager

Métriques

Consultations de la notice

157

Téléchargements de fichiers

85