La th'eorie des files d'attente s'attache a` mod'eliser et a`
analyser de nombreuses situations diff'erentes en apparences, mais qui
relèvent n'eanmoins du sch'ema descriptif g'en'eral suivant. Des clients
arrivent a` intervalles al'eatoires dans un système comportant plusieurs
serveurs auxquels ils vont adresser une requête. La dur'ee du service
auprès de chaque serveur est elle-même al'eatoire. Après
avoir 'et'e servis, les clients quittent le système. Illustrons cette
description g'en'erale par des exemples sp'ecifiques.
Les clients sont les machines qui tombent en panne, et les
serveurs sont les m'ecaniciens qui s'occupent de la r'eparation.
Un système de files d'attente g'en'eral peut être
vu comme une boàýte noire dans laquelle les clients arrivent
suivant un processus quelconque, s'ejournent pour recevoir un ou plusieurs
services et finalement quittent le système. Ce système pourra
être compos'e d'une file simple ou d'un ensemble de files appel'e
réseau de files d'attente.
Definition. On appelle système de files d'attente
l'abstraction math'ematique d'un sujet qu'on peut d'ecrire par les 'el'ements
suivants :
1. Le flot des arriv'ees des clients.
2. La source des clients
3. Le comportement du client.
4. La loi de la dur'ee de service de chaque client.
5. La discipline de service
6. Le nombre de serveurs.
7. La capacit'e de la file.
· Le flot des arrivées des clients.
D'habitude, on suppose que les temps des inter arriv'ees sont
ind'ependants et identiquement distribu'es. En g'en'eral, le flot des arriv'ees
des clients est poissonnien, ce qui revient a` dire que la distribution du
temps des inter arriv'ees est exponentiel. Les clients peuvent arriver
individuellement ou par groupes. Un exemple d'arriv'ee par groupes est un poste
de police au niveau d'une frontière o`u les passagers ainsi que leurs
bagages sont soumis au contrôle.
· La source des clients.
Dans la plupart des cas, cette source est suppos'ee infinie.
Cependant, pour les modèles de fiabilit'e, la source des clients est
limit'ee (par exemple le cas d'un r'eparateur au sein d'une usine).
· Le comportement du client.
Certains clients peuvent être patients et vouloir
attendre pendant longtemps. Par contre d'autres s'impatientent et quittent
après un bout de temps. C'est le cas par exemple d'une centrale
t'el'ephonique o`u les clients raccrochent quand ils ont a` attendre longtemps
avant qu'une ligne ne soit disponible pour rappeler ult'erieurement.
· La durée de service.
En g'en'eral, on suppose que les dur'ees de service sont
ind'ependantes, identiquement distribu'ees et ind'ependantes des temps des
inter arriv'ees. Ce qui n'est toujours pas le cas. Par exemple, le temps de
traitement des machines au niveau d'un système de production peut
s''elever une fois le nombre de tâches a` ex'ecuter devient trop
grand.
· La discipline de service.
Les clients peuvent être servis individuellement ou par
groupe. Cependant, plusieurs possibilit'es existent quant a` l'ordre selon
lequel ils seront servis. Les principales disciplines de service sont :
* FIFO(First In First Out) : les entit'es sortent dans l'ordre
suivant lequel elles sont entr'ees. Cette discipline est la plus utilis'ee.
* LIFO(Last In First Out) : la dernière entit'e dans la
file est la première a` être servie. C'est le cas de la pile au
niveau des ordinateurs.
* Random : toutes les entit'es ont la même probabilit'e
d'être servies en premier.
* Prioritaire : les entit'es sont servies suivant un attribut
qui leur est associ'e. Par exemple l'entit'e ayant le plus court temps de
traitement d'abord.
· Le nombre de serveur.
Il peut être 'egale a` l'unit'e ou plus selon la nature du
service a` fournir.
· La capacitéde la file.
Dans pas mal de cas, la file est suppos'ee infinie.
Cependant, il n'est pas rare de rencontrer des situations dans lesquelles elle
est finie (par exemple le cas d'une salle d'attente).
Pour la classification des systèmes d'attente, on a
recours a` la notation symbolique introduite par Kendall au d'ebut des ann'ees
cinquante. Cette notation comprend quatre symboles rang'es dans l'ordre
A/B/s/N
o`u
A = distribution des temps entre deux arriv'ees successives,
B = distribution des dur'ees de service,
s = nombre de postes de service en parallèle,
N = capacit'e du système
On peut toutefois faire abstraction du dernier symbole lorsque N
= 8. Pour sp'ecifier les distributions A et B, les symboles suivants sont
utilis'es :
M = distribution exponentielle,
Ek = distribution d'Erlang d'ordre k,
Hk = distribution hyperexponentielle,
C = distribution g'en'erale,
D = cas d'eterministe
Notion de classes de clients
Une file d'attente peut être parcourue par diff'erentes
classes de clients. Ces diff'erentes classes se distinguent par :
- des processus d'arriv'ee diff'erents;
- des temps de service diff'erents;
- un ordonnancement dans la file d'attente en fonction de leur
classe.
Pour d'efinir une file multiclasse, il y a lieu de pr'eciser
pour chaque classe de clients le processus d'arriv'ee et la distribution du
temps de service associ'es ainsi que la manière dont les clients des
diff'erentes classes s'ordonnent dans la file.
