À la poste, au péage, au standard téléphonique, aux urgences : des clients arrivent au hasard, des serveurs les traitent un par un. Combien de temps attend-on ? Combien de guichets faut-il ouvrir ? La théorie des files d'attente répond avec quelques formules étonnamment simples.
Une file d'attente, c'est trois ingrédients : un flux de clients qui arrivent, des durées de service, et un certain nombre de serveurs. Quand tous les serveurs sont occupés, les nouveaux arrivants attendent. Le hasard des arrivées suffit à créer des files, même quand les serveurs ont, en moyenne, largement le temps.
Trois guichets, occupés à 80 % en moyenne. Les clients passent du bleu au rouge à mesure qu'ils attendent ; la barre sous chaque guichet montre l'avancement du service.
Les données sont inventées. Les résultats sont calculés sur place dans votre navigateur. Chaque formule est confrontée à une simulation : on fait réellement arriver des dizaines de milliers de clients au hasard, et on mesure. Cette page fait partie d'une série sur la recherche opérationnelle ; elle est voisine de Modélisation d'un problème de décision (incertitude) et de Programmation dynamique.
Planche 1
Arrivées, durées de service et nombre de serveurs
On décrit une file par trois données. Le taux d'arrivée λ : le nombre moyen de clients par heure. La durée moyenne de service 1/μ, où μ est le nombre de clients qu'un serveur traite par heure. Le nombre de serveurs c. Le cas le plus courant : des arrivées « au hasard pur » (processus de Poisson), indépendantes les unes des autres.
La file en direct, avec vos réglages. L'horloge est accélérée : une minute simulée par demi-seconde.
–
–
Intervalle moyen entre deux arrivées : mesuré / théorique 60/λ–
Arrivées par quart d'heure : moyenne et variance mesurées–
Notation de Kendall–
Dans l'animation : clients servis, attente moyenne–
Ce qu'il faut retenir. Des arrivées au hasard pur ne sont pas régulières : les intervalles courts sont les plus fréquents (loi exponentielle), et les clients arrivent par grappes. Le nombre d'arrivées dans un quart d'heure suit une loi de Poisson, dont la variance est égale à la moyenne. On note une file A/S/c (Kendall) : M (« sans mémoire ») pour des arrivées ou des services exponentiels, D pour des durées constantes, G pour une loi quelconque, et c le nombre de serveurs.
Planche 2
Taux d'occupation et condition de stabilité
Le taux d'occupation ρ = λ / (c μ) compare le travail qui arrive à la capacité de traitement. C'est aussi la fraction du temps où un serveur est occupé. Si ρ ≥ 1, il arrive plus de travail que les serveurs ne peuvent en absorber : la file grandit sans fin. La condition de stabilité est donc ρ < 1. Mais même en dessous, la file s'allonge très vite quand ρ approche de 1.
Nombre de clients présents au fil du temps, pour trois journées simulées (un serveur, service moyen 1 minute).
Nombre moyen de clients L selon ρ, pour un serveur : la formule ρ / (1 − ρ) (courbe) et la simulation (points, 60 000 clients chacun).
–
Serveur occupé (simulation, 100 000 clients)–
Clients présents L : formule–
L simulé : sur 1 000 min ; sur 100 000 clients–
Serveur inoccupé : 1 − ρ–
Ce qu'il faut retenir. La relation entre occupation et attente n'est pas linéaire : passer de ρ = 0,8 à 0,9 fait passer la file moyenne de 4 à 9 clients, et à 0,95, on atteint 19. Un service « rentabilisé » à 100 % est un service saturé. Il faut garder une marge, et c'est le hasard, pas la paresse des serveurs, qui l'exige. Au-delà de 1, la file ne se stabilise jamais : sa moyenne dépend de la durée d'observation.
Planche 3
La loi de Little
John Little (1961) : dans tout système stable, L = λ W. Le nombre moyen de clients présents est égal au taux d'arrivée multiplié par le temps moyen passé dans le système. Aucune hypothèse sur les lois d'arrivée ou de service, sur le nombre de serveurs ou l'ordre de passage. Une boulangerie où entrent 2 clients par minute et où chacun reste 3 minutes compte en moyenne 6 clients.
Courbe bleue : nombre cumulé d'arrivées. Courbe verte : nombre cumulé de départs. Chaque bande horizontale est un client, de son arrivée à son départ. La hauteur entre les deux courbes, à un instant donné, est le nombre de clients présents (trait rouge).
Aire entre les courbes (minutes × clients)–
L = aire / durée ; λ = clients / durée–
W = aire / clients ; produit λ × W–
Contrôle sur 100 000 clients : L mesuré / λ × W mesurés–
Ce qu'il faut retenir. La démonstration tient dans le dessin : l'aire entre les deux courbes se lit de deux façons. Verticalement, c'est le nombre de présents intégré dans le temps, soit L × durée. Horizontalement, c'est la somme des temps de séjour, soit nombre de clients × W. Donc L = λ W. La loi sert tous les jours : connaissant deux des trois grandeurs, on déduit la troisième. Changer la loi de service change L et W, jamais leur relation : un service très variable allonge beaucoup la file à occupation égale.
Planche 4
Modèles simples : M/M/1 et M/M/c
Avec des arrivées et des services exponentiels, tout se calcule. M/M/1 : un serveur, et la probabilité de trouver n clients est (1 − ρ) ρⁿ ; on en tire L = ρ / (1 − ρ) et W = 1 / (μ − λ). M/M/c : une file commune devant c serveurs. La formule d'Erlang C (1917, pour les standards téléphoniques) donne la probabilité qu'un client doive attendre, et de là toutes les moyennes.
Probabilité de trouver n clients dans le système : formule (barres) et simulation de 200 000 clients (points). Barres orange : les états où un nouvel arrivant doit attendre.
Temps moyen passé (attente + service), en durées de service, selon ρ. Bleu : c files séparées, une par guichet. Vert : une file commune pour c guichets. Violet : un seul guichet c fois plus rapide.
–
Probabilité d'attendre (Erlang C) : formule / simulation–
Clients en file Lq : formule / simulation–
Attente moyenne Wq : formule / simulation–
Temps total W et clients présents L–
Au ρ choisi : files séparées / file commune / guichet rapide–
Ce qu'il faut retenir. En M/M/1 à ρ = 0,8, on trouve en moyenne 4 clients et on passe 5 durées de service dans le système. À occupation égale, mutualiser paie : avec deux guichets occupés à 80 %, deux files séparées font passer 5 durées de service, une file commune 2,8 seulement. Un seul guichet deux fois plus rapide fait encore un peu mieux (2,5), mais il est rarement disponible. C'est pourquoi les banques et les aéroports ont adopté la file unique « serpentin ».
Planche 5
Combien de guichets ouvrir ?
Un bureau de poste reçoit en moyenne 50 clients par heure ; chacun occupe un guichet 6 minutes en moyenne. Un guichet ouvert coûte 30 € de l'heure (salaire et poste). Une heure d'attente d'un client coûte 20 € (mécontentement, clients perdus, image). Trop peu de guichets : la file explose. Trop : on paie des agents qui attendent. Où est le juste milieu ?
Coût horaire selon le nombre de guichets : guichets (bleu) et attente (orange). Point rouge : le coût total le plus bas. Zone hachurée : nombre de guichets insuffisant, la file ne se stabilise pas.
–
–
Minimum pour la stabilité : plus que λ/μ guichets–
Moindre coût total–
Minimum pour l'objectif de service–
Contrôle par simulation (200 000 clients) au nombre animé–
Ce qu'il faut retenir. La charge vaut λ/μ = 50 × 6 / 60 = 5 guichets pleins. Avec 5 guichets, la file explose ; avec 6, elle tient, mais on attend 3,5 minutes en moyenne et 4 clients sur 10 attendent plus de 2 minutes. Le 7ᵉ guichet coûte 30 € et en fait gagner 42 € d'attente : c'est l'optimum, à 226 € de l'heure. Le 8ᵉ ne fait plus gagner que 11 € : il ne se justifie pas. Les deux critères, coût total et niveau de service, désignent ici le même nombre ; changez les coûts pour les voir diverger. Comme la courbe d'attente est très coudée, on se trompe rarement de beaucoup en ajoutant un guichet au minimum de stabilité ; en retirer un est en revanche catastrophique.
Ce qu'il faut garder
L'occupation
ρ = λ/(cμ) doit rester sous 1, et l'attente explose quand on s'en approche. Le hasard impose de garder une marge de capacité.
La loi de Little
L = λ W, toujours. Des clients présents, du débit, du temps de séjour : deux suffisent à connaître le troisième.
Le dimensionnement
Erlang C donne l'attente pour chaque nombre de guichets ; on choisit ensuite au moindre coût total ou au niveau de service visé.
Pour aller plus loin
Dans ce cahier.Modélisation d'un problème de décision (déterministe ou aléatoire) ; Programmation dynamique (stocks) ; Simulation de Monte-Carlo ; Processus de Poisson et chaînes de Markov.
Sur les calculs. Les simulations suivent les clients un par un, dans l'ordre d'arrivée : chacun prend le premier guichet qui se libère. Les moyennes dans le temps (L, occupation) sont intégrées exactement entre les événements. Les formules utilisées sont celles d'Erlang C : P(attente) = C, Lq = C ρ/(1 − ρ), Wq = C/(cμ − λ), et P(attente > t) = C e^(−(cμ − λ)t). Pour un service non exponentiel à un guichet, la formule de Pollaczek-Khintchine donne Wq = ρ (1 + CV²) / (2 (1 − ρ)) × durée de service, où CV est le coefficient de variation de la durée : 0 pour un service constant, 1 pour l'exponentielle, 2 pour le service « très variable » de la planche 3.