Fichier PDF

Partage, hébergement, conversion et archivage facile de documents au format PDF

Partager un fichier Mes fichiers Convertir un fichier Boite à outils Recherche Aide Contact



YEO Yardjouma Memoire de master Reseaux de files d'attente .pdf



Nom original: YEO Yardjouma Memoire de master Reseaux de files d'attente.pdf

Ce document au format PDF 1.5 a été généré par TeX / MiKTeX pdfTeX-1.40.12, et a été envoyé sur fichier-pdf.fr le 09/05/2017 à 16:33, depuis l'adresse IP 154.68.x.x. La présente page de téléchargement du fichier a été vue 242 fois.
Taille du document: 863 Ko (71 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Année Académique 2014-2015
THEME:
Réseaux de Files d'Attente

Auteur: YEO Yardjouma
Université Felix Houphouet Boigny
de Cocody
Côte d'Ivoire
yardjoumayeo01@gmail.com/y.yardjouma@yahoo.fr
Travail dirigé par le Professeur N'ZI Yao Ko Modeste
Mémoire de Master soutenu le 26 Mai 2016 devant le jury:
Président:prof. ADOU Kablan Jérôme,Professeur Titulaire
Université FELIX HOUPHOUËT-BOBIGNY
Directeur: Prof. N'ZI Yao Ko Modeste, Professeur Titulaire
Université FELIX HOUPHOUËT-BOBIGNY
Membre:Prof. AMAN Auguste, Maître de Conférences
Université FELIX HOUPHOUËT-BOIGNY
Membre: Dr. OWO Jean Marc, Maître- Assistant
Université FELIX HOUPHOUËT-BOBIGNY
Mémoire de Master soutenu le 26 Mai 2016

Table des matières
Introduction

5

1

8

Notions sur les Processus Markoviens de Sauts
1.1

1.2

Processus de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.1.1

Dé nitions et notations . . . . . . . . . . . . . . . . . . . . . . . .

8

Processus Markoviens de Sauts . . . . . . . . . . . . . . . . . . . . . . .

10

1.2.1

Générateur in nitésimal . . . . . . . . . . . . . . . . . . . . . . .

11

1.2.2

Etats récurrents et transitoires . . . . . . . . . . . . . . . . . . . .

13

2 Files d'attente unique
2.1

2.2

2.3

15

Dé nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.1.1

Processus d'arrivée ou processus de renouvellement . . . . . . . .

15

2.1.2

Temps de service . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.1.3

Structure et discipline de service . . . . . . . . . . . . . . . . . . .

16

2.1.4

Notations de Kendall . . . . . . . . . . . . . . . . . . . . . . . . .

17

Files d'attente Markovienne . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.2.1

18

File d'attente M/M/1

. . . . . . . . . . . . . . . . . . . . . . . .

2.2.2

File d'attente M/M/1/K

. . . . . . . . . . . . . . . . . . . . . .

25

2.2.3

Modèle de le d'attente M/M/s . . . . . . . . . . . . . . . . . . .

29

2.2.4

File d'attente M/M/s/s

. . . . . . . . . . . . . . . . . . . . . . .

35

2.2.5

File d'attente M/G/∞ . . . . . . . . . . . . . . . . . . . . . . . .

39

Etude de la File d'attente M/G/1 . . . . . . . . . . . . . . . . . . . . . .

42

1

2.3.1

Méthode de la chaîne de Markov incluse . . . . . . . . . . . . . .

42

2.3.2

Le cas récurrent positif . . . . . . . . . . . . . . . . . . . . . . . .

43

3 Réseaux de les d'attente

45

3.1

Dé nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

3.2

Réseaux ouvert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

3.2.1

Réseau de Jackson ouvert . . . . . . . . . . . . . . . . . . . . . .

46

Réseaux fermés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

3.3.1

Réseau de Jackson fermé . . . . . . . . . . . . . . . . . . . . . . .

53

Réseau de Kelly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

3.4.1

Classes de clients . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

Réseau téléphonique . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

3.5.1

Dé nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

3.5.2

Distribution stationnaire . . . . . . . . . . . . . . . . . . . . . . .

58

3.5.3

Nombre moyen de communications mettant en jeu n canaux. . . .

60

Simulation de les d'attente . . . . . . . . . . . . . . . . . . . . . . . . .

61

3.6.1

Processus d'arrivée . . . . . . . . . . . . . . . . . . . . . . . . . .

63

3.6.2

Processus de service

. . . . . . . . . . . . . . . . . . . . . . . . .

63

3.6.3

La longueur de le d'attente dans le système . . . . . . . . . . . .

64

3.6.4

Utilisation du modèle de simulation pour la détermination des vari-

3.3

3.4

3.5

3.6

ables d'action . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

Conclusion

68

Bibliographie

69

2

Rémerciement
Je tiens d'abord à remercier mon directeur de mémoire, Prof. N'ZI

Yao Ko Mod-

este,de l'UFR de mathématiques et informatique de l'Université Félix Houphouët-Boigny
de Cocody-Abidjan pour ses conseils judicieux, sa patience, sa disponibilité qui m'ont été
d'une aide précieuse pour assurer la réussiste de ce travail.

Je voudrais adresser une reconnaisance toute particulière au Prof.

Jérôme,de

ADOU Kablan

l'UFR de mathématiques et informatique de l'Université Félix Houphouët-

Boigny de Cocody-Abidjan, qui malgré ses occupations a accepté de présider le Jury de
mon travail.

Je suis honoré par la présence dans le Jury de prof.

AMAN Auguste,

Maître de

Conférences de l'UFR de mathématiques et informatique de l'Université Félix HouphouëtBoigny de Cocody-Abidjan.

Je voudrais aussi exprimer un profond respect au Docteur OWO Jean Marc Maître
assistant de l'UFR de mathématiques et informatique de l'Université Félix HouphouëtBoigny de Cocody-Abidjan, qui malgré ces occupation a accepté d'être membre du Jury.

Je tiens à remercier prof.

COULIBALY Adama, Maître de Conférences de l'UFR

de mathématiques et informatique de l'Université Félix Houphouët-Boigny de CocodyAbidjan, pour ses nombreux conseils pendant les séances de cours qui m'ont value un

3

bien soutien moral et une motivation supplementaire.

Je remerci prof.

Assohoun ADJE, Directeur de l'UFR de Mathématiques et Infor-

matique, pour ses encouragements. Qu'il trouve ici le témoignage de ma reconnaissance.

Je remercie aussi les

Docteurs et tous ceux qui de près ou de loin m'ont transmis le

savoir et apporté une quelconque aide nécessaire à la réussite de ce travail.

Un merci spécial à tout le personnel de l'UFR de mathématiques et informatique de
l'Université Félix Houphouët-Boigny de Cocody-Abidjan .

Un grand merci à mes

Amis pour leurs aides et leur soutien moral durant mon par-

cours scolaire.

Je ne saurais terminer sans remercier Parents et Famille qui m'ont toujours soutenu
et accompagné tout au long de mes études.

4

Dédicace
Toutes mes pensés pour feu Yssouf OUATTARA qui nous a quitté il y a maintenant
trois ans, j'aurais souhaité qu'il soit là pour suivre mon évolution scolaire, que son âme
repose en paix.
Je dédie ce travail à mon père qui n'a jamais cessé de m'encourager en me disant toujour
que je dois devenir un homme célèbre dans la vie. Cette grande con ance qu'il manifeste
à mon égard m'a donné beaucoup de force dans la prise de mes étudees universitaires.
Je dédie également ce travail à ma mère celle qui ma supporté, m'allaita, gouverna mes
premier pas.
Je dédie ce travail particulièrement à ma ancée YEO Chata pour la considération qu'elle
m'accorde.

5

INTRODUCTION
La Théorie des les d'attente est une technique de la Recherche opérationnelle qui
permet de modéliser un système admettant un phénomène d'attente, de calculer ses
performances et de déterminer ses caractéristiques pour aider les gestionnaires dans leurs
prises de décisions.
Les les d'attente peuvent être considérées comme un phénomène caractéristique de la vie
contemporaine. On les rencontre dans les domaines d'activité les plus divers spécialement
dans le tra c routier (carrefour à feux). L'étude mathématique des phénomènes d'attente
constitue un champ d'application important des processus stochastiques.
On parle de phénomène d'attente chaque fois que certaines unités appelées "clients"
se présentent d'une manière aléatoire à des "stations" a n de recevoir un service dont
la durée est généralement aléatoire.Cette théorie des les d'attente est un formalisme
mathématique qui permet de mener des analyses quantitatives à partir de la donnée des
caractéristiques du ux d'arrivées et des temps de service. Les origines de ce formalisme
des les d'attente datent du début du XX-ième siècle et principalement des travaux
de deux mathématiciens : le mathématicien danois A.K.Erlang avec ses travaux sur les
réseaux téléphoniques et le russe A.A. Markov avec la création des modèles markoviens.
C'est en 1909 que les bases de ce formalisme sont jetées, grâce à l'article du mathématicien
danois A.K. Erlang [7] "The theory of probabilities and telephone conversations". Les
premiers résultats sont variés : Erlang observe le caractère poissonnier des arrivées des
appels à un central téléphonique, et le caractère exponentiel des durées des appels ; il
réussit à calculer de manière relativement simple la probabilité d'avoir un appel rejeté.

6

La notion d'équilibre stationnaire d'un système d'attente est introduite.
L'objectif principal de ce travail est d'expliquer le phénomène d'attente, de présenter les
notions de base concernant les systèmes de les d'attente et de dé nir les paramètres
permettant de décrire les performances de tels systèmes.

7

Chapitre 1
Notions sur les Processus Markoviens
de Sauts
1.1 Processus de Poisson
1.1.1 Dé nitions et notations
Dé nition 1.1 On appelle processus ponctuel une suite croissante
0 < T1 < T2 < ... < Tn < ... < +∞

(1.1)

de variables aléatoires à valeurs dans R+ dé nies sur un espace probabilisé (Ω,F,P).
Dans la suite on supposera que la suite (Tn )n N tend vers +∞ quand n tend vers +∞.

On pose :

T0 = 0
S1 = T1 − T0 ,
......

8

∀n N
Sn = Tn − Tn−1 .
Les Tn sont les instants où se produisent des événements. Les Sn sont les délais d'attentes
entre deux événements successifs .

Notons
Nt =

+∞
X

I{Tk ≤t} = sup{n ≥ 1 : Tn ≤ t}

(1.2)

k=1

le nombre d'événements qui se produisent avant l'instant t.

Nt est aussi appelé processus de comptage. On a :

N0 =0
Nt < +∞

∀ 0 ≤ s < t Nt -Ns est égal au nombre d'événements qui se produisent dans l'intervalle
de temps ]s,t].

Dé nition 1.2 On dit qu'un processus ponctuel (Tn )n N ou sa fonction aléatoire de comptage (Nt )t≥0 est un processus de poisson ,si (Nt )t≥0 est une fonction aléatiore à accroissements indépendants et stationnaires.
C'est-à-dire :
a) ∀ 0=t0 <t1 <t2 <...<tn les accroissements Nti − Nti−1 sont des variables aléatoires
indépendantes ∀ i=1...n.
b) ∀ 0≤ s<t, Nt -Ns dépend uniquement de t-s et non de t et s.

Remarque 1.1 La propriété b) est appelée la "stationarité des accroissements" de (Nt )t≥0 .
Le nom "processus de Poisson" est justi é par la proposition 6.2.2 de [4]. L'existance
d'un paramètre λ est donné par cette proposition . Ce paramètre λ est appelé l'intensité
9

du processus de Poisson (Nt )t≥0 . Il est égal au nombre moyen d'événements qui se produisent pendant un intervalle de temps de longueur unité, i.e.
E[Nt − Ns ] = λ.

1.2 Processus Markoviens de Sauts
Dé nition 1.3 Une fonction aléatoire (Xt )t≥0 à valeurs dans un ensemble ni où denombrable E est appelée fonction aléatoire de sauts, si elle est de la forme :
X

Xt (ω) =

Zn (ω)I[Tn (ω),Tn+1 (ω)] (t)

(1.3)

{n≥0;Tn (ω)≤∞}

où 0=T0 ≤ T1 ≤ ... ≤ Tn ≤ ... est une suite croissante de variables aléatoires dé nies
sur un espace probabilisé (Ω,F,P) telle que :
Tn (ω) −→ ∞ quand n −→ ∞ où
Zn sont des variables aléatoires de (Ω,F,P) à valeurs dans un ensemble ni où dénom-

brable E. La suite (Zn )n≥0 est appelée chaîne incluse.

Dé nition 1.4 Une fonction aléatoire de sauts (Xt )t≥0 à valeurs dans un ensemble ni
où dénombrable E est appelée processus markovien de sauts si pour tout 0 < s < t,
la loi conditionnelle de la variable aléatoire Xt sachant {Xu ; 0 ≤ u ≤ s} ne dépend que
de Xs . C'est-à-dire :
si ∀n N 0 ≤ t1 < t2 < ... < tn < s et x0 ,x1 ,...,xn ,x,y E,alors

P(Xt = y|Xto = x0 , Xt1 = x1 , ...., Xtn = xn , Xs = x) = P(Xt = y|Xs = x)
= Pxy (t, s)
Dans la suite on notera E l'ensemble des états de la chaîne de Markov.

10

(1.4)
(1.5)

Dé nition 1.5 Un processus de naissance et de mort est un processus de markovien de
sauts à valeurs dans E = N tels que les seules transitions non négligeables possibles à
partir de x soient vers x + 1 ou vers x − 1.
Les les d'attente de type markovien (M/M) sont des cas particuliers très importants de
processus de naissance et de mort. Leur étude complète sera e ectuée dans la suite.

Dé nition 1.6 On dira qu'un processus markovien de sauts (Xt )t≥0 est homogène si
la quantité P(Xt =y|Xs =x) ne dépend de s et de t que par la di érence t - s.

Dé nition 1.7 On dit qu'un processus markovien (Xt )t≥0 est stationnaire si sa loi est
indépendante de t

Dé nition 1.8 On appelle distribution stationnaire toute probabilité Π qui véri e Π =
ΠP .C'est-à-dire

P

y E

Πy Py,x (t) = Πx ,x E

Dans la suite on utilisera qu'une chaîne de Markov homogène.

1.2.1 Générateur in nitésimal
La propriété de semi-groupe fait que P(t) est connu pour tout t dès qu'il est connu
pour t petit. En fait, il est entièrement déterminé par sa dérivée à droite en t = 0 (on
sait que P (0) = I ).

Théorème 1.1 Soit {P (t), t ≥ 0} le semi-groupe des matrices de transition d'un processus markovien de sauts (Xt )t≥0 . Il existe une matrice {Qxy ; x, y E} appelée le générateur

in nitésimal du semi-groupe
{P (t), t ≥ 0} qui véri e

i)Qx,y ≥ 0 si x 6= y

11

ii)Qx,x = −

P

y E\{x}

Qx,y ≤ 0,

(cette dernière égalité étant stricte sauf si l'état x est absorbant) et telle que, lorsque h ↓ 0,
Pxy (h) = hQxy + ◦(h)

Pxx (h) = 1 + hQxx + ◦(h).

En outre, conditionnellement en X0 = x, l'instant de premier saut T1 et la position
après le premier saut Z1 = XT1 sont indépendants, T1 de loi exponentielle de paramètre
; y 6= x}.
qx = −Qxx , et Z1 de loi sur E donnée par { Qqxy
x

Preuve
Remarquons tout d'abord que

{T1 > nh} ⊂ {X0 = Xh = ... = Xnh } ⊂ {T1 > nh} ∪ {T2 − T1 = h}.
Comme P(T2 − T1 ≤ h) → 0 quand h → 0, nh → t (avec nh ≥ t)

P(T1 > t | X0 = x) = lim P(X0 = Xh = ... = Xnh | X0 = x)
h→0

= lim [Pxx (h)]n .
h→0

L'existence de cette dernière limite entraîne que

1
lim [1 − Pxx (h)] → qx [0, +∞],
h→0 h
et donc

P(T1 > t | X0 = x) = e−qx t .
D'où nécessairement qx < 0 et qx = 0 si seulement et x est absorbant. On pose Qxx = −qx .
La démonstration de l'existence des limites de h1 Pxy (h) pour x 6= y se fait de façon analogue :
12

{T1 ≤ t, Z0 = x, Z1 } =

lim

h→0,nh→t

∪1≤m≤n {X0 = Xh = ... = X(m−1)h = x, Xmh = y}

1 − Pxx (h)n
Pxy (h)
h→0 1 − Pxx (h)
1
1 − e−qx t
lim Pxy (h).
=
qx
h

P(T1 ≤ t, Z1 = y | X0 = x) = lim

Donc Qxy = lim h1 Pxy (h) existe pour x 6= y et

P(T1 ≤ t, Z1 = y | X0 = x) = 1 − e−qx t

Qxy
qx

D'où

P(T1 ≤ t, Z1 = y | X0 = x) = P(T1 ≤ t | X0 = x)P(Z1 = y | X0 = x)
et

P(Z1 = y | X0 = x) =

Qxy
.
qx



1.2.2 Etats récurrents et transitoires
On note Rx = inf{t > 0 : Xt = x} le premier instant où la chaîne retoune en x.

Dé nition 1.9 L'état x E est dit récurrent si P(Tx < ∞) = 1 et transitoire dans le cas
contraire.

Dé nition 1.10 Une chaîne de Markov est dite irréductible si E est constitué d'une
unique classe d'équivalence. Elle est dite récurrente irréductible si elle est irréductible et
si tous les états sont récurrents.

Théorème 1.2 Soit (Xt )t≥0 un processus markovien de sauts irréductible. Alors un état
x E est récurrent positif si et seulement si tous les états sont récurrents positifs, si et
13

seulement si il existe une probabilité invariante Π, et dans ce cas
Ex (Rx ) =

1
Π x qx

∀x E.

Preuve
Si x est récurrent positif pour (Xt )t≥0 ,alors x est récurrent pour la chaîne incluse (Zn )n≥0 .
On désigne par γyx le nombre moyen de visites à l'état y lors d'une excursion de (Zn )n≥0
partant de x .Il résulte de ce que la durée de chaque séjour à l'état y est indépendante de
la chaîne incluse, et d'espérance

1
qy

que

Ex (Rx ) =

X γyx
yεE

qy

.

La condition x récurrent positif entraîne donc l'existence d'une mesure invariante de
masse nie, donc d'une probabilté invariante.
Supposons réciproquement qu'il existe une probabilité Π solution de

ΠQ = 0. Alors la mesure qΠ est invariante par P, et pour tout x, y E ,
qy Π y
qx Πx
est le nombre moyen de visites à l'état y au cours d'une excursion de (Zn≥0 )n≥0 partant
de x. Donc

Ex (Rx ) =

X Πy
1
=
< ∞ ∀x, y E
q
q
x Πx
x Πx
yεE

et n'importe quel état x E est récurrent positif.

14

Chapitre 2
Files d'attente unique
2.1 Dé nitions
Dé nition 2.1 Une le simple (ou station) est un système constitué d'un ou plusieurs
serveurs et d'un espace d'attente. Elle est caractérisée par le processus d'arrivée des
clients, le temps de service ainsi que sa structure et sa discipline de service.

2.1.1 Processus d'arrivée ou processus de renouvellement
Dé nition 2.2 Le processus de comptage (Nt )t≥0 est un processus de renouvellement si
les variables aléatoires Tn sont des variables indépendantes et identiquement distribuées.
La loi décrivant le temps d'interarrivée su t alors à caractériser le processus de renouvellement.
Tn étant le temps d'arrivée du nime client.

Remarque 2.1 La plupart du temps, l'arrivée des clients à une le simple est supposée
d'ecrite par un processus de renouvellement. Le processus d'arrivée le plus simple et le plus
couramment employé est le processus de Poisson. C'est un processus de renouvellement
qui est tel que les interarrivées sont distribuées selon une loi exponentielle.

Dé nition 2.3 Le débit moyen d'entré noté de est le nombre moyen de clients arrivés
dans le système par unité de temps, pendant la période d'observation [0,t].
15

débit moyen de sortie noté ds est le nombre moyen de clients ayant quitté le système
par unité de temps, pendant la période d'observation [0,t].

Figure 2.1 Modèle d'une le d'attente simple à un serveur

2.1.2 Temps de service
Dé nition 2.4 On appelle temps de service le temps séparant l'arrivée et le départ d'un
client.

2.1.3 Structure et discipline de service
Nombre de serveurs
Une station peut disposer de plusieurs serveurs en parallèle. Soit C le nombre de serveurs.
Dès qu'un client arrive à la station, soit il y a un serveur de libre et le client entre instantanément en service, soit tous les serveurs sont occupés et le client se place dans la
le 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
16

des autres. Une station particulière est la station IS (in nite servers) dans laquelle le
nombre de serveurs est in ni. Cette station ne comporte donc pas de le d'attente. Dès
qu'un client s'y présente, il trouve en e et instantanément un serveur disponible et entre donc directement en service. Elle permet de représenter des systèmes pour lesquels
le nombre de serveurs est toujours supérieur au nombre de clients qui peuvent s'y trouver.

Capacité de la file
La capacité de la le à accueillir des clients en attente de service peut être nie ou in nie.
Soit K la capacité de la le (incluant le ou les clients en service). Une le à capacité
illimitée véri eK = +∞. Lorsque la capacité de la le est limitée et qu'un client arrive
alors que cette dernière est pleine, le client est perdu.

Discipline de service
-FIFO ( rst in, rst out) ou FCFS ( rst come rst served) ou PAPS (premier arrivé,
premier servi) : c'est la le standard dans laquelle les clients sont servis dans leur ordre
d'arrivée.
-LIFO : (last in, rst out) ou LCFS (last come, rst served) ou DAPS (dernier arrivé,
premier servi).
-RANDOM (aléatoire) : Le prochain client qui sera servi est choisi aléatoirement dans la
le d'attente.
-Round-Robin(cyclique) : Tous les clients de la le d'attente entrent en service à tour
de rôle, e ectuant un quantum Q de leur temps de service et sont replacés dans la le,
jusqu'à ce que leur service soit totalement accompli.
-PS (Processor Sharing). C'est le cas limite de la distribution Round-Robin lorsque le
quantum de temps Q tend vers 0.

2.1.4 Notations de Kendall
Dé nition 2.5 On appelle notation de Kendall la notation T/Y/C/K/m/Z avec
T :distribution d'interarrivée
17

Y :distribution de service
C :nombre de serveurs
K : capacité de la le
m :population des usagers
Z :discipline de service.
Lorsque les trois derniers éléments de la notation de Kendall ne sont pas précisés, il est
sous entendu que K = +∞, m = +∞ et Z=FIFO.

2.2 Files d'attente Markovienne
2.2.1 File d'attente M/M/1
Dé nition 2.6 Une le d'attente M/M/1 est une le d'attente dont le processus des
arrivées est un processus de Poisson d'intensité λ, et que les temps de service sont i.i.d.
de loi commune la loi exponentielle de paramètre µ.

Figure 2.2 Graphe associé à la le d'attente M/M/1.
Notons λ le taux des arrivées : λ1

est le temps moyen entre deux arrivées consécutifs.

Dans la suite, Xt désigne le nombre de clients présents dans le système à l'instant t.

Théorème 2.1 Le nombre de clients Xt présents dans le système (au guichet + en attente) à l'instant t est alors un processus markovien de sauts à valeurs dans N de générateur in nitésimal Q donné par :
Qx,x+1 = λ, x N ; Qx,x−1 = µ, x ≥ 1 ; Qx,y = 0 si | x − y |≥2 ;
Q00 = −λ ; Qx,x = −(λ + µ) si x ≥ 1
18

Preuve
Soient t ≥ 0 xé et x N. Si on note (Ns ) le processus des arrivées, et S le temps d'attente
à partir de t pour que le service en cours à l'instant t se termine, on a :

P(Xt+h = x + 1|Xt = x) = P(Nt+h − Nt = 1, S > h) + ◦(h)
= P(Nt+h − Nt = 1)P(S > h) + ◦(h)
Z +∞
µ exp(−µs)ds + ◦(h)
= exp(−λh)λh
h

= exp(−λh)λh exp(−µh) + ◦(h)

Car les variables aléatoires S et Nt+h − Nt sont indépendantes. De plus S ,→ ε(µ) et

Nt+h − Nt est une variable aléatoire de loi de poisson de paramètre λh.
En appliquant le théorème 1.1 on a :

P(Xt+h = x + 1|Xt = x)
Px,x+1 (h)
= lim
h→0
h→0
h
h
lim


= Qx,x+1

P(Xt+h = x − 1|Xt = x) = P(Nt+h − Nt = 0, S ≤ h) + ◦(h)
= P(Nt+h − Nt = 0)P(S ≤ h) + ◦(h)
Z h
= exp(−λh)
µ exp(−µs)ds + ◦(h)
0

= exp(−λh)(1 − exp(−µh)) + ◦(h)

On a utilisé l'indépendance du processus des arrivées et du temps de service. En appli-

19

quant le théorème 1.1 on obtient :

Px,x−1 (h)
P(Xt+h = x − 1|Xt = x)
= lim
h→0
h→0
h
h
lim


= Qx,x−1
En outre, par le même raisonnement, pour | x − y |≥ 2

P(Xt+h = y|Xt = x) = ◦(h)
.

Px,y (h)
P(Xt+h = y|Xt = x)
= lim
h→0
h→0
h
h
lim

=0
= Qx,y
Pour x = y ≥ 1 en appliquant le théorème 1.1 on a :
P
Qx,x = − y N\{x} Qx,y = −(Qx,x+1 + Qx,x−1 ) = −(λ + µ)
P
P
Q0,0 = − y N\{0} Q0,y = −(Q0,1 + y N\{0;1} Q0,y ) = −(λ + 0)

Dé nition 2.7 Le nombre moyen de clients présents dans le système est la moyenne
de Xt .

Proposition 2.1 .
1)Si λ > µ, alors le processus (Xt )t≥0 est transitoire.
2)Si λ < µ, alors le processus (Xt )t≥0 est récurrent positif.
3)Si λ = µ, alors le processus (Xt )t≥0 est récurrent nul.

Preuve
Supposons que λ > µ, alors le nombre moyen d'arrivées par unité de temps est supérieur
20

au nombre moyen de départs par unité de temps. Par conseqent : Xt −→ +∞ quand

t → +∞,d'où le prémier résultat.
Supposons que λ < µ,alors le nombre moyen d'arrivées par unité de temps est inférieur
au nombre moyen de départs par unité. Par consequent

Xt → 0 quand t → +∞, d'où le deuxième résultat. Suppons que
λ = µ,alors le nombre moyen d'arrivées par unité de temps est égal au nombre moyen de
départs par unité de temps, d'où le troisième résultat.

Proposition 2.2 Si λ < µ, alors le processus (Xt )t≥0 est récurrent positif, de probabilité
invarriante :

Πx =

λ
1−
µ

x
λ
µ

(2.1)

Preuve
Si λ < µ, alors le processus (Xt )t≥0 est récurrent positif. Voir la proposition (2.1)
Supposons que Π est une mesure invariante. Alors Π véri e les équations suivantes :

Πx (Qx,x+1 + Qx,x−1 ) = Πx+1 Qx+1,x + Πx−1 Qx−1,x
Π0 Q0,1 = Π1 Q1,0 .
Par suite :

Πx (λ + µ) = Πx+1 µ + Πx−1 λ
Π0 λ = Π1 µ
λ
Π1 = Π0 .
µ
En plus µΠ2 = (λ + µ) µλ Π0 − λΠ0 ⇒ Π2 = ( µλ )2 Π0 .

Par récurrence on obtient Πx = Π0 ( µλ )x .
Or Π0 = 1 − µλ .
21

Donc Πx = (1 − µλ )( µλ )x

Proposition 2.3 Soient Xt le nombre de clients présents dans le système à l'instant t
et R0 le premier instant où le processus retourne en 0. Alors les a rmations suivantes
sont véri ées :
A l'équilibre le nombre moyen de client présent dans le système vaut
EΠ (Xt ) =


X

λ
,
µ−λ

(2.2)

1
µ
=
,
q0 Π 0
λ(µ − λ)

(2.3)

xΠx =

x=1

L'espérance du temps de retour en 0 est
E0 (R0 ) =

Le temps moyen entre deux périodes où le guichet est vide vaut
E0 (R0 ) −

1
1
=
.
q0
µ−λ

(2.4)

Preuve
Si Xt désigne le nombre de client présent dans le système, alors à l'équilibre ce nombre
moyen est :

EΠ (Xt ) =


X

xΠx

x=1


x

X
λ
λ
=
x 1−
µ
µ
x=1

x+1 !


x
X
λ
λ
−x
=
x
µ
µ
x=1
X


x X


∞ x
x
X
λ
λ
λ
λ
=
+
x

x
+
µ
µ
µ
µ
x=2
x=2
x=2
∞ x
X
λ
=
µ
x=1
=

µ
.
µ−λ
22

∀x E , si Rx désigne le premier instant où le processus retourne en x, alors d'après le
théorème 1.2

E(Rx ) =

1
Πx qx

En particulier pour x = 0 on a :

E(R0 ) =

1
µ
=
.
Π0 q0
λ(µ − λ)

Le temps moyen entre deux périodes où le guichet est vide est la di érence entre l'espérance du temps de retour en 0 et le temps moyen entre deux départ consécutifs.D'où

E0 (R0 ) −

1
µ
1
=

q0
λ(µ − λ) λ
1
=
µ−λ



Dé nition 2.8 On appelle temps moyen passé d'un client dans le système, le temps
moyen e ectué par un client depuis son arrivé jusqu'à la sortie du système.

Proposition 2.4 Soit Xt le nombre de clients présents dans le système à l'instant t.
Alors le temps moyen passé d'un client dans le système est :
EΠ (Xt + 1)
1
=
.
µ
µ−λ

(2.5)

Preuve
Supposons qu'un client arrive et trouve x clients dans le système à l'instent t. Alors

Xt = x et le temps moyen de ce client pour sortir du système est

23

x+1
.Donc
µ

le temps

moyen pour tout client est :

EΠ (Xt + 1)
EΠ (Xt ) 1
=
+
µ
µ
µ
1
λ
+
=
µ (µ − λ) µ
1
=
µ−λ
Dans notre étude ,nous allons établir la formule de Little. On suppose que les hypothèses suivantes sont véri ées.

H1)t−1

Rt
0

Xs ds −→ X p.s., quand t −→ ∞ où X est une constante.

H2)Il existe une suite aléatoire tn −→ ∞ n −→ ∞ telle que Xtn → 0.

H3) Supposons que les durées de séjour de tous les clients sont nies. Notons Dn la
durée du séjour du nime client arrivé après l'instant 0, il existe une constante D telle que
n

1X
Dk .
D = lim
n→∞ n
k=1

Théorème 2.2 formule de little.
On considère un système de service tel que le nombre moyen d'arrivées par unité de temps
soit égal à λ, et qui véri e les hypothèses (H1), (H2) et (H3) ci-dessus. Alors
X = λD.

(2.6)

Preuve
Désignons par N(t) le nombre de clients arrivés avant l'instant t. Soit (tn )n N une suite
telle que Xtn −→ 0 et tn −→ ∞ quand n −→ ∞. On a :

24

n
X

Z

tn

Xs ds.

Dk =
0

k=1

Donc

1
tn

Z
0

tn

n

N (tn )
1 X
Xs ds =
×
Dk .
tn
N (tn ) k=1

Par passage à la limite, et en utilisant (H1), (H2), (H3), on obtient

X = λD.



Remarque 2.2 Notons que la formule de Little est très intuitive. Car elle établit une
rélation de proportionnalité entre le nombre moyen de clients, le temps moyen passé dans
le système et le débit moyen du même système.

2.2.2

File d'attente M/M/1/K

Dé nition 2.9 On appelle modèle M/M/1/K de le d'attente, un modèle identique au
modèle M/M/1,dont la "salle d'attente" contient au plus K clients (dont celui en train de
se faire servir). Ceci signi e que tout client qui arrive quand la salle d'attente est pleine
est rejeté.

Figure 2.3 Graphe associé à la le d'attente M/M/1/K : K=N
Proposition 2.5 Soit Xt le nombre de clients présents dans le système à l'instant t.
Alors (Xt )≥0 est un processus markovien de sauts à valeurs dans E = {0, 1, 2..., K}, de
générateur in nitésimal donné par :
25

Qx,x+1 = λ si 0 ≤ x ≤ K − 1 ;Qx,x−1 = µ si 1 ≤ x ≤ K
Qx,y = 0 si | x − y |≥ 2
Q0,0 = −λ ; Qx,x = −(λ + µ) si 1 ≤ x ≤ K − 1 ;QK,K = −µ

Preuve
Soient 0 ≤ x ≤ K − 1,et t ≥ 0 xé. Si on note (Ns ) le processus des arrivées, et S le
temps d'attente à partir de t pour que le service en cours à l'instant t se termine, on a :

P(Xt+h = x + 1|Xt = x) = P(Nt+h − Nt = 1, S > h) + ◦(h)
= P(Nt+h − Nt = 1)P(S > h) + ◦(h)
Z +∞
= exp(−λh)λh
µ exp(−µs)ds + ◦(h)
h

= exp(−λh)λh exp(−µh) + ◦(h).

Car les variables aléatoires S et Nt+h − Nt sont indépendantes. De plus S ,→ ε(µ) et

Nt+h − Nt est une variable aléatoire de loi de poisson de paramètre λh.
En appliquant le théorème 1.1 on a :

P(Xt+h = x + 1|Xt = x)
Px,x+1 (h)
= lim
h→0
h→0
h
h
lim


= Qx,x+1
Soit 1 ≤ x ≤ K on a :

P(Xt+h = x − 1|Xt = x) = P(Nt+h − Nt = 0, S ≤ h) + ◦(h)
= P(Nt+h − Nt = 0)P(S ≤ h) + ◦(h)
Z h
= exp(−λh)
µ exp(−µs)ds + ◦(h)
0

= exp(−λh)(1 − exp(−µh)) + ◦(h)
26

On a utilisé l'indépendance du processus des arrivées et du temps de service. En appliquant le théorème 1.1 on obtient :

Px,x−1 (h)
P(Xt+h = x − 1|Xt = x)
= lim
h→0
h→0
h
h
lim


= Qx,x−1
En outre, par le même raisonnement, pour | x − y |≥ 2

P(Xt+h = y|Xt = x) = ◦(h).

Px,y (h)
P(Xt+h = y|Xt = x)
= lim
h→0
h→0
h
h
lim

=0
= Qx,y
Pour x = y ≥ 1 en appliquant le théorème 1.1 on a :
P
Qx,x = − y E\{x} Qx,y = −(Qx,x+1 + Qx,x−1 ) = −(λ + µ)

Q0,0 = −

X

X

Q0,y = −(Q0,1 +

y E\{0}

Q0,y )

y E\{0;1}

= −(λ + 0)

Soit 0 ≤ x ≤ K

QK,K = −

X

QK,y = −(QK,0 +

y E\{K}

X
y E\{K;0}

= −(0 + QK,K−1 )
= −µ

27

QK,y )



Proposition 2.6 Soit (Xt )t≥0 le processus Markovien de sauts du modèle M/M/1/K .
Alors (Xt )t≥0 est irreductible, récurrent positif, de probabilité invariante Π dé nie par :
x
λ
1 − λ/µ
Πx =
µ
1 − (λ/µ)K+1

(2.7)

si λ < µ et 0 ≤ x ≤ K .
Πx =

1
K +1

si λ = µ.

Preuve
Si λ < µ, alors le processus (Xt )t≥0 est récurrent positif. Voir la proposition (2.1)
Supposons que Π est une mesure invariante. Alors Π véri e les équation suivantes :

Πx (Qx,x+1 + Qx,x−1 ) = Πx+1 Qx+1,x + Πx−1 Qx−1,x
Π0 Q0,1 = Π1 Q1,0 .
Par suite :

Πx (λ + µ) = Πx+1 µ + Πx−1 λ
Π0 λ = Π1 µ
λ
Π1 = Π0 .
µ
En plus µΠ2 = (λ + µ) µλ Π0 − λΠ0 ⇒ Π2 = ( µλ )2 Π0 .

Par récurrence on obtient Πx = Π0 ( µλ )x .
Or

Π0 + Π1 + ... + ΠK = 1.
28

(2.8)

Donc

Π0

λ
1 + + ... +
µ

D'où

1−
Π0
soit

K !
λ
= 1.
µ

K+1
λ
µ

1−

λ
µ

=1

1 − µλ
Π0 =
K+1 .
1 − µλ

Par consequent :

x
λ
Πx =
µ

1 − µλ
K+1 .
1 − µλ

Si λ = µ,tout les clients ont la même chance d'être en service. Donc la loi initiale est la
loi uniforme sur {0, 1, ..., K}.Par consequent ∀x E Πx =

1
K+1



2.2.3

Modèle de le d'attente M/M/s

Dé nition 2.10 Un modèle de le d'attente M/M/s est un modèle de le d'attente simple. Elle est composée de s guichets "serveurs", et d'une salle d'attente de capacité in nie.
Les temps de service aux di érents guichets sont indépendants.

Figure 2.4 Graphe associé à la le d'attente M/M/s.
Proposition 2.7 Soit Xt le nombre de clients présents dans le système à l'instant t.
Alors (Xt )t≥0 est un processus Markovien de sauts à valeurs dans E={0,1,...,n,n+1,...},
et de générateur in nitésimal Q donné par :

29

Q0,1 = λ, Q0,x = 0 si x > 1 ;

pour 1 ≤ x ≤ s Qx,x+1 = λ Qx,x−1 = xµ. Qx,y = 0 si |x − y| > 1
pour x ≥ s Qx,x+1 = λ, Qx,x−1 = sµ. Qx,y = 0 si | x − y |> 1

Preuve
Soient 0 ≤ x ≤ s, et t ≥ 0 xé. Si on note (Ns ) le processus des arrivées, et S le temps
d'attente à partir de t pour que le service en cours à l'instant t se termine, on a :

P(Xt+h = x + 1|Xt = x) = P(Nt+h − Nt = 1, S > h) + ◦(h)
= P(Nt+h − Nt = 1)P(S > h) + ◦(h)
Z +∞
= exp(−λh)λh
xµ exp(−µx)ds + ◦(h)
h

= exp(−λh)λh exp(−µh) + ◦(h).

Car les variables aléatoires S et Nt+h − Nt sont indépendantes. De plus S ,→ ε(µ) et

Nt+h − Nt est une variable aléatoire de loi de poisson de paramètre λh.
En appliquant le théorème 1.1 on a :

P(Xt+h = x + 1|Xt = x)
Px,x+1 (h)
= lim
h→0
h→0
h
h
lim


= Qx,x+1

30

Soit 1 ≤ x ≤ s on a :

P(Xt+h = x − 1|Xt = x) = P(Nt+h − Nt = 0, S ≤ h) + ◦(h)
= P(Nt+h − Nt = 0)P(S ≤ h) + ◦(h)
Z h
xµ exp(−xµv)dv + ◦(h)
= exp(−λh)
0

= exp(−λh)(1 − exp(−xµh)) + ◦(h)

On a utilisé l'indépendance du processus des arrivées et du temps de service. En appliquant le théorème 1.1 on obtient :

Px,x−1 (h)
P(Xt+h = x − 1|Xt = x)
= lim
h→0
h→0
h
h
lim

= xµ
= Qx,x−1
En outre, par le même raisonnement, pour | x − y |≥ 2

P(Xt+h = y|Xt = x) = ◦(h).

P(Xt+h = y|Xt = x)
Px,y (h)
= lim
h→0
h→0
h
h
lim

=0
= Qx,y
Soient x ≥ s, et t ≥ 0 xé. Si on note (Ns ) le processus des arrivées, et S le temps
d'attente à partir de t pour que le service en cours à l'instant t se termine, on a :

31

P(Xt+h = x + 1|Xt = x) = P(Nt+h − Nt = 1, S > h) + ◦(h)
= P(Nt+h − Nt = 1)P(S > h) + ◦(h)
Z +∞
sµ exp(−sµv)dv + ◦(h)
= exp(−λh)λh
h

= exp(−λh)λh exp(−sµh) + ◦(h).

Car les variables aléatoires S et Nt+h − Nt sont indépendantes. De plus S ,→ ε(µ) et

Nt+h − Nt est une variable aléatoire de loi de poisson de paramètre λh.
En appliquant le théorème 1.1 on a :

Px,x+1 (h)
P(Xt+h = x + 1|Xt = x)
= lim
h→0
h→0
h
h
lim


= Qx,x+1
Soit x ≥ s on a :

P(Xt+h = x − 1|Xt = x) = P(Nt+h − Nt = 0, S ≤ h) + ◦(h)
= P(Nt+h − Nt = 0)P(S ≤ h) + ◦(h)
Z h
= exp(−λh)
sµ exp(−sµv)dv + ◦(h)
0

= exp(−λh)(1 − exp(−sµh)) + ◦(h)

On a utilisé l'indépendance du processus des arrivées et du temps de service. En appli-

32

quant le théorème 1.1 on obtient :

Px,x−1 (h)
P(Xt+h = x − 1|Xt = x)
= lim
h→0
h→0
h
h
lim

= sµ
= Qx,x−1
En outre, par le même raisonnement, pour | x − y |≥ 2

P(Xt+h = y|Xt = x) = ◦(h).

Px,y (h)
P(Xt+h = y|Xt = x)
= lim
h→0
h→0
h
h
lim

=0
= Qx,y



Proposition 2.8 Soit Xt le nombre de clients présents dans le système à l'instant t.
Alors si λ < µs, alors (Xt )t≥0 est récurent positif de loi invariante Π dé nie par :
1)

Πx
Π0

=

(λ/µ)x
x!

si 0 ≤ x ≤ s

2)

Πx
Π0

=

(λ/µ)x
sx−s s!

si x>s .

Preuve
Si λ < µs, alors le processus (Xt )t≥0 est récurent positif et admet une loi invariante Π.
Considèrons l'équation d'équilibre ponctuel

Πx Qx,x+1 = Πx+1 Qx+1,x d'inconnu Πx .

33

Si x = 1 , alors Π1 = µλ Π0 .
Si x = 2, alors Π2 =

(λ)2
Π.
2(µ)2 0

Par suite

Πx =

λ0
µ1

Πx =

λ
µ

×

×

λ1
µ2

λ


× ... ×

× ... ×

λx−1
µx

λ


× Π0

× Π0 =

(λ/µ)x
x!

Supposons que x > s, alors Πx =

× Π0 si 0 ≤ x ≤ s

λx
Π
µ×2µ×...×sµ×(sµ)x−s 0

=

λx
Π
s!µx sx−s 0



Remarque 2.3 Les deux cas qui conduisent à une formule simple dont le cas où s = 1
(déjà traité dans le modèle M/M/1) et le cas s = ∞, auquel cas
Π0 = exp(−λ/µ)

(2.9)

et
Πx = exp(−λ/µ)

(λ/µ)x
,
x!

(2.10)

i.e. la probabilité invariante est la loi de Poisson λ/µ.

Théorème 2.3 Théorème de Burke
Si λ < sµ, à l'équilibre le processus des départs est un processus de Poisson d'intensité λ.

Preuve
Supposons que λ < sµ. Le processus (Xt )t≥0 est réversible par rapport à Π. Donc à
l'équilibre" (i.e. sous PΠ ),les processus (XT −t )0≤t≤T et (Xt )0≤t≤T ont même loi, et les
départs de Xt sont les arrivés XT −t poisson d'intensité λ.

Ce résultat est important dans l'étude des réseaux de les d'attentes car il caractérise la distribution des clients rejoignant une seconde le après avoir été servis dans une
première le.
34

2.2.4 File d'attente M/M/s/s
Hypothèse :.
-les clients arrivent selon un processus de Poisson de paramètre λ > 0,
- le temps de service est une loi exponentielle de paramètre µ > 0,
- il y a s serveurs montés en parallèle,
-il n'y a pas d'attente.

Ce système est modelisé par un processus de naissance et mort tel que :




λx = λ (0 ≤ x ≤ s)







 µx = sµ (0 ≤ x ≤ s)

Dé nition 2.11 Un modèle de le d'attente M/M/s/s est un modèle de le d'attente
simple, composé de s guichets sans salle d'attente. Dans ce modèle tout client arrivant
alors que les s guichets sont occupés est rejeté. C'est le modèle de fonctionnement d'un
central téléphonique.

Proposition 2.9 Soit Xt le nombre de clients présents dans le système à l'instant t.
Alors (Xt )t≥0 constitue un processus Markovien de sauts à valeurs dans E = {0, 1, ..., s},de
générateur in nitésimal Q donné par :
Q0,1 = λ, Q0,x = 0, x > 1 ;

si 0 < x < s, alors
Qx,x+1 = λ, Qx,x−1 = xµ, Qx,y = 0, |x-y|>1 ;
Qs,s−1 = sµ, Qs,y = 0,y 6= s, y 6= s − 1.

Preuve
Soient 0 ≤ x < s, et t ≥ 0 xé. Si on note (Ns ) le processus des arrivées, et S le temps
35

d'attente à partir de t pour que le service en cours à l'instant t se termine, on a :

P(Xt+h = x + 1|Xt = x) = P(Nt+h − Nt = 1, S > h) + ◦(h)
= P(Nt+h − Nt = 1)P(S > h) + ◦(h)
Z +∞
xµ exp(−xµs)ds + ◦(h)
= exp(−λh)λh
h

= exp(−λh)λh exp(−µh) + ◦(h).

Car les variables aléatoires S et Nt+h − Nt sont indépendantes. De plus S ,→ ε(µ) et

Nt+h − Nt est une variable aléatoire de loi de poisson de paramètre λh.
En appliquant le théorème 1.1 on a :

Px,x+1 (h)
P(Xt+h = x + 1|Xt = x)
= lim
h→0
h→0
h
h
lim


= Qx,x+1
Soit 1 < x < s on a :

P(Xt+h = x − 1|Xt = x) = P(Nt+h − Nt = 0, S ≤ h) + ◦(h)
= P(Nt+h − Nt = 0)P(S ≤ h) + ◦(h)
Z h
= exp(−λh)
x exp(−xµv)dv + ◦(h)
0

= exp(−λh)(1 − exp(−xµh)) + ◦(h)

On a utilisé l'indépendance du processus des arrivées et du temps de service. En appli-

36

quant le théorème 1.1 on obtient :

Px,x−1 (h)
P(Xt+h = x − 1|Xt = x)
= lim
h→0
h→0
h
h
lim

= xµ
= Qx,x−1
En particulier pour x = s Qs,s−1 = sµ et pour y 6= s et y 6= s − 1 Qs,y = 0. En outre, par
le même raisonnement, pour | x − y |≥ 2

P(Xt+h = y|Xt = x) = ◦(h).

Px,y (h)
P(Xt+h = y|Xt = x)
= lim
h→0
h→0
h
h
lim

=0
= Qx,y



Proposition 2.10 Si (Xt )t≥0 designe le processus Markovien de sauts du modèle M/M/s/s.
Alors (Xt )t≥0 admet une distribution stationnaire donnée par la "loi de Poisson tronquée" :

s
(λ/µ)x X (λ/µ)y
Πx =
/
,
x!
y!
y=0

Preuve
Considèrons l'équation d'équilibre ponctuel

Πx Qx,x+1 = Πx+1 Qx+1,x d'inconnu Πx .

Si x = 1 , alors Π1 = µλ Π0 .
Si x = 2, alors Π2 =

(λ)2
Π.
2(µ)2 0

Par suite
37

si

0 ≤ x ≤ s.

(2.11)

Πx =

λ0
µ1

Πx =

λ
µ

×

×

λ1
µ2

λ


× ... ×

× ... ×

λx−1
µx

λ


× Π0

× Π0 =

(λ/µ)x
x!

× Π0 si 0 ≤ x ≤ s

Compte-tenu de la condition Π0 + Π1 + ... + Πs = 1

On obtient :

Πx =

y
(λ/µ)x Ps
/ y=0 (λ/µ)
,
x!
y!

si 0 ≤ x ≤ s

Remarque 2.4 Si le système est plein, alors x ≥ s.Dans ce cas Πx = Πs , s clients
restent dans le système et x − s clients sont rejetés. La proportion du temps pendant
laquelle le système est plein est :
Πs =

s
(λ/µ)s X (λ/µ)y
/
.
s!
y!
y=0

(2.12)

Cette formule est connue sous le nom d'Erlang.

Exemple 2.1 Atelier de réparation
Une usine fait fonctionner s machines. Chacune d'elles tombe en panne au taux λ (l'instant de panne est une variable aléatoire de loi exponentielle de paramètre λ). L'usine est
équipée d'un atelier de réparation. Les temps de réparation sont exponentiels de paramètre
µ.

Désignons par Xt le nombre de machines en état de marche à l'instant t à valeurs dans E
= {0, 1, . . . , s}. (Xt )t≥0 est un processus markovien de saut. Le générateur in nitésimal
de ce processus est le même que celui de la le M/M/s/s, mais avec λ et µ intervertis !
Donc la probabilité invariante de ce processus est
s
(µ/λ)x X (µ/λ)y
Πx =
/
x!
y!
y=0

38

(2.13)

Le taux de panne global est

λg =

s
X

λx Πx = µ

x=1

s−1
s
X
(µ/λ)x X (µ/λ)y
/
x!
y!
x=0
y=0

(2.14)

Le nombre moyen de machines réparées par unité de temps vaut

nr = µ(1 − Πs ) = λb

(2.15)

Exemple 2.2 Files d'attente en série
Supposons que les clients demandent deux services : ils font d'abord la queue au guichet A,
puis au guichet B, dont les deux temps de service sont indépendants, le temps de service
de A suivant une exponentielle α, et celui de B une loi exponentielle β .
Quelle est la longueur moyenne de la le au guichet B ? Notons Xt le nombre de clients
(en service ou en attente) au guichet A, Yt le nombre de clients au guichet B.
Les arrivées au guichet A sont supposées former un processus de Poisson d'intensité λ.
Si λ > α, Xt −→ ∞ , on peut admettre qu'il y a toujours des clients en A, et ils sortent
suivant un processus de Poisson d'intensité α. Si λ < α, d'après le théorème de Burke
les départs de A forment un processus de Poisson d'intensité λ. Il est donc naturel de
prétendre que le processus des arrivées en B est un processus de Poisson d'intensité α ∧ λ.
Donc Yt est récurrent positif ssi α ∧ λ < β , et dans ce cas la longueur moyenne de la les
en B est

α∧λ
β−α∧λ

. Les deux les sont récurrentes positives si λ < α ∧ β .

Dans ce cas, à l'équilibre, le temps moyen passé par un client dans le système A+B est
1
1
+
α−λ β−λ

(2.16)

2.2.5 File d'attente M/G/∞
Les arrivées forment un processus de Poisson d'intensité λ. Les temps de service sont
i.i.d., de loi commune "générale", de fonction de répartition F (t) = P(T ≤ t). Il y a une

39

in nité de serveurs' ce qui simpli e énormément l'analyse, en évitant toute interaction
entre les clients.

Dé nition 2.12 Un modèle de le d'attente M/G/∞ est un système de le d'attente
composé d'une in nité de serveurs. Les arrivées forment un processus de poisson d'intensité λ. Les temps de service sont i.i.d de même loi.

Le nombre de clients arrivés avant t suit une loi de Poisson de paramètre λt.
Si Nt = n est le nombre de clients arrivés de façon aléatoire à l'instant t, alors les temps
d'arrivée A1 , ..., An de ces clients sont i.i.d. de loi uniforme sur [0, t].
Si F est la fonction de répartition du temps T de sevice d'un client, alors pour chacun de
ces clients, le service n'est pas terminé avec la probabilité

1
p=
t

Z
0

t

1
P(T > s)ds =
t

Z

t

(1 − F (s))ds.

(2.17)

0

Remarque 2.5 La loi conditionnelle de Xt , sachant que Nt = n, est la loi binomiale de
paramètre (n, p).

Proposition 2.11 Soit Xt le nombre de clients présents dans le système à l'instant t,
alors la loi de Xt est la loi de Poisson de paramètre
λ

Rt
0

(1 − F (s))ds.

Preuve

40

La preuve de cette proposition utilise la remarque précédente.

P(Xt = x) =


X

P(Xt = x | Nt = n)P(Nt = n)

n=0

=


X

Cnx px (1 − p)n−x e−λt (λt)/n!

n=0
x
−λt (λpt)

=e
=

x!


X
(λ(1 − p)t)n−x

(n − x)!

n=x
x

e−λpt (λpt)
.
x!

D'où le résultat est prouvé.

Corollaire 2.1 Si E(T ) < ∞, alors la le a comme loi limite, la loi de Poisson de
paramètre λE(T ).Où
Z



Z
(1 − F (s))ds =

E(T ) =



P(T > s)ds

(2.18)

0

0

Preuve
Supposons que E(T ) < ∞,alors

Z

t

lim E(Xt ) = lim λ (1 − F (s))ds
t→+∞
Z +∞ 0
(1 − F (s))ds


t→+∞

0

= λE(T )
<∞

∀t ≥ 0 Xt est une variable aléatoire de loi de poisson. Comme E(Xt ) < ∞, alors il existe
une variable aléatoire notée X∞ telle que

lim Xt = X∞ .

t→∞

41

Comme Xt est une variable aléatoire de loi de poisson. Alors X∞ est une variable aléatoire
de loi de poisson. Par suite E(X∞ ) = λE(T ).
Par consequent :
La le a comme loi limite, la loi de Poisson de paramètre λE(T ).

2.3 Etude de la File d'attente M/G/1
Dé nition 2.13 Un modèle de le d'attente M/G/1 est un système de le d'attente dans
lequel les clients arrivent suivant un processus de Poisson d'intensité λ > 0. Les temps
de service successifs sont des variables aléatoires i. i. d., indépendantes du processus des
arrivées.
On note ν la loi des temps de service, et L sa transformée de Laplace, ie

Z
L(u) =



e−ut ν(dt),

u>0

0

2.3.1 Méthode de la chaîne de Markov incluse
Pour tout n ≥ 0, on note Xn le nombre de clients en attente (ou en train de se faire
servir) juste après le nime départ. Pour n ≥ 0,

Xn+1 = Xn + Yn+1 − I(Xn>0 )
où Yn est le nombre d'arrivées durant le service du nime client. Le fait que Xn , n ≥ 0
est une chaîne de Markov résulte du lemme suivant :

Lemme 2.1 Pour tout n N les variables aléatoires Yn sont i. i.d., indépendantes de X0 ,
42

de loi commune de fonction génératrice
A(z) = L(λ(1 − z))

(2.19)

Preuve
Le nombre de clients en attente X0 (ou en train de se faire servir) juste après le 0ime départ,est
indépendant Yn , n ≥ 0 le nombre d'arrivées durant le service du nime client.

E(z1Y1 ...znYn ) = E[E(z1Y1 ...znYn | S1 , ..., Sn )
Z
=
E(z1Y1 ...znYn | S1 = t1 , ..., Sn = tn )ν(dt1 )ν(dt2 )...ν(dtn )
=
=

Rn
+
n
YZ
i=1
n
Y

e−λti (1−zi ) ν(dti )

R+

L(λ(1 − zi )).

i=1

Donc (Xn )n N est une chaîne de Markov. Pour tout n dans N, Xn est une variable aléatoire
à valeur dans N. Dons la chaîne de markov (Xn )n N est à valeurs dans N et irrécductible.


Posons :ρ = E(Yn ) = λµ.

2.3.2 Le cas récurrent positif
Proposition 2.12 Si ρ < 1, la chaîne (Xn )n N est récurrente positive.
Preuve
Désignons parZn le nombre de visites de la chaîne en 0 avant le nime départ. On a

Xn = X0 + Y1 + ... + Yn − n + Zn

43

Supposons la chaîne transitoire. Alors Xn −→ ∞ p. s. quand n −→ ∞, et Zn /n −→ 0
quand n −→ ∞, puisqu'il y a p. s. au plus un nombre ni de retour en 0. Mais par la loi
des grands nombres,

n−1 (Y1 + ... + Yn ) −→ ρ < 1
Donc

Y1 + ... + Yn − n −→ −∞
quand n −→ ∞, ce qui contredit le fait que Xn ≥ 0, et la chaîne est nécessairement récurrente. En prenant l'espérance dans la formule de récurrence ci-dessus. Puisque Xn ≥ 0,
On obtient

0 < 1 − ρ ≤ n−1 E(x0 ) + n−1 E(Zn ) −→

1
m0

quand n −→ ∞, où m0 est l'espérance du temps de retour en 0, d'après le théorème
ergodique. Donc

m0 ≤

1
<∞
1−ρ



44

Chapitre 3
Réseaux de les d'attente
3.1 Dé nitions
Dé nition 3.1 Un réseau de les d'attente est un ensemble de les simples (stations)
interconnectées.
Il existe des réseaux de type ouvert, fermé ou mixte

3.2 Réseaux ouvert
Dé nition 3.2 On dit qu'un réseau est ouvert,lorsque les clients arrivent de l'extérieur,
circulent dans le réseau à travers les di èrentes stations, puis quittent le réseau après une
durée bien déterminée.
Le nombre de client présent dans ce type de réseau peut varier d'un instant à l'autre.
Pour spéci er complètement un réseau ouvert, il faut bien sûr caractériser chaque
station, mais également le processus d'arrivée des clients et le routage (cheminement) des
clients dans le réseau.

a-Processus d'arrivée
Le processus d'arrivée des clients dans le réseau est décrit, comme pour une le simple,
45

à l'aide d'un processus de renouvellement (il est donc caractérisé par la distribution du
temps d'interarrivée). Si l'arrivée des clients suit un processus de Poisson, les interarrivées
sont exponentielles et sont caractérisées par un unique paramètre : le taux d'arrivée λ.
Dans le cas d'un processus d'arrivée non Poissonnien, ce paramètre reste intéressant,
puisqu'il indique le nombre moyen de clients qui arrivent dans le système par unité de
temps.

b-Routage des clients
Lorsqu'un client termine son service à une station, il faut préciser où ce client va se
rendre : soit à une autre station, soit à l'extérieur (le client quitte alors le réseau). Il
existe cependant d'autres types de routages :
- le routage vers la le la plus courte (routage dynamique) : un client quittant une station
choisira, parmi toutes les destinations possibles, la station qui comporte le moins de
clients
- le routage cyclique (routage déterministe) : les clients quittant une station choisiront à
tour de rôle chacune des stations parmi toutes les destinations possibles.

3.2.1

Réseau de Jackson ouvert

On considère un réseau constitué de N stations interconnectées. Chaque station p
(1 ≤ p ≤ N ) doit traiter les clients qui arrivent de l'extérieur, ainsi que ceux qui lui sont
envoyés par les autres stations.
Dans le modéle de Jackson, les arrivées exogènes à la station p forment un processus de
Poisson d'intensité λp0 . Chaque station est une le d'attente.
Le taux avec lequel les clients quittent la station p est µp (n), si n clients sont à la station
p. Par exemple

µp (n) = µp I(n≥0) , dans le cas d'un serveur M/M/1

46

µp (n) = n ∧ sp µp , dans le cas de s guichets M/M/s
Un client quittant la station p se dirige vers la station q avec la probabilité rpq (1 ≤ q ≤

N ), et quitte le réseau avec la probabilité rp0 . On suppose pour simpli er que rpp = 0,
1 ≤ p ≤ N ; cette hypothèse peut être levée sans di culté.

Figure 3.1 Schéma d'un réseau de Jackson ouvert.où rij = pij

47

Proposition 3.1 Le processus Xt = (Xt1 , ..., XtN ) des nombres de clients présents aux
stations 1,...,N à l'instant t est un processus Markovien de sauts à valeurs dans lespace
E = NN
+.
∀i = 1, .., N Xti est le nombre de clients présents à la station i à l'instant t.

Preuve
Pour i = 1, .., N Xti est le nombre de clients présents à la station i à l'instant t. D'après
le

chapitre 2 ∀i = 1, .., N Xti

est un processus Markovien de sauts à valeurs dans N+ .

De plus pour i 6= j Xti est indépendante de Xtj . Par consequent Xt = (Xt1 , ..., XtN ) est
un processus Markovien de sauts à valeurs dans E = NN
+.
On note ep = (0, ..., 0, 1, 0, ..., 0) le vecteur dont seule la pime coordonnée est non nulle
et vaut 1.

Les seuls termes hors diagonaux non nuls du générateur in nitésimal du processus Xt
sont
 donnés par


Qx,x+ep = λ0p , x E, 1 ≤ p ≤ N









Qx+ep ,x = µp (xp + 1)rp0 , x E, 1 ≤ p ≤ N










 Q
x E, 1 ≤ p 6= q ≤ N
x+ep ,x+eq = µp (xp + 1)rpq ,
Dans la suite nous allons nous intéresser aux ux des clients vers les di érentes stations. Si le réseau est "sans capture" chaque station peut être le point de départ d'un
client vers l'extérieur du réseau ou vers une autre station.

Dé nition 3.3 On dit que le réseau est "sans capture" si pour tout p {1, ..., N }, ∃n ≥ 0,
p1 , ..., pn {1, ..., N } tels que

rpp1 rp1 p2 ...rpn−1 pn rpn0 > 0

48

(∗)


Documents similaires


Fichier PDF uaxzh3d
Fichier PDF techniques de findelisation2
Fichier PDF mq
Fichier PDF td1 uml diagramme des cas d utilisation
Fichier PDF devoir n 4
Fichier PDF se synchroprocess


Sur le même sujet..