Estimation de l'erreur de troncature de l' espace d'états du système d'attente m/m/1: méthode de stabilité forte

2

Systémes de files d'attente

2.1 Introduction et structure d'un système d'attente

Les premiers résultats sur les systèmes de files d'attente ont étéproposés par l'ingénieur électricien Erlang au début du vingtième siècle, dans le but de décrire les phénomènes de congestion et d'attente ont étéutilisées dans la modélisation des systèmes de production et des systèmes informatique [14].

D'une manière générale, une file d'attente est la donnée d'une (ou plusieurs) unitéde service o`u arrivent des clients qui demandent une certaine durée d'utilisation de cette unité. Quand les clients ne peuvent accéder a` cette unitéde service, ils attendent dans une file d'attente (qui peut être éventuellement de capacitélimitée).

FIGURE 2.1 - Système de files d'attente a` un seul serveur

2.1.1 Classification et formalisation d'un système de files d'attente

En g'en'eral, une file d'attente est d'efinie par :

1) Un processus d'arriv'ee de clients, i.e. une suite croissante {T_n, m = 0}, o`u T<sub>n</sub> est l'instant d'arriv'ee du <sup>m`eme</sup> client. Le processus d'arriv'ee est alors la fonction de comptage associ'ee aux temps d'inter-arriv'ees. Si de plus la loi est une exponentielle, alors le processus des arriv'ees est un processus de Poisson, et on utilise la notation M pour souligner le caractère markovien.

2) Une suite de r'eels {S_n, m = 0} avec S_n est la dur'ee de service requise par le ^m`eme client. Nous verrons que dans ce cas, si le processus d'arriv'ee est un processus de Poisson, alors l''evolution de la taille de la file d'attente est une chaàýne de Markov.

3) Une discipline de service . Distributions des inter-arrivées

Les symboles utilis'es pour d'ecrire les processus d'entr'ee et de service sont :

- M : Loi exponentielle (processus de Markov);

- G : Loi g'en'erale;

- GI : Loi-g'en'erale ind'ependante;

- D : Loi constante (d'eterministe);

- Ek : Loi Erlang-k;

- Hk : Loi hyper exponentielle d'ordre k;

- Ck : Loi de Cox-k.

Discipline de service

- FIFO(First In First Out) : Les clients sont servis suivant leur ordre d'arriv'ee; - LIFO(Last In First Out) Le dernier client arriv'e est le premier servi;

- Services partagées Tous les clients sont servis en même temps, mais avec une vitesse inversement proportionnelle au nombre de clients;

- Aléatoire Le prochain client de la file d'attente a` être servi est choisi au hasard;

- SPT (Shortest Processing Time) Le prochain client de la file d'attente a` être servi est celui qui a la requête la plus courte;

-

...

Ces trois 'el'ements sont consid'er'es comme les paramètres essentiels du système, Kendall [15] a propos'e de repr'esenter les modèles stochastiques de files d'attente sous forme d'un sextuplet