- Loi de little
-
Théorie des files d'attente
La théorie des files d'attente est une théorie mathématique relevant du domaine des probabilités, qui étudie les solutions optimales de gestion des files d’attente, ou queues. Elle peut s’appliquer à différentes situations : gestion des avions au décollage ou à l’atterrissage, attente des clients et des administrés aux guichets, ou bien encore stockage des programmes informatiques avant leur traitement. Ce domaine de recherches, né en 1917, des travaux de l’ingénieur danois Erlang sur la gestion des réseaux téléphoniques, étudie notamment les systèmes d’arrivée dans une queue, les différentes priorités de chaque nouvel arrivant, ainsi que la modélisation statistique des temps d’exécution.
Sommaire
Loi de Little
la loi de Little dit que le nombre moyen <N> de clients dans un système stable, est égal à leur fréquence moyenne d'arrivée λ multipliée par leur temps moyen τ passé dans le système :
Notation de Kendall
Il existe, évidemment, de très nombreux systèmes de files d'attente. La notation de Kendall permet de décrire le système par une suite de 6 symboles a/s/C/K/m/Z. Voici la signification de ces symboles:
- a, indique la loi de probabilité des instants d'arrivées, on utilise les symboles suivants:
- GI: loi générale indépendante
- G: loi générale
- M: loi exponentielle
- Ek: loi Erlang-k
- Hk: loi hyper-exponentielle d'ordre k
- D: loi constante
- s, indique la loi de probabilité de la durée du service (au guichet), on utilise les mêmes symboles que précédemment
- C, indique le nombre de serveurs (nombre de guichets)
- K, c'est la capacité totale du système, c'est à dire le nombre de serveurs (C) + le nombre de places en attente
- m, indique la population totale de clients (par exemple: nombre d'inscrits sur une liste electorale dans le cas d'une file d"attente à un bureau de vote)
- Z, la discipline de service, à savoir:
- paps: premier arrivé, premier servi (fifo ou fcfs en anglais)
- daps: dernier arrivé, premier servi (lifo ou lcfs en anglais)
- a: aléatoire (firo en anglais)
- ...
Très souvent les trois derniers symboles de la notation sont omis. On a alors: K infini, m infini et Z en paps.
Quelques résultats
Avec:
- λ = fréquence moyenne d'arrivées
- temps moyen de service
- trafic offert (nombre moyen d'arrivées pendant le temps moyen de service)
File M/M/1 File M/M/S Probabilité système vide (P0) 1 − A Probabilité d'attente (Pa) A Nombre moyen de clients dans le système (<N>) Nombre moyen de clients en attente (<Na>) Nombre moyen de clients en service (au guichet) (<Ns>) A A Temps moyen de séjour dans le système (τ) Temps moyen d'attente (τa) Condition d'atteinte de l'équilibre ("pas d'engorgement") Voir aussi
- Portail des probabilités et des statistiques
Catégories : Algorithme | Théorie | Recherche opérationnelle
Wikimedia Foundation. 2010.