Accueil > Informatique > RCP101 : Recherche opérationnelle et aide à la décision > Les files d’attentes
Les files d’attentes
lundi 27 juillet 2009, par
I/ Définition
Une file d’attente est caractérisée par :
Un flot d’arrivées
Un mécanisme de service
Une file d’attente
Une discipline de service
Capacité de la file d’attente :
nombre de places possibles : limité ou illimité.
Si capacité limitée : les clients supplémentaires sont perdus ou rejoignent une autre file d’attente.
Le nombre de clients dans le système est différent du nombre de clients dans la file d’attente
Discipline de service :
- règle d’ordonnancement des clients au service.
- FIFO : first in first out (exemple file d’attente à la sécu, 1er arrivé 1er servie)
- LIFO : Last in first out (ex : l’ascenseur : dernier rentré, premier sortie)
- PS : processor sharing, un serveur donne à chaque client en attente une “tranche” de service. (c’est du partage de ressources, le processeur accomplit un bout de tache sur un client puis passe au suivant ... )
- ALEA un serveur libre choisit un client au hasard dans la file
- Priorité : on ajoute une suite Un, n appartient à N+, au flot des arrivées où Un est une variable aléatoire prenant ses valeurs dans l’ensemble des classes de priorités P. Un=i, signifie que le neme client, arrivant au temps Tn est de la classe i.
- Priorité préemptive : le programme preemptif passe en premier devant tous les autres et est servi en premier
Notation de KENDALL A/B/C/D/E
A : statistique du processus d’arrivée (M = markovien ; D=déterministe ; G=générale)
B : statistique des lois de service (M = markovien ; D=déterministe ; G=générale)
C : nombre de serveurs
D : nombre de clients dans le système
E : discipline du service
M/M/1 ==> Modèle le plus classique
M/M/5/20
M///5/infini/LIFO
LOI DE LITTLE
cette loi part du principe que sur le terme, la vitesse d’arrivée = vitesse de traitement
HYPOTHESES
- Lorsqu’un client, ayant terminé son service, quitte le système, il laisse, en moyenne, derrière lui, un nombre de clients égal à E(k). Ce client a trouvé en arrivant E(k) clients déjà présents et a passé dans le système un temps, E(T).
- Nous supposons que :
- Le nombre moyen des arrivées est égal au nombre moyen des départs du système.
- La longueur moyenne de la file lors des arrivées est égale à la longueur moyenne de la file lors des départs
ENONCE
- Si on appelle, l, le taux moyen des arrivées on a :
Nombre moyen de clients arrivés pendant le séjour du client dans le système =
E(t) = nombre moyen de clients qu’il laisse
Et en régime permanent, si T temps passé dans la file :
: nombre de client dans le système
: taux moyen d’arrivé des clients
: temps passé dans la file
VALIDITE
Régime permanent
Les formules de Little sont valides pour les files G/G/S. Elles ont un caractère très général. En effet, il n’ y a aucune restriction quant à :
la loi d’arrivée, la loi des services, le nombre de serveurs.
Elles peuvent prendre en compte le cas où il existe plusieurs classes de clients mais la discipline de service doit être définie, nous avons considéré la discipline FIFO.
II/ File M/M/1
M/M/1 = statistique du processus d’arrivée : markovien / statistique des lois de service : markovien / 1 serveur
Les formules à retenir :
État : nombre de clients, k, dans le système
: probabilité d’avoir 0 clients dans la file d’attente
Taux de trafic, r (charge, activité du serveur) :
: taux de traffic
: taux moyen d’arrivée des clients
: taux moyen de traitement, débit du serveur, taux de service du serveur
- Condition de stabilité :
- activité du serveur <1
-
- Débit d’entrée < débit du serveur
- Temps moyen inter-arrivée > temps de service moyen
- Si serveur saturé (
—>1) :
- La distribution des intervalles de temps séparant deux départ consécutifs de la file saturée tend vers la distribution des temps de service
Nombre moyen de clients dans le système, N
: taux de traffic
: Nombre de client dans le système
Nombre moyen de clients dans la file, E(v)
: Taux de traffic
: Nombre moyen de client dans la file
Temps moyen, T, passé par un client dans le système
: taux de traffic
: temps passé par un client dans le système
: taux moyen de traitement, débit du serveur, taux de service
III/ File M/M/S
M/M/S = statistique du processus d’arrivée : markovien / statistique des lois de service : markovien / S serveurs
Les formules à retenir :
Taux de trafic
: taux de traffic
: taux moyen d’arrivée des clients
: taux moyen de traitement, débit du serveur, taux de service du serveur
S : Nombre de serveurs
Nombre moyen de guichets, g, occupés :
: Nombre de guichets occupés
: taux moyen d’arrivée des clients
: taux moyen de traitement, débit du serveur, taux de service du serveur
Nombre moyen de clients, v , dans la file :
k>s, k : nombre de clients, s nombre de serveurs
: nombre moyen de clients dans la file
: taux moyen d’arrivée des clients
: taux moyen de traitement, débit du serveur, taux de service du serveur
: probabilité qu’il y ait 0 client dans le système
S : nombre de serveurs
Temps d’attente moyen, tf , dans la file :
: temps d’attente moyen des clients dans la file
: taux moyen d’arrivée des clients
: taux moyen de traitement, débit du serveur, taux de service du serveur
: probabilité qu’il y ait 0 client dans le système
S : nombre de serveurs
Nombre moyen de clients dans le système
: Nombre de client dans le système
: temps d’attente moyen des clients dans la file
: taux moyen d’arrivée des clients
: taux moyen de traitement
Temps d’attentes dans le système
: temps d’attente dans le système
: Nombre de client dans le système
: taux moyen d’arrivée des clients