En théorie des files d'attente, une file M/M/1 est un type de file d'attente classique. Le terme M/M/1 utilise la notation de Kendall, et signifie que les travaux à effectuer (ou les clients) arrivent à un intervalle qui suit une loi exponentielle, sont mis en attente dans une file et sont traités dans l'ordre d'arrivée, selon une loi elle aussi exponentielle.

Une file M/M/1.

C'est l'une des files d'attente les plus élémentaires.

Modélisation

modifier

La file M/M/1 est un exemple de processus de Markov à temps continu. Une file M/M/1 peut être vue comme un processus stochastique. Un état correspond à un nombre de clients dans la file (en attente ou en train d'être traités). Il y a donc une infinité d'états : 0, 1, 2, 3, etc.

  • Les clients arrivent selon une loi exponentielle de taux λ. Quand un client arrive, l'état du système passe de i à i + 1 (un client de plus).
  • Le taux de service suit une loi exponentielle de paramètre μ, où 1/μ est la durée moyenne du service.
  • Un serveur traite les clients un à un selon le mode premier arrivé, premier servi. Quand le service est fini, les clients quittent le système et le processus passe de l'état i à l'état i - 1 (un client de moins).

La chaîne de Markov à temps continu sous-jacente est la même que pour un processus de naissance et de mort[1] :

 

La matrice de taux de transition possède une infinité de lignes et de colonnes et est :

 .

Résultats

modifier

De nombreuses quantités peuvent être calculées explicitement.

Stabilité et régime stationnaire

modifier

La file est stable si et seulement si le taux d'arrivée est strictement plus petit que le taux de départ[2], i.e.  . On pose :  .

Le nombre de clients dans le système pendant le régime stationnaire suit une loi géométrique. Plus précisément, la probabilité d'être dans l'état i, c'est-à-dire d'avoir i client dans le système est[2] : , et le nombre moyen de client est  .

Régime transitoire

modifier

Notes et références

modifier
  1. (en) Chuan Shi, Stanley Gershwin, Duane Boning, « Introduction to Manufacturing Systems : M/M/1 Queue lecture notes », sur MIT Opencourseware.
  2. a et b Frédéric Sur, « Recherche opérationnelle : Files d'attente 1 », sur Mines de Nancy, .