Théorie des files d'attente

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. 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 entre 1909 et 1920, é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 et Kolmogorov que la théorie s'est vraiment développée.

Sommaire

Description

Une file d'attente se crée pour chaque cas où des clients désirent recevoir un service, auprès d'un producteur. En informatique, on parlera de client et de serveur, ailleurs, on préfèrera les termes d'unités et station.

Aspects mathématiques

Loi de Little

la loi de Little dit que le nombre moyen \langle N \rangle 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 :

 \langle N \rangle = \lambda \cdot \tau

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:

- 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:

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
  • \tfrac{1}{\mu} = temps moyen de service
  • A = \tfrac{\lambda}{\mu} = 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 \frac{1}{\sum_{k=0}^{S-1} \frac{A^k}{k!} + \frac {A^S}{S!} \frac {1}{1-A/S} }
Probabilité d'attente (Pa) A P0 \cdot \frac{A^S}{(S-1)!(S-A)}
Nombre moyen de clients dans le système (<N>) \frac{A}{1 - A} A (1 + \frac{Pa}{S-A})
Nombre moyen de clients en attente (<Na>) \frac{A^2}{1-A} A \cdot \frac{Pa}{S-A}
Nombre moyen de clients en service (au guichet) (<Ns>) A A
Temps moyen de séjour dans le système (τ) \frac{1}{\mu} \cdot \frac{1}{1-A} \frac{1}{\mu} \cdot (1 + \frac{Pa}{S-A})
Temps moyen d'attente (τa)  \frac{A}{\mu (1-A)}  \frac{Pa}{\mu (S-A)}
Condition d'atteinte de l'équilibre ("pas d'engorgement")  \frac{\lambda}{\mu} < 1  \frac{\lambda}{S\mu} < 1

Voir aussi

  • Portail des probabilités et des statistiques Portail des probabilités et des statistiques

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorie des files d'attente de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Theorie des files d'attente — 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… …   Wikipédia en Français

  • Théorie des files d'attente — ● Théorie des files d attente étude mathématique des trafics ou des flux (en vue de réduire les temps d attente des clients, d éviter la rupture des stocks, d améliorer la vitesse de rotation de véhicules ou de navires, etc.) …   Encyclopédie Universelle

  • théorie des files d'attente — eilių teorija statusas T sritis automatika atitikmenys: angl. queuing theory vok. Bedienungstheorie, f; Warteschlangentheorie, f rus. теория очередей, f pranc. théorie des files d attente, f …   Automatikos terminų žodynas

  • Gestion des files d'attente — 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… …   Wikipédia en Français

  • attente — [ atɑ̃t ] n. f. • 1567; atente fin XIe; d un p. p. fém. lat. °attendita, de attendere « attendre » 1 ♦ Le fait d attendre; temps pendant lequel on attend. L attente n a pas été longue. Une attente prolongée. ⇒ faction, pause, station. Deux heures …   Encyclopédie Universelle

  • File d'attente — à Berlin pour un concert en 1988. Une file d attente est un regroupement d individus attendant de manière organisée quelque chose. Les files d attente résultent d une demande supérieure à la capacité d écoulement d une offre (un bien ou un… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Union des étudiants communistes — Logotype de l UEC L’Union des étudiants communistes (UEC) est une organisation politique étudiante française, qui fait partie du Mouvement Jeunes communistes de France (MJCF). Elle a été fondée pour la première fois en 1939, puis dissoute après… …   Wikipédia en Français

  • Théorie de l'emmerdement maximum — Loi de Murphy La loi de Murphy est un principe empirique énonçant que si quelque chose peut mal tourner, alors cette chose finira infailliblement par mal tourner. Une autre version du même adage indique que s il existe au moins deux façons de… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”