File M/M/1

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.

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

Modélisation

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 dont l'espace d'états est le nombre de clients dans le système (en attente ou en train d'être traités).

Les clients arrivent selon une loi exponentielle de taux λ, changeant l'état du système de i à i + 1.
Le taux de service suit une loi exponentielle de paramètre μ.
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.

La chaîne sous-jacente est la suivante^[1]^,^[2] :

Et la matrice de taux de transition est :

Q={\begin{pmatrix}-\lambda &\lambda \\\mu &-(\mu +\lambda )&\lambda \\&\mu &-(\mu +\lambda )&\lambda \\&&\mu &-(\mu +\lambda )&\lambda &\\&&&&\ddots \end{pmatrix}}

Résultats

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

Stabilité et régime stationnaire

La file est stable si et seulement si le taux d'arrivée est strictement plus petit que le taux de départ^[1], i.e. $\lambda <\mu$ . On pose : $\rho ={\frac {\lambda }{\mu }}$ .

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^[1] : ${\textstyle \pi _{i}=(1-\rho )\cdot \rho ^{i}}$ , et le nombre moyen de client est ${\frac {\rho }{1-\rho }}$ .

Régime transitoire

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « M/M/1 queue » (voir la liste des auteurs).

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

[sur-1] {a b et c} Frédéric Sur, « Recherche opérationnelle : Files d'attente 1 », sur Mines de Nancy, 2013.

[2] (en) Chuan Shi, Stanley Gershwin, Duane Boning, « Introduction to Manufacturing Systems : M/M/1 Queue lecture notes », sur MIT Opencourseware.

[1]

[2]

v · m Théorie des files d'attente
Nœuds de file d'attente uniques	D/M/1 queue (en) M/D/1 queue (en) M/D/c queue (en) file M/M/1 Burke's theorem (en) M/M/c queue (en) M/M/∞ queue (en) M/G/1 queue (en) Formule de Pollaczek-Khinchine Matrix analytic method (en) M/G/k queue (en) G/M/1 queue (en) G/G/1 queue (en) Kingman's formula (en) Lindley equation (en) Fork–join queue (en) Bulk queue (en)
Processus d'arrivée	Processus de Poisson Markovian arrival process (en) Rational arrival process (en)
File de réseau	Jackson network (en) Traffic equations (en) Gordon–Newell theorem (en) Mean value analysis (en) Buzen's algorithm (en) Kelly network (en) G-network (en) BCMP network (en)
Politique de services	First in, first out Last in, first out Processor sharing (en) Shortest job first Shortest remaining time
Concepts clés	Processus de Markov à temps continu Notation de Kendall Théorie des files d'attente Product-form solution (en) Balance equation (en) Quasireversibility (en) Flow-equivalent server method (en) Arrival theorem (en) Decomposition method (queueing theory) (en) Beneš method (en)
Limite des théorèmes	Fluid limit (en) Mean field theory Heavy traffic approximation (en) Reflected Brownian motion (en)
Extensions	Fluid queue (en) Layered queueing network (en) Polling system (en) Adversarial queueing network (en) Loss network (en)