Réseaux de Files d’Attente
(RFA)
Nawal SBITI
Applications : systèmes informatiques
réseaux de télécommunication
systèmes de production
1
1- Evaluation des performances de systèmes de
production :
1-1 Pourquoi?
systèmes de production complexes Choix
compétitivité accrue difficiles
Conception
dimensionnement = point crucial
sous-dimensionné => objectif non atteint
surdimensionné => gaspillage
Configuration Performances
donnée Evaluation attendues
de performances
• nombre de machines • taux de production
• taux de panne • en-cours moyen
• nombre de palettes • taux d’utilisation des
• gammes machines
…. ….
Répétition sur différentes configurations =>
meilleur compromis
Exploitation
• le système existe
• comment se comporterait le système si … 2
SED
1-2 Comment?
Système de
production
Modélisation
• simplification du système physique
• hypothèses concernant les données
Très fidèle
non exploitable
Modèle
(RdP, RFA, autre…)
Non fidèle
très exploitable
Analyse
Simulation Méthodes
analytiques
Reproduction pas à pas Equations/résolution
Performances de l’évolution du modèle
• simpl. physiques pas • simpl. physiques
du modèle énormes nécessaires
• simpl. données nécessaire • simpl. données nécessaire
• transitoire et permanent • seulement permanent
• dure longtemps • rapide
• approche la réalité de • exact ou approché
très près mais pas exact
1960 : file unique
Analyse des résultats 1960-1980 RFA à FP (exact)
1980 : approx
3
SED
2- Généralités sur les R.F.A.
2-1 File d’attente unique
Arrivée Départ
clients clients
station
• Processus d’arrivée : distribution des probabilités des
temps interarrivées
A(t) = P[tps entre 2 arrivées t]
• Processus de service : distribution des probabilités des
temps de service
B(x) = P[tps de service x]
• Structure et discipline :
1) Nombre de serveurs disponibles : C
2) Capacité de la file : K
(éventuellement )
3) Discipline de service
PAPS
DAPS
…
Notation de Kendall : A / B / C / K
! Si plusieurs classes de clients, définir :
.processus d’arrivée, de service pour chaque classe
.discipline de service entre classes
4
SED
2-2 Réseau de files d’attente
= ensemble de stations interconnectées
Réseau ouvert/fermé
Réseau ouvert : nombre de clients variable
Départ
Arrivée
clients
clients
Réseau ouvert (monoclasse) défini par :
. Description de chaque station
. Processus d’arrivée des clients dans le réseau
. Cheminement des clients dans le réseau
Rq : réseau ouvert à capacité totale limitée => nb total de clients borné
Réseau fermé: nombre de clients constant
Réseau fermé(monoclasse) défini par :
. Description de chaque station
. Cheminement des clients dans le réseau
. Nombre total de clients dans le réseau 5
SED
Classe - chaîne
1 classe de clients : ensemble de clients dont le
comportement a la même description
* mêmes temps de service
* même cheminement
réseau monoclasse (ouvert, fermé)
réseau multiclasse (ouvert, fermé, mixte)
Décrire :
. chaque station pour chaque classe
. cheminement de chaque classe
. processus d’arrivée de chaque classe (ouvert)
. nombre de clients de chaque classe (fermé)
1 client peut changer de classe
1 chaîne : ensemble de classes auxquelles peut
appartenir un même client
2-3 Exemples de modélisation
Principes de base d’une modélisation :
. Définir les stations du RFA
. Définir les clients
. Caractériser les classes et les chaînes du RFA
Exemples
SED
2-4 Analyse d’un réseau de files d’attente
paramètres de performances :
. Débit de clients à chaque station
. Taux d’utilisation de chaque serveur
. Nombre moyen de clients présents à chaque station
. Temps moyen de réponse d’un client à une station
…
Si réseau multiclasse définir les paramètres pour chaque classe
Pour calculer les performances, on a besoin de :
processus d’arrivée et de service des clients
SED
3- Quelques rappels sur la théorie des probabilités
3-1 Grandeurs utilisées
X : variable aléatoire
Complètement caractérisée par :
Fonction de répartition : FX (x) = P (X x)
dFX (x)
Densité de probabilité : fX (x) =
(distribution) dx
probabilité pour que X [x0, x0+dx] = fX (x0) dx
Description suffisante par :
Espérance (moyenne, moment d’ordre 1)
+
E(X) = x fX (x) dx (=xi pi si discret)
- i
Moment d’ordre n
+
E(X ) = xn fX (x) dx
n
-
Variance (moment d’ordre 2 de la variable centrée)
X² = E(X²) – [ E(X)]² 8
SED
X : écart-type
Coefficient de variation
X
cvX =
E(X)
disparité par rapport à la moyenne
3-2 Utilisation de la transformée de Laplace
pour le calcul des moments
v. a. X dont la d.d.p est fX(x) x0
+
LX (s) = e-sx fX (x) dx
0
Calcul des moments (v.a. causale)
dnLX(s)
E(Xn) = (-1)n
dsn s=0
Somme de v.a.
La d.d.p. de la somme de 2 v.a. est le produit
de convolution des d.d.p. de chaque variable
La T.L. de la d.d.p. de la somme de 2 v.a. est
le produit des T.L. de chacune des d.d.p.
SED
2 v.a. indépendantes de ddp f1 et f2
f : ddp de la somme :
+
f = f 1 * f2 = f1 (X-x) f2(x) dx
-
TL (f) = TL(f1) . TL(f2)
3-3 Quelques lois importantes
Loi exponentielle de taux m :
ddp:
fX (t) = m e-mt t0 fX (t)
m
t
Fonction de répartition :
FX (t) = 1 - e-mt t0 FX (t)
= P [X t] 1
10
SED
Moyenne : +
E(X) = t fX (t) dt = 1/m
0
Variance : X² = 1/m²
Coefficient de variation cvX = X / E(X) = 1
Représentation :
Propriété sans mémoire de la loi exponentielle :
P[X t+t0 / X > t0] = P[X t ]
Interprétation : Savoir qu’une activité distribuée
exponentiellement a déjà eu lieu pendant un temps t0 ne va
pas affecter la distribution de la durée résiduelle.
Exemple : temps interarrivée distribuée exponentiellement
l’instant de la prochaine arrivée
indépendant du passé 11
SED
Loi d’Erlang:
Une loi d’Erlang d’ordre k est une succession de k lois
exponentielles de taux m identiques.
m m m
E(X) = k/m
cvX = 1/√k
Loi hypoexponentielle:
Une loi hypoexponentielle est une suite de lois
exponentielles.
m1 m2 mk
k étages
cvX < 1
12
SED
Loi hyperexponentielle:
Choix entre k exponentielles.
a1
m1 cvX > 1
a2
m2
ak
ai = 1
mk
Loi de Cox:
Loi PH:
13
SED
3-4 Processus aléatoire (stochastique)
Un processus aléatoire est une famille de variables
aléatoires X(t), t T
Exemples :
-> Xt : niveau d’eau dans un réservoir au temps
t après la mise en service
alors {Xt ; t 0} est un processus stochastique
- à paramètre continu t
- à espace d’état continu
-> Si on remplace le niveau d’eau par un nb de
pièces
- à paramètre continu t
- à espace d’état discret
Fonction de répartition :
FX (x, t) = P (X(t) x) = FX(t) (x)
14
SED
Processus Markovien
X(t), espace d’états discret, paramètre discret ou continu
Le P.A. X(t) est un processus Markovien
si n; t1 < t2 < … < tn ; x1 , x2 …, xn
On a :
P[X(tn) xn / X(tn-1) xn-1 ; X(tn-2) xn-2 ; …; X(t1) x1 ]
= P[X(tn) xn / X(tn-1) xn-1 ]
Chaîne de Markov à temps continu : t IR
(temps passé dans chaque état : sans mémoire exponentiel)
Processus de renouvellement
0=t0 t1 t2 t3 t4 t5 …
T = {ti} suite d’instants aléatoires (processus d’arrivée)
Xi = ti+1 – ti (temps interarrivée)
Le processus d’arrivée T est un processus de
renouvellement si les v.a. Xi sont :
. Indépendantes
. Identiquement distribuées
15
SED
Processus de Poisson
Processus de renouvellement tel que les temps interarrivée
Xi sont distribués selon une loi exponentielle.
Pour un processus de Poisson de taux l, la probabilité
d’une arrivée entre t et t+dt est ldt (ne dépend pas du
passé).
16
SED
4- Analyse d’une file d’attente
4-1 Présentation / Notations
A(t) B(t)
C
K A/B/C/K
Pour A et B, on choisit parmi :
M : exponentiel
Ek : Erlang d’ordre k
PH
Ck : Cox d’ordre k
G : Générale
D : Déterministe
Exemple : M / M / 3 / 10
Performances recherchées : (stationnaires)
Débit moyen de la file d’attente : X
Temps de réponse moyen : W
Nombre moyen de clients : Q
Loi de LITTLE :
Q=W.X
17
SED
Soit n(t) : nombre de clients dans la file à l’instant t
Objectif :
Calculer p(n) n = 0, 1, …
dont on peut déduire les
principales performances :
Q = n . p(n)
n
X = (1 – p(0)) . (taux de service)
18
SED
4-2 Etude d’une M / M
File M / M / 1 m
l
−
Instants d’arrivée et de fin de service indépendants
du passé n(t) processus Markovien
Chaîne de Markov : processus de naissance et mort
Performances recherchées : (stationnaires)
Utilisation du serveur : U
Débit : X
Nombre moyen de clients dans le
système (= en-cours): Q
Nombre moyen de clients qui
attendent
Temps de réponse moyen : W
Temps d’attente
Analyse d’autres files d’attente : M/M/1/K, M/M/C, …
Applications
19
SED
