Loading AI tools
De Wikipédia, l'encyclopédie libre
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[1]. Une queue est nécessaire et se créera d'elle-même si ce n'est pas anticipé, dans tous les cas où l'offre est inférieure à la demande, même temporairement. 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 de Copenhague[2] à partir de 1908, é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.
C'est grâce aux apports des mathématiciens Khintchine, Palm, Kendall, Pollaczek[3] et Kolmogorov que la théorie s'est vraiment développée.
On définit un système d’attente de la manière suivante : un flux d’événements qu’on appellera « clients » arrive séquentiellement en réclamant un service[4]. La théorie considère généralement le temps séparant l’arrivée des clients et la durée de service comme deux variables aléatoires (files dites « markoviennes[5] »), mais certains travaux considèrent plutôt les files déterministes, où le temps d'attente est constant. Le client se dirige vers un poste de service (serveur) dès qu’il y en a un de libre, afin d’être servi, sinon il se positionne dans une « file d’attente. »
Un système d’attente est donc composé d’un espace de service (comportant un ou plusieurs serveurs) et d'un espace d'attente dans lequel se forme une éventuelle file d'attente[5]. En informatique, on parlera de client et de serveur ; ailleurs on préférera les termes d’unité et de station.
La littérature distingue par ailleurs[5] :
Enfin, la description d'une file d'attente s'accompagne de la « discipline » ou « politique de service[5] » :
Étant donné une file d'attente, la théorie se propose de produire un certain nombre de résultats, tels :
Elle peut étudier l'existence ou non d'un régime stationnaire, le risque de saturation du service, la discipline optimale par rapport au temps de résidence, etc.
La loi de Little énonce que le nombre moyen 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 : .
Quoique cet énoncé paraisse évident intuitivement, il n'en est pas moins remarquable, puisqu'il ne dépend ni du processus d'arrivée, ni de la discipline de service[6]. Il s'applique également à des serveurs à l'intérieur d'un serveur[7] ; la seule exigence est que le système soit stable et non-préemptif, ce qui exclut des états de transition comme la mise en route ou l'arrêt d'un serveur.
Dans certains cas, il est possible non seulement de relier la taille moyenne de la file d'attente au temps moyen d'attente, mais même de relier la loi de probabilité (et ses moments) de la taille de la file d'attente à celle du temps moyen d'attente[8].
Dans son article original de 1954, Little énonçait cette relation sans la démontrer[9],[10]. Il en donna une première démonstration en 1961[11], simplifiée depuis par Jewell[12] et Eilon[13].
Il existe 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[14],[15].
Très souvent, K est infini, m est infini, et Z en FIFO (encore dénoté par peps). Dans ce cas, les trois derniers symboles de la notation sont omis.
Avec :
File M/M/1 | File M/M/S | |
---|---|---|
Probabilité système vide (P0) | ||
Probabilité d'attente (Pa) | ||
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>) | ||
Temps moyen de séjour dans le système () | ||
Temps moyen d'attente () | ||
Condition d'atteinte de l'équilibre (« pas d'engorgement ») |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.