THÉORIES DES FILES D'ATTENTES M/M/...
1. Diagramme de Pareto/Lorenz
1.1. Indice de Gini
2. PERT Probabiliste
4. Contrôle statistique des salaires
5.1. Stock initiale optimal
5.2. Modèle de Wilson
6.1. Amortissement linéaire
6.2. Amortissement arithmétique dégressif
6.3. Amortissement géométrique dégressif
6.4. Choix d'investissement
6.4.1. Valeur actuelle nette
6.4.2. Taux de rentabilité interne
6.4.3. Délai de récupération et d'amortissement
7. Théorie des files d'attentes M/M/...
7.1. Modélisation des durées d'arrivées M/M/...
7.2. Modélisation des durées de service M/M/...
7.3. Notation de Kendall
7.4. Modélisation des arrivées et départs M/M/1
7.5. Probabilité de mise en attente M/M/k/k (formule d'Erlang B)
7.6. Probabilité de mise en attente M/M/k/8(formule d'Erlang C)
8.1. Calcul de prime
8.2. Prise en compte de l'expérience
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 |
||
Flux de départ de clients (communication)
correspondant au taux de traitement. L'inverse |
||
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 |
- |
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)
Remarque: Insistons
sur le fait que la stabilité des probabilités
signifie qu'il y a une probabilité égale de quitter l'état que
de le rejoindre.
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