Simulateur de file d'attente (M/M/1)

taux d'arrivée, taux de service et stabilité de la file

Exemple résolu — Simulateur de file d'attente (M/M/1)

Utilisation ρ	0,750
Prédiction M/M/1 pour L	3,000
Taux d'arrivée produit par l'exécution	3,0084
Prédiction de la loi de Little pour L	3,045
L compté par un observateur (moyenne temporelle)	3,044
Écart entre les deux derniers	0,0006
Erreur type du L compté	0,121
Erreur de M/M/1 ici	−1,4%

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

la falaise de rho 🖖

L = ρ/(1−ρ) ne croît pas de façon régulière. La fonction présente une asymptote verticale en ρ = 1. Ainsi, lorsque l'utilisation passe de 90 % à 99 %, la longueur moyenne de la file bondit de 9 personnes à 99, et devient infinie exactement à la capacité. C'est la « falaise de rho ». Une file à 80 % d'utilisation semble presque identique à une file à 85 %, mais poussez-la à 95 % et les temps d'attente explosent. W = 1/(μ−λ) possède la même singularité : le dénominateur tend vers zéro, le numérateur ne grandit pas. C'est pourquoi les systèmes réels comme les centres d'appels et les urgences hospitalières sont volontairement surdimensionnés, bien en dessous de 100 % de capacité. Cette marge d'inactivité « perdue » près du sommet est ce qui vous évite de tomber de la falaise.

l'aléatoire construit la file 🖖

Dans M/M/1, les deux M signifient « Markovien ». Les arrivées se produisent au hasard (Poisson) et les temps de service varient au hasard (exponentielle), via un serveur unique. L'idée centrale est surprenante. Une file peut se former même lorsque le serveur est en moyenne plus rapide que les clients n'arrivent. Si tout le monde se présentait avec une régularité mécanique et si chaque tâche prenait le même temps, un serveur disposant d'une capacité de réserve ne formerait jamais de file. L'attente vient de la variabilité, non de la surcharge. Réglez λ bien en dessous de μ, et une file continuera d'apparaître et de disparaître. Fixez les deux modèles sur régulier, et la courbe ci-dessus ne quitte jamais 0 et 1. Avec des intervalles et des tâches identiques, le serveur termine toujours avant l'arrivée suivante, pour toute utilisation inférieure à 1.

la loi de Little ne demande presque rien 🖖

Les L et W affichés ici ne sont pas indépendants. Ils satisfont L = λW, et de même Lq = λWq. Cette identité ne suppose presque rien. John Little l'a prouvée en 1961 et elle requiert uniquement ceci : un taux d'arrivée à long terme qui existe et reste fini, ainsi qu'un temps moyen dans le système à long terme qui l'est aussi. Pas d'arrivées de Poisson, pas de service exponentiel, pas d'indépendance, pas de serveur unique, pas même de régime permanent distributionnel. Vous pouvez observer l'importance de ce résultat dans le tableau ci-dessus. Injectez un modèle régulier ou groupé dans l'un des flux, et ρ/(1−ρ) ressort quatre fois trop élevé pour un réglage, et quinze fois trop bas pour un autre. Pendant ce temps, λW et le L compté indépendamment restent à moins de 0,011 client d'écart pour chacun des 405 réglages balayés. La même relation régit le service d'un hôpital, les travaux en cours d'une usine et les stocks d'un magasin. Le contenu moyen est égal au taux d'arrivée multiplié par le temps moyen passé à l'intérieur.

deux moyennes, et une seule appartient au client 🖖

Réglez les deux modèles sur régulier et confrontez deux lignes du tableau. La file qu'un client trouve en arrivant est de 0,000. L'observateur qui compte la même file au fil du temps obtient 0,751. Chaque client entre dans un système vide. Le serveur est occupé les trois quarts du temps. Les deux sont corrects. L pondère la longueur de la file par le temps, alors que la vision de l'arrivant la pondère par client, et rien n'oblige deux pondérations différentes à concorder. La loi de Little associe une moyenne temporelle à une moyenne par client, et n'a jamais prétendu qu'elles étaient identiques. Avec des arrivées de Poisson, elles coïncident, c'est pourquoi la distinction est facile à manquer. Une arrivée est tout aussi probable à n'importe quel instant, de sorte que la vision d'un client constitue un échantillon représentatif de l'horloge. C'est la propriété PASTA, et elle appartient aux arrivées plutôt qu'à la file. Passez les arrivées sur groupé, et la même exécution donne 27,011 contre une moyenne d'horloge de 21,482. Une vague correspond en effet à la fois au moment où la plupart des clients arrivent et à celui où la file est la plus longue.

Problèmes entièrement résolus

Une file avec 3 arrivées par heure et une hausse de 20 % 5 étapes
Les clients arrivent au rythme de 3 par heure et le serveur en traite 4 par heure. Le serveur est inactif un quart du temps, ce qui semble confortable. Calculez la file que cela produit, puis l'effet d'une hausse de 20 % des arrivées.
1. La chaîne s'équilibre. Le flux entrant dans chaque état est égal au flux sortant, ce qui donne Pₙ = (1 − ρ)ρⁿ. Il s'agit d'une distribution géométrique sur la longueur de la file, où ρ est la fraction de temps pendant laquelle le serveur est occupé. Ici, ρ = 0,75.
  
  $P_{n} = (1 - ρ) ρ^{n}, ρ = \frac{λ}{μ} = \frac{3}{4} = 0.750$
2. La moyenne de cette distribution est ρ/(1 − ρ). Regardez ce qui se trouve au dénominateur : non pas la capacité de réserve en clients par heure, mais la fraction de réserve. Trois personnes dans le système en moyenne, pour un serveur inactif un quart de la journée.
  
  $L = n \geq 0 \sum n P_{n} = \frac{ρ}{1 - ρ} = \frac{0.750}{0.250} = 3.000$
3. Soustrayez la personne en cours de service, présente avec une probabilité ρ, et il en reste 2,25 en attente.
  
  $L_{q} = L - ρ = 3.000 - 0.750 = 2.250$
4. La loi de Little transforme une population en durée et ne nécessite aucune hypothèse de distribution. Le nombre moyen dans le système correspond au taux d'arrivée multiplié par le temps moyen qui y est passé. Une heure dans le système, dont 45 minutes d'attente, pour une tâche qui prend 15 minutes à accomplir.
  
  $W = \frac{L}{λ} = \frac{3.000}{3} = 1.000, W_{q} = \frac{L _{q}}{λ} = 0.750$
5. Passez maintenant λ à 3,6. L'utilisation passe de 0,75 à 0,90, soit 20 % de travail en plus, et ρ/(1 − ρ) passe de 3 à 9.
  
  $λ = 3.6 : ρ = 0.90, L = 9; λ = 3.96 : ρ = 0.99, L = 99$
Réponse

L'outil affiche L = 3,000, L_q = 2,250, W = 1,000, W_q = 0,750 à 75 % d'utilisation. La leçon se trouve dans le dénominateur de ρ/(1 − ρ). Ce qui détermine la file n'est pas la capacité de réserve dont vous disposez, mais ce qu'il vous reste en tant que fraction, et cette fraction est ce que vous dépensez lorsque vous ajoutez de la charge. Vingt pour cent d'arrivées en plus multiplient la file par trois. Encore 10 % par-dessus, soit ρ = 0,99, la font passer à 99. C'est pourquoi les hôpitaux, les autoroutes et les contrôleurs de disques s'effondrent à forte utilisation au lieu de se dégrader en douceur. Et c'est pourquoi l'affirmation « nous ne sommes qu'à 90 % de capacité » n'est pas aussi rassurante qu'elle en a l'air.

$L = \frac{ρ}{1 - ρ} blows up at ρ = 1 : + 20% λ ⟹ \times 3 queue$
Les mêmes taux en retirant l'aléatoire 5 étapes
Maintenez λ = 3 par heure et μ = 4 par heure, et retirez toute once d'aléatoire. Les arrivées sont espacées d'exactement vingt minutes, chaque tâche prend exactement quinze minutes. L'utilisation est toujours de 0,750. Calculez la file que cela produit, puis à quelle distance ρ/(1 − ρ) s'en trouve.

Ouvrez ce problème dans l'outil
1. Le client k arrive en k/λ et, le serveur étant libre, repart en k/λ + 1/μ. Le suivant arrive en (k + 1)/λ. Le serveur a terminé à temps dès lors que 1/μ ≤ 1/λ, ce qui n'est autre que ρ ≤ 1 réécrit.
  
  $ρ = \frac{λ}{μ} = \frac{3}{4} = 0.750, \frac{1}{λ} = 0.3333 > \frac{1}{μ} = 0.250$
2. Ainsi, tant que la file est stable, personne n'attend : W_q = 0, et W correspond au seul temps de service, 1/μ = 0,250 heure. Quinze minutes dans le bâtiment, dont chaque minute à être servi.
  
  $\frac{k}{λ} + \frac{1}{μ} \leq \frac{k + 1}{λ} ⟺ \frac{1}{μ} \leq \frac{1}{λ} ⟺ ρ \leq 1 ⟹ W_{q} = 0$
3. La loi de Little convertit cela en population et n'a besoin d'aucune distribution pour le faire : L = λW = 3 × 0,250 = 0,750, et L_q = 0. Trois quarts d'un client, ce qui représente la fraction de temps pendant laquelle le serveur est occupé, et rien d'autre.
  
  $W = \frac{1}{μ} = 0.250, L = λW = 3 \times 0.250 = 0.750, L_{q} = λ W_{q} = 0$
4. Or ρ/(1 − ρ) = 0,750/0,250 = 3,000, soit quatre fois la réalité. Ce facteur n'est pas une coïncidence de ces nombres. M/M/1 donne ρ/(1 − ρ) là où le rythme régulier donne ρ. La surestimation est donc de 1/(1 − ρ) à chaque utilisation.
  
  $ρ 0.50 0.75 0.90 0.95 0.99 ρ / (1 - ρ) 1.000 3.000 9.000 19.000 99.000 ρ 0.500 0.750 0.900 0.950 0.990 1/ (1 - ρ) 241020100$
5. À ρ = 0,99, ce facteur vaut 100. M/M/1 place 99 personnes dans le système. Un trafic parfaitement régulier en place 0,99.
  
  $\frac{ρ / ( 1 - ρ )}{ρ} = \frac{1}{1 - ρ}; ρ = 0.99 : 99.000 ⟷ 0.990$
Réponse

L'outil affiche W = 0,250. La loi de Little transforme cela en L = 0,750 contre une prédiction M/M/1 de 3,000, soit une erreur de +299,6 %. La file n'a jamais existé. La falaise de ρ du premier bloc d'analyse est entièrement bâtie sur la variabilité, et lorsqu'il n'en reste aucune, il n'y a pas non plus de falaise à ρ = 0,99. Ce que cela vous apporte en dehors de cette page, c'est l'argument en faveur des rendez-vous. Ajouter de la capacité et supprimer la variabilité raccourcissent tous deux une file. Le terme 1/(1 − ρ) indique que la deuxième méthode est la plus rentable là où la première est la plus difficile à obtenir. À 75 % d'utilisation, un planning parfaitement régulier permet une division par quatre. À 99 %, une division par cent. Aucune véritable clinique n'atteint une régularité mécanique, et les mêmes taux avec des arrivées groupées donnent plutôt 21,482.

$L_{D / D /1} = ρ = 0.750 ⟷ L_{M / M /1} = \frac{ρ}{1 - ρ} = 3.000, \frac{L _{M / M /1}}{L _{D / D /1}} = \frac{1}{1 - ρ} = 4$

Références (1)

Insight block 3 — how little L = λW assumes: J. D. C. Little, "A Proof for the Queuing Formula: L = λW." Operations Research 9(3), 383–387, 1961.

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.