File d’attente
M. Badaoui
2023-2024
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 1 / 50
Introduction
1 Introduction
2 L’objectif de l’analyse de file d’attente
3 Description d’un système de file d’attente
4 Étude de la loi des arrivées et de la loi des services
5 Étude de la loi de la longueur de la queue
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 2 / 50
Introduction
Introduction
Les files d’attentes se forment lorsque les clients arrivent de façon aléatoire
pour se faire servir. Les exemples les plus courants de la vie de tous les
jours sont les caisses des supermarchés, les établissements de restauration
rapide, les billetteries des aéroports, les cinémas, les bureaux de poste, les
banques.
Toutefois, lorsqu’on parle d’attente, on pense souvent à des personnes.
Or, les ” clients ” en attente sont aussi des commandes en attente de
traitement, des camions en attente de chargement ou de déchargement,
des machines en attente de réparation, des programmes d’ordinateur qui
attendent d’être exécutés, des avions qui attendent l’autorisation de
décoller, des bateaux qui attendent les remorqueurs pour accoster, les
patients dans les salles d’urgence, etc.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 3 / 50
Introduction
Introduction
Généralement, les clients voient dans l’attente une activité sans valeur
ajoutée et, s’ils attendent trop longtemps, ils associent cette perte de
temps à une mauvaise qualité de service. De la même façon, au sein de
l’entreprise, des employés inoccupés ou des équipements inutilisés
représentent des activités sans valeur ajoutée. Pour éviter ces situations, la
majorité des entreprises ont mis en place des processus d’amélioration
continue dont le but ultime est l’élimination de toute forme de gaspillage,
notamment l’attente. Tous ces exemples révèlent l’importance de l’analyse
des files d’attente.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 4 / 50
Introduction
Introduction
La théorie des files d’attente (”queueing theory” en anglais) permet de
modéliser des situations où des clients arrivent à des temps aléatoires à un
serveur afin de se faire servir également à un temps aléatoire.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 5 / 50
Introduction
Introduction
Le but de l’analyse est de caractériser le degré de performance du système
en répondant à des questions du type suivant:
Quelle est la durée d’attente moyenne d’un client arrivant dans la file?
Pendant quelle fraction du temps le serveur est-il occupé?
Quelle est la distribution de probabilité de la longueur de la file?
Selon quel processus les clients quittent-ils le système, une fois servis?
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 6 / 50
L’objectif de l’analyse de file d’attente
1 Introduction
2 L’objectif de l’analyse de file d’attente
3 Description d’un système de file d’attente
4 Étude de la loi des arrivées et de la loi des services
5 Étude de la loi de la longueur de la queue
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 7 / 50
L’objectif de l’analyse de file d’attente
L’objectif de l’analyse de file d’attente
L’objectif de l’analyse des files d’attente est de minimiser le coût total, qui
équivaut à la somme de deux coûts : le coût associé à la capacité de
service mise en place (coût de service) et le coût associé à l’attente des
clients (coût d’attente).
Définition
Le coût de service est le coût résultant du maintien d’un certain niveau de
service, par exemple le coût associé au nombre de caisses dans un
supermarché, au nombre de réparateurs dans un centre de maintenance,
au nombre de guichets dans une banque, au nombre de voies d’une
autoroute, etc. En cas de ressources inoccupées, la capacité est une valeur
perdue, car elle est non stockable.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 8 / 50
L’objectif de l’analyse de file d’attente
L’objectif de l’analyse de file d’attente
Définition
Les coûts d’attente sont constitués des salaires payés aux employés qui
attendent pour effectuer leur travail (mécanicien qui attend un outil,
chauffeur qui attend le déchargement du camion, etc.), du coût de l’espace
disponible pour l’attente (grandeur de la salle d’attente dans une clinique,
kérosène consommé par les avions qui attendent pour atterrir) et, bien sûr,
du coût associé à la perte de clients impatients qui vont chez les
concurrents.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 9 / 50
Description d’un système de file d’attente
1 Introduction
2 L’objectif de l’analyse de file d’attente
3 Description d’un système de file d’attente
4 Étude de la loi des arrivées et de la loi des services
5 Étude de la loi de la longueur de la queue
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 10 / 50
Description d’un système de file d’attente
Description d’un système de file d’attente
Remarque
Une file d’attente est décrite par la loi d’interarrivée des clients, la loi des
temps de service, le nombre de serveurs, la longueur maximale de la file
(égale à la taille de la salle d’attente éventuelle). Nous supposerons
toujours ici que les interarrivées sont des variables aléatoires indépendantes
et de même loi, indépendantes des temps de service, eux mêmes
indépendants et de même loi.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 11 / 50
Description d’un système de file d’attente
Description d’un système de file d’attente
Définition
Pour les files simples, on utilise les notations de Kendall:
Loi d’interarrivée / Loi de service / Nombre de serveurs (/ Longueur
maximale / Nombre maximal de clients potentiels / Discipline de service).
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 12 / 50
Description d’un système de file d’attente
Description d’un système de file d’attente
Définition
Les loi les plus usuelles d’interarrivée et de service sont notées
symboliquement :
M (Markov) : Loi exponentielle. En effet, nous avons vu que cette
loi implique la propriété de Markov. Il s’agit du cas le plus simple à
analyser.
D (Déterministe) : Temps constant, c’est-à-dire que les arrivées des
clients sont régulièrement espacées, respectivement le temps de
service est le même pour tous les clients.
E (Erlang) : Loi dite d’Erlang, qui est en fait une loi Gamma (loi
d’une somme de variables exponentielles).
G (Générale) : Loi arbitraire. Ce symbole s’utilise quand on dérive
des propriétés ne dépendant pas de la loi particulière considérée.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 13 / 50
Description d’un système de file d’attente
Description d’un système de file d’attente
Définition
Nombre de serveurs : Une station peut disposer de plusieurs serveurs en
parallèle. Soit s le nombre de serveurs. Dès qu’un client arrive à la station,
soit il y a un serveur libre et le client entre instantanément en service, soit
tous les serveurs sont occupés et le client se place dans la file en attente
de libération d’un des serveurs. La plupart du temps, les serveurs sont
supposés identiques (ils possèdent donc la même distribution) et
indépendants les uns des autres.
Remarque
Une station particulière est la station IS (infinite servers) dans laquelle le
nombre de serveurs est infini. Cette station ne comporte donc pas de file
d’attente. Dès qu’un client s’y présente, il trouve en effet instantanément
un serveur disponible et entre donc directement en service.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 14 / 50
Description d’un système de file d’attente
Description d’un système de file d’attente
Définition
Capacité de la file : La capacité de la file à accueillir des clients en
attente de service peut être finie ou infinie. Soit K la capacité de la file
(incluant le ou les clients en service). Une file à capacité illimitée vérifie
K = +∞. Lorsque la capacité de la file est limitée et qu’un client arrive
alors que cette dernière est pleine, le client est perdu.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 15 / 50
Description d’un système de file d’attente
Description d’un système de file d’attente
Définition
Discipline de service : La discipline de service détermine l’ordre dans
lequel les clients sont rangés dans la file et y sont retirés pour recevoir un
service. Les disciplines les plus courantes sont :
FCFS (first come, first served) on serve les personnes en respectant
leur ordre d’arrivée.
FIFO (first in, first out) c’est la valeur par défaut, qui signifie le
premier client arrivé est aussi le premier partant ces deux disciplines
sont équivalentes dans le cas ou le service est effectué par un unique
serveur.
LIFO (last in, first out) cela correspond à une pile, dans laquelle le
dernier client arrivé (donc posé sur la pile) sera le premier traité
(retiré de la pile).
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 16 / 50
Description d’un système de file d’attente
Description d’un système de file d’attente
Définition
RANDOM (aléatoire) le prochain client qui sera servi est choisi
aléatoirement dans la file d’attente.
Round-Robin (cyclique) tous les clients de la file d’attente entrent en
service à tour de rôle, effectuant un quantum Q de leur temps de
service et sont replacés dans la file, jusqu’à ce que leur service soit
totalement accompli. Cette discipline de service a été introduite afin
de modéliser des systèmes informatiques.
PS (Processor Sharing) c’est le cas limite de la distribution
Round-Robin lorsque le quantum de temps Q tend vers 0. Tous les
clients sont servis en même temps, mais avec une vitesse inversement
proportionnelle au nombre de clients simultanément présents.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 17 / 50
Description d’un système de file d’attente
Description d’un système de file d’attente
Exemple
La file décrite par le symbole
M/M/1/5/∞/LIFO
est une file dont les arrivées se font selon un processus de Poisson. Les
services suivent la loi exponentielle et la file est constituée d’un unique
serveur. On ne peut accepter plus de 5 clients en attente alors que le
nombre de clients potentiels est illimité. La discipline de service est celle
du dernier arrivé premier servi.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 18 / 50
Description d’un système de file d’attente
Description d’un système de file d’attente
Convention
La plupart du temps seul les trois premiers items sont spécifiés pour
décrire une file d’attente. Par défaut, on utilise la convention suivante
Capacité maximale de la file : ∞
Nombre maximal de clients potentiels : ∞
Discipline de service : FIFO
Ainsi la file d’attente
M/M/1/∞/∞/FIFO
se note simplement
M/M/1.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 19 / 50
Étude de la loi des arrivées et de la loi des services
1 Introduction
2 L’objectif de l’analyse de file d’attente
3 Description d’un système de file d’attente
4 Étude de la loi des arrivées et de la loi des services
Processus d’arrivée
Temps inter-arrivées
Temps d’arrivée de la ne personne
Temps de service
5 Étude de la loi de la longueur de la queue
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 20 / 50
Étude de la loi des arrivées et de la loi des services
Étude de la loi des arrivées et de la loi des services
Plaçons-nous dans le cas très simple où il n’existe qu’une file d’attente et
une seule station de service. Pour étudier les lois des arrivées et des
services, il est commode de passer par le processus de ”Poisson”.
Une file simple (ou station) est un système constitué d’un ou plusieurs
serveurs et d’un espace d’attente. Les clients arrivent de l’extérieur,
patientent éventuellement dans la file d’attente, reçoivent un service, puis
quittent la station. Afin de spécifier complètement une file simple, on doit
caractériser le processus d’arrivée des clients, le temps de service ainsi que
la structure et la discipline de service de la file d’attente.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 21 / 50
Étude de la loi des arrivées et de la loi des services Processus d’arrivée
1 Introduction
2 L’objectif de l’analyse de file d’attente
3 Description d’un système de file d’attente
4 Étude de la loi des arrivées et de la loi des services
Processus d’arrivée
Temps inter-arrivées
Temps d’arrivée de la ne personne
Temps de service
5 Étude de la loi de la longueur de la queue
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 22 / 50
Étude de la loi des arrivées et de la loi des services Processus d’arrivée
Processus d’arrivée
Prenons l’exemple des personnes se présentant à un guichet. On fera trois
hypothèses :
les arrivées sont aléatoires et les laps de temps inter-arrivées ont
même loi de probabilité;
les arrivées sur des intervalles de temps disjoints sont indépendantes;
il n’y a pas d’arrivées simultanées, i.e. il n’arrive pas plus d’un client à
la fois.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 23 / 50
Étude de la loi des arrivées et de la loi des services Processus d’arrivée
Processus d’arrivée
Divisons l’echelle du temps en sous-intervalles
[0, ∆t [ , [∆t , 2∆t [ , . . . , [(n − 1)∆t , n∆t [ , . . . de longueur ∆t trés petite de
telle sorte que pas plus d’une personne n’arrive dans chaque laps de temps
[(n − 1)∆t , n∆t [.
Figure: Subdivision de l’échelle du temps
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 24 / 50
Étude de la loi des arrivées et de la loi des services Processus d’arrivée
Processus d’arrivée
Notons Xn le nombre (aléatoire) d’arrivées durant l’intervalle de temps
[(n − 1)∆t , n∆t [. D’après ce qui précède, Xn est une v.a. prenant
essentiellement les deux valeurs 0 et 1. Elle suit approximativement une loi
de Bernoulli, elle est donc caractérisée par un paramètre p∆t qui n’est
autre que son espérance : E (Xn ) ≈ p∆t .
Il est raisonnable de supposer que cette espérance est proportionnelle à la
longueur de l’intervalle de temps [(n − 1)∆t , n∆t [ : p∆t = λ∆t .
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 25 / 50
Étude de la loi des arrivées et de la loi des services Processus d’arrivée
Processus d’arrivée
On a plus précisément, lorsque ∆t → 0+,
P (Xn = 1) = λ ∆t + o (∆t )
P (Xn = 0) = 1 − λ ∆t + o (∆t )
P (Xn ≥ 2) = o (∆t )
On modélise le processus des arrivées par une fonction aléatoire (processus
stochastique) croissante t ∈ R+ → Nt . Ici, Nt représente le nombre
(aléatoire) de clients entrés dans le système pendant le laps de temps
[0, t].
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 26 / 50
Étude de la loi des arrivées et de la loi des services Processus d’arrivée
Processus d’arrivée
L’étude faite ci-dessus montre que Nn∆t = X1 + . . . + Xn et alors la v.a.
Nn∆t suit approximativement la loi binomiale B (n, p∆t ). Pour un instant t
donné, t est dans un intervalle [(n − 1)∆t , n∆t [ et
k
P (Nt = k) ≈ pk,∆t (t) = Cnk p∆ t
(1 − p∆t )n−k + o (∆t )
Faisons tendre ∆t vers 0+ ou encore n vers +∞ avec n∆t ∼ t (fixé), donc
p∆t ∼ λt/n.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 27 / 50
Étude de la loi des arrivées et de la loi des services Processus d’arrivée
Processus d’arrivée
En écrivant
k
λt n−k
n! λt
pk,∆t (t) = × × 1− + o (∆t )
(n − k)!k! nn
(λt)k λt n−k
n!
= × × 1− + o (∆t )
(n − k)!nk k! n
n(n − 1) . . . (n − k + 1) (λt)k λt n−k
= × × 1− + o (∆t )
nk k! n
λt −k
1 2 k −1
= 1 1− 1− ... 1 − 1− ×
n n n n
(λt)k λt n
× 1− + o (∆t )
k! n
Lorsque n → +∞, tous les facteurs 1 − ni pour 1 ≤ i ≤ k − 1 et
−k
1 − λtn tendent vers 1.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 28 / 50
Étude de la loi des arrivées et de la loi des services Processus d’arrivée
Processus d’arrivée
λt n
Pour le terme 1 − n , on utilise le lemme suivant :
Lemme
Soit a ∈ R, alors, a n
lim 1− = e −a
n→+∞ n
Démonstation
n a
On écrit 1 − na = e n ln(1− n ) . Lorsque n → +∞, a
n → 0, et alors on a
ln 1 − na ∼ − na . Ainsi,
n→+∞
a n a a
1− = e n ln(1− n ) ∼ e n(− n ) = e −a
n n→+∞
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 29 / 50
Étude de la loi des arrivées et de la loi des services Processus d’arrivée
Processus d’arrivée
Ainsi, on obtient la valeur de la limite lim pk,∆t (t) :
∆t →0+
(λt)k −λt
P (Nt = k) = e
k!
C’est la loi de Poisson P(λt). On dit que (Nt )t∈R+ est un processus de
Poisson d’intensité λ.
On a E(Nt ) = λt, ce qui fournit pour λ l’interprétation suivante :
E(Nt )
λ=
t
Ainsi, le paramètre λ représente le nombre moyen d’arrivées par unité de
temps (taux d’arrivée).
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 30 / 50
Étude de la loi des arrivées et de la loi des services Temps inter-arrivées
1 Introduction
2 L’objectif de l’analyse de file d’attente
3 Description d’un système de file d’attente
4 Étude de la loi des arrivées et de la loi des services
Processus d’arrivée
Temps inter-arrivées
Temps d’arrivée de la ne personne
Temps de service
5 Étude de la loi de la longueur de la queue
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 31 / 50
Étude de la loi des arrivées et de la loi des services Temps inter-arrivées
Temps inter-arrivées
Soit T1 = inf {t ≥ 1 : Nt = 1} l’instant d’arrivée (aléatoire) de la
première personne.
La condition T1 > t signifie que la première personne arrive après l’instant
t et donc que Nt = 0. En conséquence,
P(T1 > t) = P(Nt = 0) = e −λt
d’où la fonction de répartition de T1 :
FT1 (t) = P(T1 ≤ t) = 1 − e −λt .
Ainsi, la v.a. T1 suit la loi exponentielle E(λ). Elle a pour densité
fT1 (t) = FT0 1 (t) = P(T1 ≤ t) = λe −λt .
Son espérence vaut E(T1 ) = 1/λ, ce qui donne pour λ une autre
interprétation:
1
λ=
E(T1 )
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 32 / 50
Étude de la loi des arrivées et de la loi des services Temps inter-arrivées
Temps inter-arrivées
Remarque
En fait, la loi de T1 mesure aussi l’intervalle de temps séparant deux
arrivées consécutives : si Un est le laps de temps s’écoulant entre les
(n − 1)e et ne personnes, on a déja vu que les v.a.
U1 = T1 , U2 , . . . , Un , . . . sont independantes de loi commune la loi E(λ).
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 33 / 50
Étude de la loi des arrivées et de la loi des services Temps d’arrivée de la ne personne
1 Introduction
2 L’objectif de l’analyse de file d’attente
3 Description d’un système de file d’attente
4 Étude de la loi des arrivées et de la loi des services
Processus d’arrivée
Temps inter-arrivées
Temps d’arrivée de la ne personne
Temps de service
5 Étude de la loi de la longueur de la queue
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 34 / 50
Étude de la loi des arrivées et de la loi des services Temps d’arrivée de la ne personne
Temps d’arrivée de la ne personne
Soit Tn = inf {t ≥ 0 : Nt = n} l’instant d’arrivée de la ne personne.
La condition Tn > t signifie que la ne personne arrive après l’instant t; il y
a donc eu moins de n arrivées durant l’intervalle de temps [0, t]. En
d’autres termes on a
n−1
X (λt)k
P (Tn > t) = P (Nt < n) = e −λt
k!
k=0
d’où l’on déduit la fonction de répartition de Tn :
n−1
X (λt)k
FTn (t) = P (Tn ≤ t) = 1 − e −λt
k!
k=0
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 35 / 50
Étude de la loi des arrivées et de la loi des services Temps d’arrivée de la ne personne
Temps d’arrivée de la ne personne
La densité de Tn s’obtient en dérivant l’expression ci-dessus :
n−1 k k−1
λk+1 t k −λt
X λ t
fTn (t) = FT0 n (t) = λe −λt
− − e
(k − 1)! k!
k=1
Il reste finalement
λn t n−1 −λt
fTn (t) = e
(n − 1)!
C’est la loi d’Erlang E(n; λ).
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 36 / 50
Étude de la loi des arrivées et de la loi des services Temps d’arrivée de la ne personne
Temps d’arrivée de la ne personne
Bien sûr, Tn est la somme des n premiers temps inter-arrivées :
Tn = U1 + U2 + . . . + Un ou Uk = Tk − Tk−1 (voir Figure), les v.a.
U1 , U2 , . . . , Un étant indépendantes de même loi E(λ) comme cela a été
signalé dans le paragraphe précédent.
Figure: Arrivées
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 37 / 50
Étude de la loi des arrivées et de la loi des services Temps de service
1 Introduction
2 L’objectif de l’analyse de file d’attente
3 Description d’un système de file d’attente
4 Étude de la loi des arrivées et de la loi des services
Processus d’arrivée
Temps inter-arrivées
Temps d’arrivée de la ne personne
Temps de service
5 Étude de la loi de la longueur de la queue
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 38 / 50
Étude de la loi des arrivées et de la loi des services Temps de service
Temps de service
Soit Sn la durée de service de la ne personne. Un modèle très répandu,
reposant sur l’absence de mémoire, consiste à stipuler que
P (Sn > s + t | Sn > s) = P (Sn > t) (modèle markovien)
sachant qu’à un instant donné le service a démarré depuis une durée s, le
temps d’achèvement de service est le même que s’il débutait à cet instant.
Alors
P (Sn > s + t) = P (Sn > s) P (Sn > s + t | Sn > s)
= P (Sn > s) P (Sn > t)
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 39 / 50
Étude de la loi des arrivées et de la loi des services Temps de service
Temps de service
La fonction ϕ définie par ϕ(t) = P (Sn > t) vérife ainsi l’équation
fonctionnelle ϕ(s + t) = ϕ(s)ϕ(t).
De plus, cette fonction est bornée (0 ≤ ϕ(t) ≤ 1) et vérifie ϕ(0) = 1.
En rajoutant l’hypothèse simplificatrice (non nécessaire à priori) que ϕ est
dérivable, on obtient, en dérivant par rapport à s :
ϕ0 (s + t) = ϕ0 (s)ϕ(t)
puis pour s = 0, en posant ϕ0 (0) = a :
ϕ0 (t) = aϕ(t)
Cette équation différentielle, avec la condition initiale ϕ(0) = 1, admet
pour solution ϕ(t) = e at .
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 40 / 50
Étude de la loi des arrivées et de la loi des services Temps de service
Temps de service
Enfin, la fonction ϕ recherchée doit être bornée, ceci entraine donc
P (Sn > t) = e −µt
où la constante µ = E(S1 n ) est l’inverse du temps moyen de service.
Ainsi, la v.a. Sn suit la loi exponentielle E(µ). Le paramètre µ pourrait
s’interpréter comme représentant le nombre moyen de services (taux de
service) que le serveur peut effectuer par unité de temps.
Autrement dit µ est le paramètre qui correspond au nombre de client
servis par unité de temps et 1/µ le temps moyen passé à la station par
chaque client.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 41 / 50
Étude de la loi des arrivées et de la loi des services Temps de service
Temps de service
Remarque
On note λ le taux d’arrivée des clients. Cela signifie que l’espérance de la
durée séparant deux arrivées successives est
1
E[Un ] = .
λ
On note µ le taux de service. Cela signifie que l’espérance de la durée de
service est
1
E[Sn ] = .
µ
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 42 / 50
Étude de la loi des arrivées et de la loi des services Temps de service
Temps de service
Remarque
L’intensité de trafic (ou encore charge du système) s’exprime de la
manière suivante
λ E[Sn ]
ρ= =
µ E[Un ]
Ce rapport de deux durées est une variable sans dimension. On l’exprime
pourtant souvent dans une unité appelée Erlang.
il représente en quelque sorte la proportion du temps que le serveur est
occupé.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 43 / 50
Étude de la loi de la longueur de la queue
1 Introduction
2 L’objectif de l’analyse de file d’attente
3 Description d’un système de file d’attente
4 Étude de la loi des arrivées et de la loi des services
5 Étude de la loi de la longueur de la queue
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 44 / 50
Étude de la loi de la longueur de la queue
Étude de la loi de la longueur de la queue
Introduisons Dt le nombre (aléatoire) de clients sortis du système pendant
le laps de temps [0, t] ; (Dt )t∈R+ est le processus des départs.
Notons alors Qt la longueur de la file à l’instant t, c’est-à-dire le nombre
de personnes présentes dans le système (en attente ou en service); on a
bien sur :
Q t = Nt − D t
Introduisons Dt le nombre (aléatoire) de clients sortis du système pendant
le laps de temps [0, t] ; (Dt )t∈R+ est le processus des départs.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 45 / 50
Étude de la loi de la longueur de la queue
Étude de la loi de la longueur de la queue
Notons alors Qt la longueur de la file à l’instant t, c’est-à-dire le nombre
de personnes présentes dans le système (en attente ou en service); on a
bien sur :
Q t = Nt − D t
(longueur = nombre de personnes entrées - nombre de personnes sorties).
On dit que le processus (Qt )t∈R+ est un processus de naissance et de mort
de taux de naissance λ et de taux de mort µ.
En d’autres termes, chaque arrivée d’un nouveau client étant assimilé à
une naissance, et chaque départ d’un client servi étant assimilé à une mort.
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 46 / 50
Étude de la loi de la longueur de la queue
Étude de la loi de la longueur de la queue
Pour pouvoir représenter la courbe de départs t → Dt , il est nécessaire
d’évaluer l’instant de sortie de chaque client, lequel dépend à la fois de
l’instant d’entrée de ce client, son temps d’attente et son temps de service.
Notons Wn le temps d’attente du ne client présent dans la file et σn son
instant de sortie. Le temps Wn est donné par la relation de récurrence
suivante (formule de Lindley, 1955) :
Wn+1 = max (Wn + Sn − Un+1 ; 0)
et alors
σn = Tn + Wn + Sn
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 47 / 50
Étude de la loi de la longueur de la queue
Étude de la loi de la longueur de la queue
Les graphes des fonctions d’arrivées t → Nt , de départs t → Dt sont des
courbes en escaliers croissantes avec des sauts de 1.
Figure: Courbes d’arrivées-départs
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 48 / 50
Étude de la loi de la longueur de la queue
Étude de la loi de la longueur de la queue
Le graphe de la longueur de la file t → Qt est une courbe en escaliers avec
des sauts de ±1.
Figure: Longueur de la queue
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 49 / 50
Étude de la loi de la longueur de la queue
Étude de la loi de la longueur de la queue
La formule de Lindley se démontre facilement en interprétant les laps de
temps Wn , Wn+1 , Sn , Un+1 comme les aires de rectangles de base les
temps précédents et de hauteur 1. D’après la figure ci-dessous, il est clair
que si la (n + 1)e personne arrivé avant le départ de la ne , i.e. Tn+1 < σn
ou encore Un+1 < Wn + Sn , alors Wn + Sn = Un+1 + Wn+1 . Dans le cas
ou la (n + 1)e personne arrive après le départ de la ne , la (n + 1)e n’a pas
d’attente : Wn+1 = 0.
Figure: Formule de Lindley
M. Badaoui (IG2) Processus stochastiques et File d’attente ESTO 50 / 50
