Un ensemble de cours gratuits en ligne dans différents domaines de la science pour apprendre gratuitement.

Autres sites

Comment apprendre ?

Un site communautaire de questions réponses pédagogiques. Vous y trouverez des milliers de questions et des réponses séléctionnés en tant que meilleures réponses.

Cours en vidéo

Une sélection de cours et thèmes pédagogiques en vidéo.

Sources externes

De cours gratuits en ligne.

Abonnez-vous !

Cours de gestion

Voir aussi

Cours de Sc. Eco.

Sur l'annuaire

• Cours d'économie
• Cours de comptabilité
• Cours de droit
• Cours de langue
• Cours de littérature
• Cours de marketing
• Cours de mathématiques
• Cours de philosophie
• Cours de sciences
• Cours de sciences - Géologie
• Cours de sciences physiques
• Cours de sociologie
• Cours de stratégie
• Cours financier
• Cours Informatique
• Cours de programmation

THÉORIES DES FILES D'ATTENTES M/M/...

Les théories des files d'attentes sont des outils extrêmement puissant et vastes (une présentation complète nécessite au bas mot 300 pages A4) permettant de prendre en compte et de modéliser les goulots d'étranglement dans les processus des entreprises soit au niveau de la logistique, des centrales téléphoniques, des requêtes SQL sur les serveurs, des caisses de grands magasins ou encore dans les toilettes des grands stades sportifs (...) en fonction des hypothèses et contraintes de départ.

Système	Clients	Service
Comptoir-réception	Personnes	Réceptionniste
Atelier de réparation	Machines	Technicien
Garages	Camion	Mécanicien
Hôpital	Patients	Infirmier
Ordinateur	Tâches	Processeurs, disques, rubans
Aéroport	Appareils	Piste d'envoi
Réseau routier	Véhicules	Feux de circulation
Atelier de fabrication	Tâches	Machines/Ouvriers
Téléphone	Appel	Échangeur
Transport en commun	Voyageur	Autobus/Métro
Buanderie	Ligne	Laveuse/Sécheuse
...	...	...

Ces théories permettent se révèlent notamment utile pour justifier des investissement, des embauches ou des achats d'équipements. De façon plus générale, elle est une partie intégrante des techniques mathématiques de gestion lorsqu'il est nécessaire de rechercher un optimum économique entre des coûts d'attente et des coûts de service d'un système.

La problématique type dans les entreprises peut s'exprimer ainsi:

- Quel est le nombre optimal de stations/terminaux à mettre en service permettant de traiter la demande tout en évitant une file d'attente trop importante et le départ de certains clients?

- Quels est le temps d'attente moyen d'un client devant la stations/terminal?

- Quel est le nombre moyen de clients en attente dans la file?

Ces questions permettent d'exprimer des objectifs en matière de qualité et de niveau de service:

1. Un temps d'attente moyen à ne pas dépasser

2. Une probabilité d'attente maximale

3. Un temps d'attente acceptable

Ces théories font donc appel à des méthodes statistiques et algébriques que nous avons étudiées dans les chapitres de Statistiques et de Théorie Des Graphes. Elles n'en sont alors que plus passionnante.

Pour présenter le sujet, plutôt que de faire une généralisation abstraite, nous avons choisi de développer la théorie autour d'un exemple concret et classique qui est le télétrafic. Une généralisation à tout autre cas d'étude se faisant ensuite relativement facilement par analogies.

Considérons donc une central téléphonique regroupant les lignes d'un ensemble d'immeubles d'une ville et ne possédant pas autant de lignes allant vers le réseau que de lignes allant vers les différents particuliers qu'il dessert.

Nous pouvons donc légitiment nous demander de combien de lignes nous avons besoin pour desservir tous ces abonnés.

Pour dimensionner son réseau, un opérateur va devoir calculer le nombre de ressources à mettre en oeuvre pour qu'avec une probabilité extrêmement proche de 1, un usager qui décroche son téléphone puisse disposer d'un circuit. Pour cela, il va falloir développer quelques relations de probabilité de blocage. Ces relations vont demander une modélisation statistique des instants de début et de fin d'appels ainsi que des durées de ces appels. Les paragraphes qui suivent vont donc introduire les lois de probabilités utilisées pour ces dimensionnements.

Enfin, avant de commencer, nous souhaitons mettre à disposition le tableau récapitulatif ci-dessous des notations les plus importantes que le lecteur découvrira au fur et à mesure de sa lecture et auquel il pourra se reporter en cas de confusion:

Variables	Information	Unité
	Flux d'arrivée de clients dans la file d'attente (communication), appelé également "taux moyen d'arrivée des appels", ou encore "fréquence moyenne d'arrivées". L'inverse  donne le temps moyen entre arrivées (appels) dans la file d'attente.
	Flux de départ de clients (communication) correspondant au taux de traitement. L'inverse  donne le temps moyen d'attente pendant le service (donc une fois arrivé en fin de file d'attente) appelé aussi "temps moyen de service".
A ou	Taux d'utilisation du service (par unité de serveur). Assimilé au concept de trafic (un peu abusivement) ou de charge. Est égal au rapport  et doit être strictement inférieur à 1 pour éviter l'engorgement.	-
C	Nombre de clients au total dans le système	-
	Nombre de clients en attente dans la queue	-
	Nombre de clients en service (traitement)	-
T	Temps d'attente dans le système	[s]
	Temps d'attente dans la queue	[s]
	Probabilité d'avoir k clients dans le système	-

MODÉLISATION DES durées d'ARRIVÉES M/M/...

Considérons des appels qui débuteraient de manière aléatoire. Prenons ensuite un intervalle de temps t et divisons cet intervalle en n sous intervalles de durée t/n.

Nous choisissons n suffisamment grand pour que les hypothèses suivants soient respectées :

H1. Une seule arrivée d'appel peut survenir dans un intervalle t/n

H2. Les instants d'arrivée d'appels sont indépendants les uns des autres (le taux d'arrivée n'est pas influencé par le nombre d'appels provenant de la population). Ce qui présuppose une population infinie.

H3. La probabilité qu'un appel arrive dans un sous intervalle donné est proportionnelle à la durée du sous intervalle.

Nous écrivons alors la probabilité de un appel  dans un sous intervalle (1) de la manière suivante :

  (137)

où le 1 en indice du p représente donc l'analyse sur 1 appel, le 1 entre parenthèses le fait que l'analyse se fait sur 1 sous-intervalle et enfin le terme  représente le coefficient de proportionnalité entre la probabilité et la durée t/n du sous-intervalle.

L'hypothèse de départ consistant à considérer comme nulle la probabilité d'avoir plusieurs appels dans un sous intervalle s'écrit alors :

  (138)

La probabilité de n'avoir aucun appel durant un sous intervalle de temps t/n s'écrit donc :

  (139)

En développant, nous obtenons :

  (140)

et en utilisant la propriété énoncée juste au-dessus :

  (141)

La probabilité d'avoir k arrivées d'appels durant n intervalles de temps s'obtient alors en considérant le nombre de manière de choisir k intervalles parmi n... (puisqu'il ne peut y avoir plus d'un appel par intervalle)

Pour chacune de ces solutions, nous aurons alors forcément k intervalles avec une arrivée d'appel et n-k intervalles avec aucune arrivée d'appel. Nous avons vu dans le chapitre de statistique que la loi qui permettait d'obtenir la probabilité de choisir un certain arrangement d'issues binaires parmi un nombre total d'issues était la loi de Bernoulli donnée par :

  (142)

Il vient donc dans notre cas de figure que la probabilité d'une des solutions sera :

  (143)

La probabilité globale s'obtient en sommant les probabilités de tous les cas ce qui nous donne la loi binomiale (cf. chapitre de Statistiques) :

  (144)

Ou encore, en remplaçant les probabilités par leurs valeurs en fonction de  :

  (145)

La limite de la probabilité  lorsque n tend vers l'infini va être égale à la probabilité d'avoir k arrivées d'appel durant un intervalle de temps t. Nous notons  cette probabilité :

  (146)

En reprenant alors les différents termes de l'expression de  et en faisant tendre n vers l'infini, il vient :

  (147)

En utilisant les développements de Taylor (cf. chapitres de Suites Et Séries) :

  (148)

Soit en prenant que le premier terme, c'est-à-dire en considérant x très petit  :

  (149)

Donc :

  (150)

et pour la dernière partie :

  (151)

d'où après regroupement :

  (152)

Cette relation est donc extrêmement importante car elle représente la probabilité d'observer k arrivées d'appels dans un intervalle de durée t (ou le nombre de clients qui se trouve devant une caisse dans un intervalle de durée t) et il s'agit donc d'une distribution de Poisson (cf. chapitre de Statistiques). Dans la pratique, il faut donc s'assurer avant d'utiliser les relations qui vont suivre que cette distribution soit bien respectée (avec un test du khi-deux typiquement).

Il s'ensuit par analogie avec la forme générale de la loi de Poissons que le  paramètre  est le taux moyen d'arrivée (taux moyen d'apparition) d'appels par unité de temps ( ou en anglais "Poisson arrivals see time average": PASTA...). Typiquement il s'agira d'un nombre moyen d'appels par secondes (voir les estimateurs de la loi de Poissons dans le chapitre de Statistiques).

Ainsi, nous avons pour espérance et variance (cf. chapitre de Statistiques) du nombre d'appels:

  (153)

Exemple:

Une TPE souhaitant mettre en place une hotline estime qu'au début elle recevra par journée de 8 heures, 4 appels téléphoniques (soit une probabilité de 1 chance sur 2 d'avoir un appel par heure et donc un taux moyen de 0.5 appels par heure). Alors la probabilité qu'elle reçoive exactement 4 appels (k) par jour et au moins 4 appels (k) par jour selon le modèle théorique de la théorie des files d'attentes est de:

  (154)

où nous avons utilisé la fonction POISSON( ) intégrée dans MS Excel.

Maintenant, introduisons la variable aléatoire  représentant le temps séparant deux arrivées d'appel. Nous introduisons pour cela la probabilité A(t) qui est la probabilité que le temps  soit inférieur ou égal à une valeur t :

  (155)

Nous avons donc :

  (156)

Or,  représente la probabilité qu'il n'y ait aucune arrivée d'appels durant un temps t. Cette probabilité a justement été établie plus haut :

  (157)

Nous en déduisons donc :

  (158)

Nous pouvons aussi introduit la densité de probabilité de la variable aléatoire. Nous obtenons ainsi:

  (159)

La densité de probabilité permet donc de calculer la durée moyenne entre deux arrivées d'appel :

  (160)

En intégrant par partie, il vient :

  (161)

Nous obtenons ainsi, que pour un taux d'arrivé d'appels de  appels par secondes, le temps moyen entre appel est égal à  (résultat relativement logique mais encore fallait-il le démontrer rigoureusement). Effectivement, si nous avons qui vaut 2 appels par heures, le temps moyen d'arrivée est bien de 0.5 heures (1/2) entre appels

Supposons maintenant qu'aucun appel ne soit arrivé jusqu'à un temps  et que nous souhaitons calculer la probabilité qu'un appel arrive durant une durée t après le temps .

Nous devons donc calculer la probabilité d'avoir une durée entre deux appels inférieure à  tout en étant supérieure à .

Cette probabilité s'écrit . En utilisant la formule de Bayes (cf. chapitre de Probabilités) :

  (162)

mais avec les notations idoines il vient :

  (163)

Cette probabilité peut encore s'écrire :

  (164)

En reprenant les expressions des différentes probabilités :

  (165)

Nous voyons donc que la probabilité d'apparition d'un  appel durant un temps t après une durée  pendant laquelle aucun n'est arrivé est la même que la probabilité d'apparition d'un appel pendant une durée t, indépendamment de ce qui a pu arriver avant. Nous considérons donc que le phénomène (la loi exponentielle) est sans mémoire.

MODÉLISATION DES DURÉES DE SERVICE M/M/...

Pour étudier les lois de probabilité qui modélisent les durées des appels (sous-entendu: en service une fois la fin de la file d'attente atteinte), nous procédons comme précédemment.

Nous considérons donc un intervalle de temps de durée t que nous décomposons en n sous intervalles de durée t/n. Nous choisissons n de sorte que les hypothèses suivantes restent justifiées :

H1. La probabilité qu'un appel se termine durant un sous intervalle est proportionnelle à la durée du sous intervalle.

Nous noterons :

  (166)

cette probabilité, expression dans laquelle  représente le coefficient de proportionnalité.

H2. La probabilité qu'un appel se termine durant un sous intervalle est indépendant du sous intervalle considéré.

Nous introduisons alors la variable aléatoire  représentant la durée d'un appel et la probabilité H(t) que la durée d'un appel soit inférieure ou égale à t :

  (167)

La probabilité qu'un appel ayant débuté à t = 0 ne se termine pas avant t s'écrit alors :

  (168)

cette probabilité est égale à la probabilité que l'appel ne se termine dans aucun des n sous intervalles de durée t/n :

  (169)

En faisant tendre n vers l'infini, nous obtenons :

  (170)

Nous obtenons donc l'expression de la probabilité qu'un appel ait une durée inférieure ou égale à t :

  (171)

Nous pouvons en déduire la densité de probabilité associée, notée h(t) :

  (172)

qui correspond donc à une loi exponentielle (le temps qu'un client emploie pour être servi à une caisse - durée de service - ou pour que son appel soit traité une fois en fin de file d'attente suit donc une loi exponentielle!). Dans la pratique, il faut donc s'assurer avant d'utiliser les relations qui vont suivre que cette distribution soit bien respectée (avec un test du khi-deux typiquement).

De la même manière que dans les paragraphes précédents, la durée moyenne d'appel (laps de temps moyen entre deux fins d'appels en service) s'obtient en calculant (toujours la même intégration par parties que plus haut) :

  (173)

En conclusion, nous avons  appels qui cessent par secondes et nous avons une durée moyenne d'appel en service égale à:

  (174)

Effectivement, si nous avons par exemple 2 appels en service qui cessent par heure, cela nous donne une durée moyenne de 0.5 heure (1/2) de service par appel.

Le rapport:

  (175)

représente donc le nombre d'appels qui apparaissent dans la file d'attente sur le nombre d'appels en service qui se terminent pendant un intervalle de temps (temps de service moyen), ce qui représente en fait tout simplement le trafic (ou autrement dit: l'intensité de trafic) ou d'un autre point de vue l'utilisation moyenne du service dont l'unité est le "Erlang" (nous rappelerons cette définition plusieurs fois par la suite...).

Exemple:

Dans un magasin, on compte 240 clients par heure et il faut 28 secondes en moyenne pour traiter un client (temps de service moyen). Sachant que la durée de service suit une loi exponentielle et la distribution des arrivées une loi de Poisson, quelle est l'intensité du trafic et le taux d'occupation des caisses si le magasin en a que deux?

Le trafic est donc donné par le rapport du nombre de clients par heure divisé par le nombre de clients traités par heure. Comme il faut 28 secondes pour en traiter un et qu'il y a 3'600 secondes dans une heure, nous avons l'intensité de trafic suivante:

  (176)

La charge moyenne (ou taux d'occupation) par caisse, sachant qu'il y en a deux, est donc de:

  (177)

C'est cette dernière valeur qui sera prise au final comme valeur du trafic A par station pour les calculs ultérieurs.

Les probabilités d'apparition d'appels et de fin d'appels qui ont été développées dans les paragraphes précédents permettent de modéliser le processus complet d'apparition et de fin d'appels.

NOTATION DE KENDALL

Une notation a été développée par Kendall pour représenter les files d'attentes suite aux développements intensifs (et nombreux) des modèles mathématiques les concernant. La forme réduite de cette notation est:

A/B/C

où A représente le processus d'arrivée des clients dans le système, B représente la distribution des services des clients du système et C le nombre de serveurs du système.

Par exemple, la notation M/M/1 signifie que les clients arrivent au système selon une loi de Poisson (modélisée par une chaîne de Markov), que le temps de traitement est du type exponentiel (modélisée par une chaîne de Markov aussi) et le système constitué d'un seul serveur selon le principe du premier arrivé premier servi dans une file d'attente à population infinie et régime permanent. Ce qui correspond respectivement aux trois relations suivantes que nous avons démontrées plus haut pour la probabilité d'arrivée de k appels dans un temps donné:

  (178)

la probabilité que le temps de traitement (temps de service) soit égale à une certaine valeur :

  (179)

et la probabilité d'avoir k clients (communications) :

  (180)

La lettre M est utilisée pour indiquer que les processus employés sont du type markovien (sous-entendu exponentielle.

En général, nous utilisons la notation:

A/B/C/d:e

d représente le nombre maximum de clients pouvant être présents simultanément dans le système. Ce nombre entier varie entre 1 et l'infini. Quand la capacité mémoire de la file est considérée comme illimitée, ce paramètre est souvent omis.

e représente la discipline de service. Par exemple:

-  FIFO pour premier arrivé, premier servi (First In-First Out appelé aussi FCFS pour First Come-First Serve). Tous les modèles théoriques que nous allons développer ci-dessous seront de type FIFO!

- LIFO pour dernier arrivé premier servi (Last In-First Out appelé aussi LCFS pour Last Come-First Serve)

- SJF pour servir le travail le plus court d'abord (Shortest Job First)

- SRO pour servir en ordre aléatoire (Service in Randon Order)

et encore d'autres...

Ce dernier paramètre est omis si la discipline est FIFO. Ainsi, M/M/1 s'écrirait sans rien omettre:

MODÉLISATION DES ARRIVÉES ET DÉPARTS M/M/1

A chaque instant un certain nombre d'appels vont apparaître et d'autres vont se terminer. Nous pouvons donc modéliser l'état où l'on se trouve à un instant donné comme une chaîne d'états.

Chaque état représente le nombre d'appels en cours. Nous concevons donc bien que si, à un instant donné, il y a k appels nous pouvons passer que dans deux états adjacents selon nos hypothèse : k-1 et k+1.

Nous reconnaissons alors une chaîne de Markov (cf. chapitre de Probabilités). La probabilité de passer d'un état i à un état j pendant un temps dt sera donc notée :

  (181)

Nous introduisons alors les probabilités de transition d'état suivantes :

- Etant dans l'état k, la probabilité  pour passer à l'état k + 1 durant un intervalle de temps dt sera notée

- Etant dans l'état k, la probabilité  pour passer à l'état k-1 durant un intervalle de temps dt sera notée

- Etant dans l'état k + 1, la probabilité  pour passer à l'état k durant un intervalle de temps dt sera notée

- Etant dans l'état k - 1, la probabilité  pour passer à l'état k durant un intervalle de temps dt sera notée

  (182)

Les grandeurs  et  sont des taux d'arrivée (apparition) et de départ (fin) d'appels du même type que ceux utilisés lors des paragraphes précédents. La seule différence tient au fait que ces taux ont en indice l'état où se trouve le système.

Nous pouvons alors introduire la probabilité d'état, c'est-à-dire la probabilité d'être dans un état k à un instant t. Notons pour cela  cette probabilité (à rapprocher de la notation  utilisée pour les chaînes de Markov à temps discret dans le chapitre de Probabilités).

La variation de cette probabilité durant un intervalle de temps dt est alors égale à la probabilité de rejoindre cet état en venant d'un état k-1 ou d'un état k+1 moins la probabilité de quitter cet état pour aller vers un état k-1 ou vers un état k+1.

Ce qui s'écrit :

  (183)

En supposant le système stable, c'est-à-dire en supposant qu'il se stabilise sur des probabilités d'état fixes lorsque le temps tend vers l'infini, nous pouvons écrire que :

  (184)

Nous pouvons alors noter  d'où finalement :

  (185)

Nous aurions pu introduire cette dernière relation d'une autre manière : Elle exprime simplement le fait que la probabilité de partir d'un état est égale à celle pour y arriver (c'est peut-être plus simple ainsi).

Cette relation est vérifiée pour tout  avec les conditions mathématiques suivantes (car sinon ces termes n'ont aucun sens mathématique) :

  (186)

et la condition logique réelle suivante (des appels non encore existants ne peuvent finir...) :

  (187)

En écrivant le système d'équation précédent, nous trouvons :

  (188)

Nous trouvons alors assez facilement la forme générale :

  (189)

Le système se trouvant obligatoirement dans un des états nous avons la relation suivante qui doit obligatoirement être respectée:

  (190)

En remplaçant avec la relation antéprécédente :

  (191)

Ce qui donne aussi :

  (192)

et donc :

  (193)

Si nous considérons maintenant un système avec une seule ligne et de capacité infinie (régime permanent), les grandeurs (taux d'arrivée des appels) et  (taux de départ des appels) auront des valeurs identiques pour tout k. C'est-à-dire que nous considérons que le taux d'arrivée ainsi que les taux de départ sont constant quelque soit la position dans laquelle on se trouve dans la file d'attente. Nous avons alors la dernière relation qui se simplifie:

  (194)

En utilisant le résultat démontré dans le chapitre sur les Suites Et Séries (série de Gauss) nous avons sous des conditions précises nécessaires de convergence (A doit être strictement plus petit que 1):

  (195)

Puisque k représente le nombre d'appels, cette dernière relation donne la probabilité d'avoir 0 appels (clients) pour un traffic permament donné A sur la ligne.

En utilisant:

  (196)

Nous avons alors en toute généralité pour ce type de système la probabilité d'avoir k appels en régime permanent qui est donné par:

  (197)

Il en vient que l'espérance du nombre de communications (clients) dans le système (dans la queue + en service) est alors par définition de l'espérance:

  (198)

puisque  représente la probabilité pour qu'il y ait à tout instant k appels dans le système (file d'attente + en service). Or, nous avons vu dans le chapitre sur les Suites et Séries que:

  (199)

et si q est strictement inférieur à 1 et que n tend vers l'infini, nous avons immédiatement:

  (200)

Si nous dérivons cette dernière relation:

  (201)

et en multipliant par q il vient alors:

  (202)

Il vient alors au final pour l'espérance du nombre de clients dans le système:

  (203)

Si nous souhaitons connaître l'espérance du nombre de clients en attente dans la queue uniquement, il faut bien comprendre qu'à chaque instant nous avons donc une probabilité  qu'il y ait k clients dans le système mais comme 1 parmi ceux-ci est alors toujours en service (donc hors de la queue d'attente) il reste que nous en avons toujours k-1 réellement en attente. Donc:

  (204)

Connaissant le nombre de communications (ou de clients) que nous avons sur l'unique ligne dans tout le système, nous avons alors l'espérance du temps d'attente (temps d'attente moyen), notée E(T) qui sera donnée par le rapport de l'espérance du nombre de communications (clients) en régime permanent sur la ligne E(C) par le taux d'arrivée des appels.

  (205)

Ce résultat, appelé "relation de Little" (ce dernier ayant démontré rigoureusement que la relation est valable pour n'importe quel type de file d'attente), est intuitive dans le cas présent. Effectivement, prenons un appel type au hasard. Quand il arrive dans le système, il va se trouver statistiquement face à E(C) entrain d'attendre. Quand il quittera le système, il y aura été un temps moyen  E(T) . Donc pendant ce temps moyen,  appels seront arrivés derrière lui dans le système. En régime permanent, le nombre d'appels laissés derrière lors du départ doit égaliser le nombre arrivés. D'où l'égalité  dont on déduit alors immédiatement la relation de Little.

Nous avons alors pour l'espérance du temps d'attente dans le système:

  (206)

Pour déterminer le temps d'attente dans la queue seule il suffit de soustraire le temps de traitement/service de par la propriété de linéarité de la moyenne (durée d'appel moyenne en service):

  (207)

Pour résumer, car il y a beaucoup de paramètres et résultats, nous avons donc pour une file d'attente de type M/M/1 (selon la notation de Kendall):

Information	M/M/1
Probabilité système vide
Probabilité d'attente	A
Nombre moyen de clients dans le système
Nombre moyen de clients en attente
Nombre moyen de clients en service	A
Temps moyen de séjour dans le système
Temps moyen d'attente dans la queue
Condition d'atteinte de l'équilibre
Probabilité d'avoir k clients

Il faudrait pour chaque type possible de file d'attente faire les démonstrations détaillées des relations correspondantes ce qui est long et laborieux (c'est un métier/spécialisation à part entière).

Exemple:

Supposons que l'on dispose d'une machine à commande numérique traitant des pièces une à la fois. Supposons que  (nombre de pièces arrivant en moyenne par heure) et que  (nombre de pièces sortant en moyenne par heure). Nous avons alors:

  (208)

ce qui correspond au trafic ou taux d'occupation de la machine. Donc il y a 20% de probabilité pour que le système soit vide et 80% de probabilité pour qu'il y ait une attente.

  (209)

Ce qui correspond donc au nombre moyen de pièces dans le système (machine + en attente).

  (210)

Ce qui correspond donc au nombre moyen de pièces en attente en dehors de la machine.

  (211)

Ce qui correspond à un temps moyen de séjour de 30 minutes dans le système.

  (212)

Ce qui correspond à une attente moyenne de 24 minutes dans la file d'attente.

Et la probabilité qu'il y a ait 5 pièces dans le système (exécution + attente):

  (213)

PROBABILITÉ DE MISE EN ATTENTE M/M/k/k (FORMULE D'ERLANG B)

Nous allons nous intéresser ici à un système disposant de N canaux de communication (chaque canal censé supporter un débit de un appel avec réponse immédiate). Si les N canaux sont occupés, les appels qui arrivent sont considérés comme perdus (absence de tonalité par exemple). Nous parlons alors de blocage ou ruine du système. Il s'agit donc d'une file d'attente limitée de type M/M/k/k selon la notation de Kendall, appelée également "système à perte".

Nous allons chercher à estimer cette probabilité de blocage en fonction du nombre de canaux disponibles et du trafic.

Compte tenu de ce qui a été énoncé sur le caractère sans mémoire du processus d'arrivée d'appels, nous pouvons considérer que la probabilité :

   (214)

d'avoir k appels à l'état k est indépendante de l'état du système tel que :

  (215)

Ainsi, à chaque état k du système la loi de probabilité de type Poisson est valable. La différence de traitement c'est que plutôt que de considérer des états, nous allons considérer qu'un canal de communication peut-être considéré comme un état propre.

Pour la probabilité de fin d'appel, nous avons par contre :

  (216)

Effectivement, cette probabilité traduit juste que si k appels sont en cours chacun a une probabilité  de se terminer, d'où la somme qui donne . Nous avons alors:

  (217)

Ainsi, en injectant ces relations dans :

  (218)

il vient :

  (219)

En introduisant alors (qui doit être strictement inférieure à 1 si nous voulons que les développements suivants convergent vers une valeur finie: chaîne de Markov ergodique) :

  (220)

qui représente pour rappel le nombre d'appels qui apparaissent sur le nombre d'appels qui se terminent pendant un intervalle de temps (temps de service moyen), ce qui représente en fait tout simplement le trafic (ou autrement dit: l'intensité de trafic), il vient alors :

  (221)

ou encore en introduisant le 1 dans la sommation :

  (222)

Puisque k représente le nombre d'appels, cette dernière relation donne la probabilité d'avoir 0 appels (clients) pour un traffic permament donné A dans le système.

En reportant dans l'expression suivante de (probabilité d'être dans l'état k donc...) obtenue plus haut:

  (223)

il vient:

  (224)

et en considérant le caractère sans mémoire nous avons la relation:

  (225)

Il vient :

  (226)

où les k peuvent malheureusement porter à confusion. Il convient de faire un peu le ménage. Au numérateur, le k fait référence au nombre de canaux (serveurs, lignes, opérateurs ou terminaux) et au dénominateur le N aussi. Il convient donc de récrire cela de manière plus convenable:

  (227)

qui donne donc la probabilité de mise en attente (et donc de saturation/blocage) d'un système disposant de N canaux à capacité finie selon le principe du premier/arrivé premier servi (FIFO: First In/First Out) et pour un trafic A (exprimé donc en "Erlang") et dans lequel les communications sont perdues si mises en attente.

Cette relation est parfois notée dans les ouvrages spécialisés sous la forme:

  (228)

Cette relation est très importante en théorie des files d'attentes et porte le nom de "formule d'Erlang-B".

  (229)

Elle est à la base du dimensionnement des réseaux à commutation de cericuits. En effert, le problème de dimensionnement d'un commutateur de circuits est le suivant: Etant donné le trafic en nombre de communications par unité de temps A en Erlang, trouver le nombre d'unités de service k tel que la probabilité qu'un appel arrive dans un système devenu bloquant soitn inférieur à une certaine valeur.

La probabilité obtenue représente alors la qualité de service offerte par le réseau du point de vue de l'usage. Quant au trafic A, il est estimé en fonction du nombre de postes téléphoniques existants et/ou à venir sur la base d'une activité moyenne par poste et par application (téléphone, télécopieur, terminal, serveur informatique, etc.).

Exemple:

E1. Quelle est la probabilité de saturation d'une hotline (dont la durée de service suit une loi exponentielle et la distribution des arrivées suit une loi de Poisson) sachant que le trafic A de la ligne est estimé à 2 Erlang (1 appel par heure pour 1 appel traité par ½ heure - donc rapport de 2 sur 1) pour une seule ligne téléphonique (N=1) en utilisant le modèle d'Erlang-B?:

  (230)

E2. Dans une entreprise, on a dénombré aux heures de pointes 200 appels d'une durée
moyenne de 6 minutes à l'heure (temps de service moyen). Quelle est la probabilité de saturation avec 20 opérateurs (sachant que la durée de service suit une loi exponentielle et la distribution des arrivées une loi de Poisson)?

La plus grosse difficulté ici est de calculer le trafic! Il y a donc 200 appels par heures avec 10 appels traités seulement par heure (puisque 6 minutes par appel dans une heure de 60 minutes fait 10 appels). Le trafic A est donc de 200/10 soit 20 Erlang. En appliquant alors la relation précédente, nous avons:

  (231)

Dans l'industrie on admet un taux de saturation de 0.01%. En jouant avec un tableur comme MS Excel et l'outil Valeur cible, nous trouvons rapidement que N doit alors être égal à 30.

PROBABILITÉ DE MISE EN ATTENTE M/M/k/∞ (FORMULE D'ERLANG C)

Considérons maintenant un système pour lequel les appels peuvent être mis en d'attente avant d'être servis lorsque les k serveurs sont bloqués. Il s'agit donc d'une file d'attente à capacité illimitée de type M/M/k/∞ selon la notation de Kendall.

Avec ce système, nous avons toujours :

  (232)

mais pour la probabilité de fin d'appel l'analyse devient plus subtile. D'abord il y a la probabilité que les appels qui se trouvent sur les canaux N disponibles cessent et qui est donnée par :

  (233)

Mais dès que le nombre d'appels est plus grand que le nombre de canaux de communication disponible, la probabilité que cessent les appels est :

  (234)

Ce qui exprime que quelque soit le nombre d'appels, N ont la probabilité d'être mis en attente dès que k (le nombre d'appels) est supérieur ou égal à N.

Ainsi, pour résumer :

  (235)

En utilisant :

  (236)

Nous obtenons par décomposition du terme produit :

  (237)

D'où finalement :

  (238)

En utilisant l'expression de :

  (239)

Nous pouvons décomposer la sommation :

  (240)

et décomposer le deuxième produit :

  (241)

Sous l'hypothèse que :

  (242)

La somme :

  (243)

peut être simplifiée. Effectivement, en posant :

  (244)

il vient :

  (245)

et comme nous l'avons montré lors de notre étude la fonction Zeta (cf. chapitre de Suites Et Séries) cette somme peut s'écrire sous la forme :

  (246)

Donc :

  (247)

Donc finalement :

  (248)

Puisque k représente le nombre d'appels, cette dernière relation donne la probabilité d'avoir 0 appels (clients) pour un traffic permament donné A dans le système.

Nous avons donc pour :

  (249)

La probabilité cumulée de mise en file d'attente se note C(N, A) est elle est égale à :

  (250)

en procédant exactement comme dans les paragraphes précédents, nous avons finalement :

  (251)

qui donne donc la probabilité de mise en attente (et donc de saturation/blocage - c'est-à-dire que tous les serveurs sont bloqués) dès l'arrive dans un système disposant de N canaux à capacité infinie selon le principe du premier/arrivé premier servi (FIFO: First In/First Out) et pour un trafic A (exprimé donc en "Erlang") et dans lequel les communications peuvent être mises en attente (à l'opposé du modèle Erlang-B). Cette dernière relation est appelée "formule d'Erlang C". Traditionnellement on note :

  (252)

le "W" venant de l'anglais "Wait" (attendre).

Le modèle proposé ci-dessus est bien évidemment critiquable car en réalité la capacité de la file d'attente est finie et certains clients abandonnent lorsque l'attente est trop longue.

Exemple:

Si nous prenons un taux d'arrivé de 1 appel par minute et une durée moyenne de service de 5 minutes, nous avons alors:

  (253)

Si nous prenons un nombre N de 7 serveurs, nous avons:

  (254)

Donc 32.41% de probabilité cumulée d'être mis en attente. Ce qui un peu beaucoup... (un règle empirique consiste à chercher le nombre N de serveurs afin que cette dernière valeur descende en-dessous des 20%).

page suivante : 8. Assurances