Notation de Kendall
En théorie des files d'attente, discipline basée sur la théorie des probabilités, la notation de Kendall permet de décrire un système de files d'attente à l'aide de six paramètres. Elle porte le nom du mathématicien David George Kendall, qui a introduit cette notation en 1953[1], avec seulement trois paramètres A/S/c, où A spécifie la durée entre deux arrivées, S la durée du service, c le nombre de guichet. Elle a ensuite été complétée[2],[3],[4] en A/S/c/K/m/Z où K est la capacité totale du système, m est le nombre de clients et Z le type de files. Quand ces trois derniers paramètres ne sont pas spécifiés, on suppose que K est l'infini, m est l'infini et Z en premier arrivé, premier servi (FIFO).
Exemple de la file M/M/1
modifier
Un modèle classique est la file M/M/1. Il s'agit d'une file où la durée entre deux arrivées est markovien (M). L'adjectif markovien signifie que la durée entre deux arrivées soit une loi exponentielle de paramètre λ. La durée du service est markovien (M), autrement dit la durée du service suit une loi exponentielle de paramètre μ. De plus, il y a un seul guichet (1).
Définition
modifierLa notation de Kendall est une suite de 6 symboles a/s/C/K/m/Z.
- a indique la loi de probabilité des instants d'arrivées, par exemple GI pour la loi générale indépendante et M pour la loi exponentielle.
- 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 est la capacité totale du système, c'est-à-dire le nombre de serveurs (C) plus le nombre de places en attente.
- m indique la population totale de clients (par exemple : nombre d'inscrits sur une liste électorale dans le cas d'une file d'attente à un bureau de vote).
- Z désigne la discipline de service, par exemple first in, first out (FIFO alias paps : premier arrivé, premier servi).
Très souvent, les trois derniers symboles de la notation sont omis avec, par défaut, K infini, m infini et Z en premier arrivé, premier servi.
Valeurs classiques prises par les paramètres
modifier- a et s peuvent être :
- GI : loi générale indépendante,
- G : loi générale,
- M (pour Markov) : loi de Poisson ou loi exponentielle,
- Ek : loi d’Erlang de paramètre k,
- Hk : loi hyperexponentielle d'ordre k,
- D (pour déterministe) : loi uniforme
- Z peut être :
- 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),
- …
Bibliographie
modifier- (en) David George Kendall, « Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain », The Annals of Mathematical Statistics, vol. 24, no 3, , p. 338 (DOI 10.1214/aoms/1177728975, JSTOR 2236285)
- (en) Alec Miller Lee, « A Problem of Standards of Service (Chapter 15) », dans Applied Queueing Theory, New York, MacMillan, (ISBN 0-333-04079-1)
Notes et références
modifier- (Kendall 1953).
- (Lee 1966).
- Hamdy A. Taha, Operations research: an introduction, , Preliminary éd.
- Rathindra P. Sen, Operations Research: Algorithms And Applications, Prentice-Hall of India, (ISBN 978-81-203-3930-9), p. 518
