Processus de Naissance Et de Mort [PDF]

Zitiervorschau

République Algérienne Démocratique et Populaire Ministère de l’Enseignement Supérieur et de la Recherche Scientifique Université De M’hamed Bougara Boumerdes Faculté des Sciences Département de Mathématiques

Gestion des files d’attente Présenté par

ISSAADI Badredine Maître de conférences classe A,

Pour Master I Spécialité : Recherche Opérationnelle, Optimisation et Management Stratégique.

Année Universitaire : 2020 / 2021 Email : [email protected] [email protected]

Table des matières

Table des matières . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I

1

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

1.1

Introduction

1

1.2

Processus de comptage

1

1.3

Une relation fondamentale

2

1.4

Définition et propriété principale

3

1.4.1

Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.4.2

Propriété principale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.4.3

Graphe des transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.5

Processus de Poisson et loi exponentielle

6

1.6

Exemple

7

2

Phénomènes d’attente processus de naissance et de mort . . . . . . . . . . . . . . . . . . . . . . 9

2.1

Processus de naissance et de mort

2.1.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.1.2

Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

U.M.B.B

9

B. ISSAADI

2.1.3

Régime transitoire et régime stationnaire . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.1.3.1

Régime transitoire . . . . . . . . . . . . . . . . . . . . . . . 10

2.1.3.2

Régime stationnaire . . . . . . . . . . . . . . . . . . . . . . 11

2.1.4

Graphes des transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.5

Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2

Phénomènes d’attente

2.2.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2.2

Discipline du service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2.3

Classification des systèmes d’attente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.4

Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

14

IS SA AD I

Introduction

P

ARMI

les processus stochastiques à temps continu, le processus de Poisson occupe

Ba dr

1.1

ed in

e

1. Processus de Poisson

une place privilégiée. Il est utilisé avant tout pour décrire la réalisation dans le

temps d’événements aléatoires d’un type donné, comme par exemple : – L’arrivée de clients vers un guichet ;

– L’occurrence d’accidents dans une entreprise ;

– L’apparition de pannes dans un parc de machines ;

– L’arrivée de tâches dans l’unité centrale d’un ordinateur.

1.2

Processus de comptage

La description mathématique d’un flux d’événements aléatoires peut se faire de

deux manières différentes :

– On considère le nombre d’événements N ( t) se produisant dans l’intervalle de temps [0, t[ et on cherche à déterminer la distribution de cette variable discrète. Le processus stochastique { N ( t), t ≥ 0} est appelé processus de comptage, ses réalisations sont des fonctions en escalier non décroissantes. Notons que

N ( u + t) − N ( u) indique le nombre (aléatoire) d’événements se produisant dans l’intervalle semi-ouvert ( u, u + t].

U.M.B.B

B. ISSAADI

1.3 Une relation fondamentale

2

– On considère les intervalles de temps qui séparent les instants d’apparitions de deux événements consécutifs. Ce sont des variables aléatoires continues et positives dont on admettra généralement qu’elles sont indépendantes et identiquement distribuées. La connaissance de leur distribution commune permettra alors de déterminer les propriétés caractéristiques du processus de

Une relation fondamentale

Soit { N ( t), t ≥ 0} un processus de comptage et désignons par T n la durée séparant

le ( n − 1) − ième du n − ième événement ( n = 2, 3, . . .). En particulier, T1 est l’instant de réalisation du premier événement. La variable aléatoire T n appelée durée d’attente, représente le temps pendant lequel le processus demeure dans l’état ( n − 1), posons ensuite :

S n = T1 + T2 + · · · + T n ,

S n est le temps écoulé jusqu’à la réalisation du n − ième événement. On vérifie

" N ( t) ≤ n"

et

" N ( t) ≥ n"

et

Il en résulte que pour n = 1, , . . .

ed in

e

aisément qu’il y a équivalence pour chacune des paires d’événement suivantes : "S n+1 > t,

"S n ≤ t.

Ba dr

1.3

IS SA AD I

comptage correspondant.

N ( t) = n ⇔ N ( t) ≤ n et N ( t) ≥ n, ⇔ S n+1 > t et S n ≤ t, ⇔ t ∈ [S n , S n+1 [.

Donc,

P ( N ( t) = n) = P (S n+1 > t et S n ≤ t)

= P (S n+1 > tS n ≤ t) P (S n ≤ t)

= [1 − P (S n+1 ≤ tS n ≤ t)] P (S n ≤ t)

= P (S n ≤ t) − P (S n+1 ≤ tS n ≤ t) P (S n ≤ t) = P (S n ≤ t) − P (S n+1 ≤ t et S n ≤ t) = P (S n ≤ t) − P (S n+1 ≤ t)

puisque S n+1 ≤ t implique S n ≤ t, cette relation est valable pour tout processus de comptage. U.M.B.B

B. ISSAADI

1.4 Définition et propriété principale

1.4 1.4.1

3

Définition et propriété principale Définition On dit qu’un processus de comptage { N ( t), t ≥ 0} est un processus de Poisson s’il satisfait aux trois conditions suivantes :

c 1 − Le processus N ( t) est homogène dans le temps, ceci veut dire que la probabilité d’avoir k événements dans un intervalle de longueur donnée t ne dépend que de t et non pas de la position de l’intervalle par rapport à l’axe temporel.

IS SA AD I

En d’autres termes,

P ( N ( s + t) − N ( s) = k) = P ( N ( t) = k) = p k ( t),

pour tout s > 0, t > 0 et k = 0, 1, 2, . . .

c 2 − Le processus N ( t) est à accroissement indépendants ce qui signifie que pour tout systèmes d’intervalles disjoints, les nombres d’événements s’y produisant sont des variables aléatoires indépendantes. En particulier,

P ( N ( s + t) − N ( s) = k, N ( s) = j ) = P ( N ( s + t) − N ( s) = k) P ( N ( s) = j ) = P ( N ( t) = k ) P ( N ( s) = j )

e

= p k ( t) p j ( t),

ed in

pour tout s > 0, t > 0.

c 3 − La probabilité que deux événements ou plus se produisent dans un petit

Ba dr

intervalle ∆ t est négligeable par rapport à la probabilité qu’il n’y ait qu’un seul événement. En termes plus précis :   O (∆ t )    p k (∆ t) = λ∆ t + O (∆ t)    1 − λ∆ t + O (∆ t)

k ≥ 2, k = 1,

k = 0.

Le coefficient λ est appelé densité ou intensité du processus Poissonien. La condition c 3 exclut la possibilité d’une réalisation simultanée de deux événements ou plus.

1.4.2

Propriété principale

Nous donnons ci-après le résultat principal de ce chapitre qui explique bien le

nom donné au processus Poissonien. Théorème 1.4.1 Si un processus de comptage { N ( t), t ≥ 0} satisfait aux conditions

c 1 , c 2 et c 3 formulées dans le paragraphe 1.4.1, alors : p k ( t) = P ( N ( t) = k ) =

U.M.B.B

(λ t)k −λ t e , t > 0 et k = 0, 1, 2, . . . k!

B. ISSAADI

1.4 Définition et propriété principale

4

Par conséquent

E ( N ( t)) = λ t et V ( N ( t)) = λ t. Démonstration. D’après le théorème des probabilités totales et en tenant compte des conditions c 2 et c 3 on a pour n = 1, 2, . . .

p n ( t + ∆ t) = P ( N ( t + ∆ t) = n) n X = P ( N ( t) = n − i, N (∆ t) = i )

IS SA AD I

i =0 n X

=

P ( N ( t) = n − i ) P ( N (∆ t) = i )

i =0

= p n ( t) p 0 (∆ t) + p n−1 ( t) p 1 (∆ t) +

n X

p n− i ( t) p i (∆ t)

i =2

= p n ( t) (1 − λ∆ t) + p n−1 ( t) λ∆ t + O (∆ t)

Ce qui implique

O (∆ t) ∆t = λ( p n−1 ( t) − p n ( t)) + O (∆ t)

Lorsque ∆ t tend vers zéro, on obtient :

e

= −λ p n ( t) + λ p n−1 ( t) +

ed in

p n ( t + ∆ t) − p n ( t) ∆t

Ba dr

p0n ( t) = λ( p n−1 ( t) − p n ( t)).

De la même façon, nous avons :

p 0 ( t + ∆ t) = P ( N ( t + ∆ t) = 0)

= P ( N ( t) = 0, N (∆ t) = 0)

= P ( N ( t) = 0) P ( N (∆ t) = 0)

= p 0 ( t) p 0 (∆ t) = p 0 ( t)(1 − λ∆ t + O (∆ t))

Puis,

p 0 ( t + ∆ t) − p 0 ( t) = −λ p 0 ( t) + O (∆ t) ∆t

Lorsque ∆ t → 0,

p00 ( t) = −λ p 0 ( t). Donc,   p0 ( t) = λ( p n−1 ( t) − p n ( t)) n  p0 ( t) = −λ p ( t) 0

0

si n ≥ 1, sinon.

Ce système d’équations différentielles connus sous le nom d’équations de ChapmanKolmogorov, il peut être résolu soit par récurrence, soit en employant les fonctions U.M.B.B

B. ISSAADI

1.4 Définition et propriété principale

5

génératrices. Utilisons la récurrence, avec les conditions initiales p 0 (0) = 1 et p i (0) = 0, i ≥ 1. Pour p00 ( t) = −λ p 0 ( t) la solution est donnée par p 0 ( t) = K e−λ t , avec p 0 (0) = 1 on trouve k = 1, d’où

p 0 ( t) = e−λ t . Pour p01 ( t) = λ( p 0 ( t) − p 1 ( t)), la solution est donnée par p 1 ( t) = (λ t + C ) e−λ t , avec

p 1 (0) = 0 on trouve C = 0, d’où

IS SA AD I

p 1 ( t) = λ te−λ t . Pour p02 ( t) = λ( p 1 ( t) − p 2 ( t)), la solution est donnée par p 2 ( t) =

¡ (λ t)2 2

¢ + C e−λ t , avec

p 2 (0) = 0 on trouve C = 0, d’où

p 1 ( t) =

(λ t)2 −λ t e . 2

p j ( t) =

(λ t) j −λ t e , j!

Supposons que ∀ j ≥ 2, on a

et montrons que cette relation reste valable pour ( j + 1), on doit alors résoudre

Alors ∀ n ≥ 0 :

p n ( t) =

U.M.B.B

(λ t) j+1 −λ t e . ( j + 1)!

Ba dr

p j+1 ( t) =

ed in

e

p0j+1 ( t) = λ( p j ( t) − p j+1 ( t)), la solution de cette dernière est donnée par p j+1 ( t) = ¡ (λ t) j+1 ¢ −λ t e , avec p j+1 (0) = 0 on trouve C = 0, d’où + C ( j +1)!

(λ t)n −λ t e . ( n)!

■

B. ISSAADI

1.5 Processus de Poisson et loi exponentielle Graphe des transitions 1                      

 ∆  

1

 ∆  

1

1

 

1 

∆  

∆  

IS SA AD I

                      ou bien,

1

 

1 

 

  

Processus de Poisson et loi exponentielle la ( n − 1) − ième et le n − ième événement.

e

Soit { N ( t), t ≥ 0} un processus de Poisson de paramètre λ, et T n la durée séparant

Théorème 1.5.1 Les temps d’attente T n d’un processus de Poisson de paramètre λ

sont des variables aléatoires indépendantes et distribuées identiquement selon

Ba dr

1.5

∆  

ed in

1.4.3

6

une loi exponentielle de paramètre λ.

Théorème 1.5.2 Un processus de comptage { N ( t), t ≥ 0} est un processus de Pois-

son de paramètre λ si les intervalles de temps entre deux événements consécutifs sont des variables aléatoires indépendantes obéissant à la même loi exponentielle de paramètre λ.

Démonstration. Soit T1 , T2 , . . ., T n des variables aléatoires indépendantes obéissant à la même loi exponentielle de paramètre λ, leur somme S n = T1 + T2 + . . . + T n est alors distribuée suivant une loi gamme de paramètre λ et n qui est également connue sous le nom de loi d’Erlang d’ordre n, sa densité de probabilité est :

f n ( t) = λn t n−1 e−λ t /( n − 1)!, t ≥ 0. Pour déterminer la distribution de N ( t), constatons que :

P ( N ( t) = 0) = P (T1 > t) = e−λ t .

U.M.B.B

B. ISSAADI

1.6 Exemple

7

D’autre part,

P ( N ( t) = n) = P (S n ≤ t) − P (S n+1 ≤ t), n = 1, 2, . . . Et par conséquent, Z

P ( N ( t) = n) =

= =

=

■

e

Exemple

ed in

Admettons que la durée de vie d’un dispositif technique est exponentielle de

paramètre λ = 1 h−1 . Dès qu’un dispositif tombe en panne, il est immédiatement remplacé par un élément identique.

Ba dr

1.6

( f n ( u) − f n+1 ( u)) du ¶ Z t µ n n−1 λn+1 u n −λu λ u −λ u e − e du n! 0 ( n − 1)! Z ¢ λn t ¡ n−1 nu − λ u n e−λu du n! 0 λn h n −λu i t du u e 0 n! (λ t)n −λ t e n! 0

IS SA AD I

=

t

1. Quelle est la probabilité d’avoir plus de 3 pannes dans un intervalle d’une durée de 2 h ?

2. Quelle est la distribution de l’instant d’occurrence de la première panne sachant que le deuxième dispositif fonctionne encore à l’instant t = 3 h ?

Solution :

1) D’après le théorème 1.5.2 le nombre de pannes N ( t) se produisant dans un intervalle de temps [0, t], suit une loi Poissonienne de paramètre λ, d’où :

P ( N (2) > 3) = 1 − P ( N (2) ≤ 3)

= 1 − P ( N (2) = 0) − P ( N (2) = 1) − P ( N (2) = 2) − P ( N (2) = 3) = 1 − p 0 (2) − p 1 (2) − p 2 (2) − p 3 (2) 4 = 1 − e−2 − 2 e−2 − 2 e−2 − e−2 3 19 −2 = 1− e 3 = 0, 14287

2)

P (T1 < t N (3) = 1) = U.M.B.B

P (T1 < t, N (3) = 1) P ( N (3) = 1) B. ISSAADI

1.6 Exemple

8

T1 est l’instant de la première occurrence. P (T1 < t N (3) = 1) = = =

IS SA AD I

=

P ( N ( t) = 1, N (3) = 1) P ( N (3) = 1) P ( N ( t) = 1, N (3) − N ( t) = 0) P ( N (3) = 1) P ( N ( t) = 1, N (3) − N ( t) = 0) P ( N (3) = 1) P ( N ( t) = 1) P ( N (3) − N ( t) = 0) P ( N (3) = 1) −t ( te ) ((3 − t)0 e−(3− t) /0!) 3 e−3 − t −(3− t) te e 3 e−3 t 3

= =

=

où, 0 ≤ t ≤ 3.

Ba dr

ed in

e

T1 est donc uniformément répartie dans [0, 3].

U.M.B.B

B. ISSAADI

2.1.1

Processus de naissance et de mort Introduction

L

ÉTUDE

Ba dr

2.1

ed in

e

IS SA AD I

2. Phénomènes d’attente processus de naissance et de mort

mathématique d’un système se fait le plus souvent par l’introduction

d’un processus stochastique défini de façon appropriée. En premier lieu, on

s’intéresse ici au nombre X ( t) de clients se trouvant dans le système à l’instant t ( t ≥ 0).

Les processus de naissance et de mort interviennent non seulement lors de la

modélisation de systèmes d’attente, mais encore ils permettent de façon générale de décrire l’évolution temporelle de la taille d’une population d’un type donné. De tels phénomènes sont naturellement étudiés en biologie, en démographie et en sociologie, mais on les rencontre aussi en physique et dans des domaines techniques.

2.1.2

Définition Soit un processus stochastique { X ( t), t ≥ 0} à temps continu, à états discret

n = 0, 1, 2, . . . et homogène dans le temps, c’est à dire tel que : p i j ( t) = P ( X ( t + s) = j  X ( s) = i )

U.M.B.B

B. ISSAADI

2.1 Processus de naissance et de mort

10

ne dépend pas de s. Alors { X ( t), t ≥ 0} est un processus de naissance et de mort s’il satisfait les postulats suivants :

p i,i+1 (∆ t) = λ i ∆ t + O (∆ t)

( i ≥ 0)

p i,i−1 (∆ t) = µ i ∆ t + O (∆ t)

( i ≥ 1)

p i,i (∆ t) = 1 − (λ i + µ i )∆ t + O (∆ t) p 0,0 (∆ t) = 1 − λ0 ∆ t + O (∆ t)

( i ≥ 1)

( i = 0)

IS SA AD I

Les coefficients non négatifs, λ i et µ i sont appelés taux de transition, plus particulièrement, on parle de taux de naissance (ou de croissance) et de taux de mort (ou de décroissance).

De cette définition, on déduit que :

p i, j (∆ t) = O (∆) si | i − j | ≥ 2.

e

Régime transitoire

Les probabilités p n ( t) = P ( X ( t) = n) définissent le régime transitoire du processus

ed in

2.1.3.1

Régime transitoire et régime stationnaire

{ X ( t), t ≥ 0}. Pour calculer les probabilités d’état p n ( t) = P ( X ( t) = n) nous devons

écrire, d’après le théorème des probabilités totales et pour n ≥ 1 :

Ba dr

2.1.3

p n ( t + ∆ t) = P ( X ( t + ∆ t) = n) ∞ X = P ( X ( t) = i, X ( t + ∆ t) = n) =

i =0 ∞ X

p i ( t) p in (∆ t)

i =0

= p n ( t) p nn (∆ t) + p n−1 ( t) p n−1,n (∆ t) + p n+1 ( t) p n+1,n (∆ t) ∞ X + p i ( t) p in (∆ t) i 6= n,n−1,n+1

= p n ( t) (1 − (λn + µn )∆ t + O (∆ t)) + p n−1 ( t) (λn−1 ∆ t + O (∆ t)) + p n+1 ( t) (µn+1 ∆ t + O (∆ t)) + O (∆ t)

= p n ( t) − p n ( t) (λn + µn )∆ t + p n−1 ( t) λn−1 ∆ t + p n+1 ( t) µn+1 ∆ t + O (∆ t)

D’où

p n ( t + ∆ t) − p n ( t) O (∆ t ) = − p n ( t) (λn + µn ) + p n−1 ( t) λn−1 + p n+1 ( t) µn+1 + ∆t ∆t En faisant tendre ∆ t → 0 (vers 0), on trouve

p0n ( t) = −(λn + µn ) p n ( t) + λn−1 p n−1 ( t) + µn+1 p n+1 ( t). U.M.B.B

B. ISSAADI

2.1 Processus de naissance et de mort

11

De la même façon :

p 0 ( t + ∆ t) =

∞ X

p i ( t) p i0 (∆ t)

i =0

= p 0 ( t) p 00 (∆ t) + p 1 ( t) p 10 (∆ t) +

X

p i ( t) p i0 (∆ t)

i >1

= p 0 ( t) (1 − λ0 ∆ t) + p 1 ( t) µ1 ∆ t + O (∆ t) = p 0 ( t) − p 0 ( t)λ0 ∆ t + p 1 ( t)µ1 ∆ t + O (∆ t)

Par conséquent,

IS SA AD I

p 0 ( t + ∆ t) − p 0 ( t) O (∆ t ) = −λ0 p 0 ( t) + µ1 p 1 ( t) + ∆t ∆t

Lorsque ∆ t → 0,

p00 ( t) = −λ0 p 0 ( t) + µ1 p 1 ( t).

Ces équations sont connues sous le nom d’équations différentielles de Kolmogorov ; elles permettent de calculer les probabilités d’état p n ( t) si l’on connait les conditions initiales du processus X (0). On peut ainsi déterminer le régime transitoire du processus stochastique { X ( t), t ≥ 0}. Cependant, la résolution analytique des équations de Kolmogorov se montre généralement très complexe, voire impossible, on ne considère

ed in

Régime stationnaire

Le régime stationnaire du processus stochastique, défini par : πn = lim p n ( t) = P ( X (+∞) = n), n = 0, 1, 2, . . .

Ba dr

2.1.3.2

e

donc généralement que la distribution stationnaire.

t→∞

Ces limites existent et sont indépendantes de l’état initial du processus, et lim p0n ( t) = 0, n = 0, 1, 2, . . .

t→∞

A la place d’un système d’équations différentielles, on obtient alors un système d’équations linéaires :  λ0 π0 = µ1 π1 ( λ + µ ) π = µ n

n

n

si ( n = 0),

n+1 π n+1 + λ n−1 π n−1

si ( n ≥ 1).

appelées équations de balance.

Additionnons les ( n + 1) premières équations, c.-à-d. : λ0 π0 = µ1 π1

(λ1 + µ1 )π1 = µ2 π2 + λ0 π0 (λ2 + µ2 )π2 = µ3 π3 + λ1 π1 .. . (λn + µn )πn = µn+1 πn+1 + λn−1 πn−1

U.M.B.B

B. ISSAADI

2.1 Processus de naissance et de mort

12

Nous trouvons, λn πn = µn+1 πn+1

Donc, πn+1 =

λn µn+1

( n ≥ 0)

πn ,

en d’autre termes : λn−1 µn λn−2

πn−1

IS SA AD I

πn = πn−1 =

.. .

π1 =

µn−1

λ0 µ1

πn−2

π0

donc,

Ajoutons la condition :

λn−1

¶µ

µn

∞ X

λn−2 µn−1

¶

µ

···

λ0 µ1

¶

π0 =

πn = 1, alors

λ0 λ1 · · · λn−1 µ1 µ2 · · · µ n

¶

π0 .

ed in

n=0

µ

e

πn =

µ

∞ λ λ ···λ X 0 1 n−1 π0 = 1 µ µ · · · µ 1 2 n n=1 Ã ! ∞ λ λ ···λ X 0 1 n−1 π0 1 + = 1 µ µ · · · µ 1 2 n n=1

Ba dr

π0 +

d’où :

"

π0 =

U.M.B.B

∞ λ λ ···λ X 0 1 n−1 1+ n=1 µ1 µ2 · · · µ n

#−1

.

B. ISSAADI

2.1 Processus de naissance et de mort 2.1.4

13

Graphes des transitions

1

Δ  

1

 

Δ  

Δ  

1

Δ

Δ  

  0 

1

  2 

Δ  

Δ

Δ

  1 

Δ   n+1 

Δ

Δ

Δ  

Δ   n 

···

Δ  

1

Δ

Δ

··· Δ  

ou bien,   ߤଵ  

ߤଶ  

ߤ௡ାଵ

IS SA AD I   0 

  1 

  2 

ߣ଴  

  n 

···

ߣଵ  

ߣ௡ିଵ

ߣଶ

ߣ௡

ߤ௡ାଶ   n+1 

··· ߣ௡ାଵ  

Exemple

Dans un cabinet médical, l’arrivée des patients peut être décrite par un processus

poissonnien de paramètre λ = 4 h−1 . La durée de traitement suit une loi exponentielle de moyenne 12 min. Si l’on admet de plus que la salle d’attente ne contient qu’une

e

seule place, quelle est la probabilité qu’une personne qui arrive puisse être traitée ?

ed in

Solution :

Le nombre de patients se trouvant dans le cabinet forme un processus de naissance et de mort dont on veut connaitre le régime stationnaire, on a :   λ i = 0 , ∀ i ≥ 2 λ0 = λ1 = λ = 4 et µ = µ = µ = 5 µ = 0 , ∀ i ≥ 3 1

Ba dr

2.1.5

ߤ௡

ߤଷ

2

le graphe des transitions est donné :   1 5Δ   1 4Δ     0 

i

9Δ

5Δ  

  1 

4Δ  

1

5Δ

  2 

4Δ  

µπ1 = λπ0

λπ0 + µπ2 = (λ + µ)π1 λπ1 = µπ2

on tire alors : π1 =

avec :

λ µ

π0

µ ¶2 λ et π2 = π0 , µ

³ λ ´ ³ λ ´2 ¶−1 + . π0 = 1 + µ µ µ

U.M.B.B

B. ISSAADI

2.2 Phénomènes d’attente

14

Numériquement, on obtient : π0 = 0.41, π1 = 0.33 et π2 = 0.26. La probabilité qu’un client qui arrive soit traité vaut donc : π0 + π1 = 0.74. vn+1 servis

2.2 2.2.1

  d’attente Phénomènes

…

Introduction  

IS SA AD I

Serveur comprend un espace de service avec une ou plusieurs Un système  d’attente stations de service montées en parallèle, et un espace d’attente dans lequel se   forme une éventuelle file d’attente. Des phénomènes d’attente se manifestent sous Temps

des formes multiples dont voici     quelques exemples :

d’attente – L’arrivée deFile voitures vers une station-service ;   – Vente de billets auprès d’un guichet ;   de machines   – Réparation défectueuses par un ; qn+1mécanicien clients qn clients

• 

• 

– Atterrissage des avions Cn sur un aéroport ; Cn+1   .. .   Un système d’attente peut être représente, dans le cas d’un seul serveur comme suit :

 

 

 

 

 

 

 

e

  File d’attente

 

Serveur

ed in

 

 

 

Ba dr

  Dans le cas de plusieurs serveurs, il est représenté comme suit :  

   

2.2.2

Discipline du service

La discipline de la file d’attente concerne l’ordre de traitement des clients. Les

principales disciplines de service utilisées sont :

– FIFO (First In First Out) : premier entré, premier servi. C’est la règle la plus communément utilisée dans les entreprises de services ; elle procure aux clients un sentiment de justice, bien qu’elle pénalise les clients dont le temps de service est court. Elle est appliquée dans les banques, les magasins, les cinémas, les restaurants, etc ; – LIFO (Last In First Out) : le dernier arrivé sera le premier servi. Cette discipline est généralement très utilisée dans les stocks non périssables ;

U.M.B.B

B. ISSAADI

2.2 Phénomènes d’attente

15

– FIRO (First In Random Out) : les clients sont servis de manière aléatoire. Cette discipline est généralement utilisée dans les serveurs informatiques ; – La discipline avec priorité : il y a plusieurs classes de clients, chaque classe possède un niveau de priorité. C’est le client qui a la plus haute priorité qui est servi le premier. – PS (Processes Sharing) : Processus Partagé, c’est le cas de la distribution ROUND-ROBIN lorsque le quantum Q tend vers 0. Tous les clients sont servis en même temps avec une vitesse inversement proportionnelle au nombre de

IS SA AD I

clients simultanément présents ;

– ROUND-ROBIN (cyclique) : tous les clients du système entrent en service à tour de rôle, effectuant Q (Quantité déterminée) de leurs temps de service et sont remplacés dans la file, jusqu’à ce que leurs service soit totalement accompli ; .. .

Classification des systèmes d’attente

– La distribution du temps de service ;

ed in

– La distribution des inter-arrivées ;

e

Pour identifier un système d’attente, on a besoin des spécifications suivantes :

– Le nombre S de stations de service qui sont montées en parallèle ;

Ba dr

2.2.3

– La capacité K du système. Si K < ∞, la file d’attente ne peut dépasser une longueur de K − S unités.

Pour la classification des systèmes d’attente, on utilise généralement la notation de KENDALL A /B/S /(K / N / Z ) où :

• A : distribution des temps entre deux arrivées successives ; • B : distribution des durées de services ;

• S : nombre de postes de service en parallèle ;

• K : capacité du système (nombre de serveurs + longueur maximale de la file) ; • N : population des usagés ; • Z : discipline du service.

Dans le cas où les valeurs K , N et Z ne sont pas données, alors on les prend par défaut à ∞, ∞, FIFO.

Pour spécifier les distributions A et B, on introduit les symboles suivants : • M : distribution exponentielle (qui vérifie donc la propriété de Markov) ; • E k : distribution d’Erlang d’ordre k ; • G : distribution générale ; • D : cas déterministe.

U.M.B.B

B. ISSAADI

2.2 Phénomènes d’attente Exemple

La notation M /D /1/4 définit un système d’attente comprenant une station de service et pour lequel la capacité de l’espace d’attente vaut 4 − 1 = 3. Le processus d’arrivée est poissonnien et la durée de service constante.

Ba dr

ed in

e

IS SA AD I

2.2.4

16

U.M.B.B

B. ISSAADI