Module C1.7 : Processus stochastique et simulation
Processus de naissance et de mort
File d'attente markovienne

Processus de naissance et de mort en équilibre
Interprétation intuitive
Condition d'existence d'équilibre
Exercices
Notation X/Y/s/s
Système M/M/1
Système M/M/s
Système M/M/1/K
Système M/M/s/s
Système M/M/ 
Système fermés
Critère d'applicabilité des modèles markoviens
Etude des arrivées
Etude des services
Exercices


Auteur(s) : Nasser Saheb - IUP Miage Bordeaux
Date de dernière modification : 06 octobre 2004

De nombreux systèmes d'attente peuvent être modélisés par un processus de naissance et de mort. Ces systèmes ont comme particularités communes un processus d'arrivée de type poissonnien et une durée de service suivant une loi exponentielle. On pourra avoir un nombre quelconque de serveurs. Le système peut adopter une discipline fixée sur la nature prioritaire d'ordre de service. Finalement, le système peut admettre un nombre fini ou infini d'usagers au total.

Notation X/Y/s/s

Un système d'attente est caractérisé par la notation de Kendall X/Y/s/K, où :

La notation peut inclure aussi la discipline de service : FIFO = PAPS (Premier Arrivé, Premier Servi), LIFO = DAPS (Dernier Arrivé, Premier Servi), ou P (Prioritaire).

 

 

Système M/M/1

Le processus d'arrivée d'usagers est de Poisson de taux   et la durée de service est exponentielle de paramètre  . On suppose   et   strictement positifs.   est appelé taux de service. L'espérance mathématique de la durée de service est l'inverse du taux de service. Le processus se modélise par un processus de naissance et de mort avec :

 

Nous avons le diagramme de transition suivant :

 

Suivant les résultats de la séquence précédente, le processus est ergodique si et seulement si  , i.e. le taux de service est supérieur à celui d'arrivée, et les équations sur les probabilités stationnaires deviennent alors :

 

Par ailleurs, la somme des probabilités vaut 1, et donc :

 

Par conséquent :

 

D'où

 

et

 

Soit  . C'est la probabilité stationnaire pour que le système soit occupé.   est appelé taux d'occupation ou facteur d'utilisation du système.

La distribution stationnaire s'écrit alors :

 

C'est une distribution géométrique. Elle possède la propriété caractéristique « sans mémoire » ; si N est la v.a. nombre d'usagers dans le système, on a :

 

Le nombre d'usagers dans le système   vaut :

 

On a la courbe variation suivante pour   en fonction de  .

 
Temps d'attente

Le temps passé par usager dans le système est par définition la somme de temps d'attente passé dans la file et celui du service. C'est une v.a. qui dépend évidemment de la discipline imposée. Mais le temps moyen d'attante par usager est indépendant de la discipline.

Considérons un intervalle de temps [0, L] suffisamment grand pour qu'on puisse identifier le taux d'arrivée   avec le ratio entre le nombre d'usagers, passés dans le système, et la longueur de l'intervalle L. Soit N(t), pour  , le nombre d'usagers dans le système, à l'instant t.

 

Soit A l'aire de la surface comprise entre la courbe de variation de N(t) et l'axe  . On a d'une part :

 

D'autre part cette aire est le produit du nombre total d'usagers, passés dans le système, et le temps moyen d'attente  . Comme ils sont arrivés de taux  , ce nombre vaut asymptotiquement  . On a donc :

   où  .

C'est la formule de Little. Elle est valable dans tout système d'attente, si l'on peut identifier   avec  .

Dans le cas du système M/M/1, le temps moyen d'attente vaut :

 

Le temps moyen passé dans la file   est l'espérance mathématique du temps qu'un usager quelconque doit attendre dans la file (en régime stationnaire) pour être servi. Il vaut donc en général la différence entre   et le temps moyen de service :  .

Dans le cas du systéme M/M/1 avec la discipline PAPS (Premier Arrivé , Premier Servi), un raisonnement direct aboutit à une formule simple pour  . En effet, un usager qui vient d'arriver, trouve en moyenne   usagers dans le système. Il doit donc attendre en moyenne :

 

unités de temps pour être servi.

Notons que ceci est vrai en vertu de la propriété sans mémoire de la durée de service.

 

 
Suite de la séquence (3/9)