Estimation de l'erreur de trocature de l'espace d'états du système d'attente m/m1: méthode stabilité forte

2.3 Files d'attente non Markoviennes

L'étude des files non markoviennes est cependant beaucoup plus difficile que celles de la section précédente sur les systèmes de files d'attente Markoviennes, et nous nous limitons ici a` présenter les résultats disponibles dans les cas les plus simples.

2.3.1 Système de files d'attente M/G/1

Dans ce type de système, la durée des inter-arrivées est une variable aléatoire suivant une loi exponentielle de paramètre ë, et la durée de service est une variable aléatoire suivant une loi quelconque H, de moyenne 1/u. La propriétéde Markov du processus {X(t), t = 0} représentant »le nombre de clients dans le système a` l'instant t» facilitant l'analyse des systèmes de type M/M/1 n'est plus vérifiée pour le système M/G/1 qui rend son analyse plus délicate. Ainsi, plusieurs méthodes ont étéproposées dan la littérature [14] :

. Méthode des étapes d'Erlang;

. Méthode de la chaàýne de Markov induite;

. Méthode des variables auxiliaires;

. Méthode des événements fictifs;

. Méthodes d'approximation;

. Simulation.

Chaàýne de Markov induite

Considérons le processus X(t), le nombre de clients dans le système aux instants (t_n, m = 1, 2, ...) o`u t<sub>n</sub> est l'instant de départ du <sup>m`eme</sup> client.

On défini ainsi le processus stochastique a` temps discret {X<sub>n</sub> = X(t<sub>n</sub>), m = 0, 1, ...} représentant le nombre de clients dans le système juste après le départ du <sup>m`eme</sup> client. La variable aléatoire X_n est une chaàýne de Markov a` temps discret. Pour vérifier cela, considérons le nombre A_n de clients qui entrent dans le système pendant que le m^eme client est servi.

Les variables aléatoires A_n sont indépendantes entre elles, leur distribution commune est :

f e-ët(ët)k

P(A_n = k) = ak = k! dH(t),

Alors,

{ X_n - 1 + _An+1, X_n = 1;

Xn+1 = (2.7)

An+1, X_n = 0.

o`u

=

e^ë(Z-1)sdH(s).

0

_X

A(z) =

j=0

On remarque que _Xn+1 dépend que de X_n et de _An+1 et non pas des valeurs de Xn-1, Xn-2, ... Ce qui signifie que la suite {X_n, n = 0, 1, ...} ainsi définie est une chaine de Markov induite du processus {X(t), t = 0}.

R'egime transitoire

Les probabilités de transition de la chaine de Markov induite {X_n, n = 1, 2, ...}, sont données par :

Pij = P(Xn+1 = j/X_n = i),

? ?

?

P0j = P(Xn+1 = j/X0 = 0) = aj = p(An+1 = j), j = 0;

Pij = P(Xn+1 = j/Xn = i) = aj-i+1 = p(An+1 = j - i + 1), 1 = i = j + 1; (2.8)

Pij = 0, ailleurs.

D'o`u la matrice de transition :
a0 ?	a1	a2	a3	·	· ·	?		? a0
a1	a2	a3	·	· ·	?	? ? 0
a0	a	a2	·	· ·	? ?	P= ? ? 0
0	a0	a1	·	· ·	? ?
? ? 0	0	0	a0		...	? ?
... ?	...	...	...	.	..	?

Puisqu'on peut passer de chaque état vers n'importe quel autre état, alors ; il s'agit d'une chaine de Markov irréductible donc, on peut montrer qu'elle converge vers une distribution limite si ñ = ë/u < 1 .

R'egime stationnaire

Supposons que ñ < 1, la distribution stationnaire de la chaine de Markov (X_n, n = 1, 2, ..), o`u

ð = lim n?8

P(Xn = k).

Il ne sera généralement pas possible de trouver la distribution ð elle-même, mais nous pou-
vons calculer la fonction génératrice correspondante ð(z). Ceci, en utilisant la définition de
la distribution de probabilitédiscr`ete stationnaire par rapport a` une matrice stochastique

P : ðP = ð. On obtient :

( Z) ð0A(z)(z - 1) =

z - A(z) ,

est la transformée de Laplace de la densitéde probabilitédu temps de service, avec |z| < 1.
On remplace A(z) par la transformée de Laplace b(ë - ëz), on obtient la formule suivante :

.

ð(z) = (1 - ñ)b(ë - ëz)(1 - z)

b(ë - ëz) - z

Cette formule est connue sous le nom de la Pollaczek-Khinchine .

Caractéristiques du système d'attente M/G/l

- Nombre moyeu de clients dans le système (L) :

Cette quantitépeut être déterminée en régime stationnaire, en utilisant la relation :

E(X) = lim

z?1 ð'(z),

Ce calcul s'avère compliqué. Par contre, elle peut être obtenue aisément en utilisant la relation [9] :

{ 1, siX_n > 0;

ó_n = (2.9)

0, siX_n = 0.

Tel que,

Xn+1 = X_n + ó_n + An+1,

ó2 + ë²V ar(Y )

L = E(X_n) = ó + 2(1 - ó)

On obtient ainsi :

,

O`u Y est la durée de service et V ar(Y ) = óY 2 est la variance de service. - Le temps moyen de séjour d'un client dans la file W :

L 1 ë[óY2+ u2 1 ]

W = ë W = + 2(1 - ñ) ,

u

- Le temps moyen de d'attente d'un client dans le système W_q :

1 Wq = W - u	=	ë[óY 2+ u2 1]
		2(1 - ñ) ,

- Nombre moyeu de clients dans la file L_q :

ë ë²[(óY 2+_ñ2)²]

L = L_q + L_q = L - ñ = 2(1 - ñ) . u

2.3.2 Système de files d'attente G/ M/ l

Le système G/M/l peut être considérécomme symétrique du système M/G/1. En effet, les temps des inter-arrivées des clients suivent une loi générale F, de moyenne 1/A et le temps de service est une variable aléatoire suivant une loi exponentielle de paramètre u. Afin d'analyser ce système, on fait appel a` la méthode de la chaàýne Markov induite.

Chaàýne Markov induite

Soit Y_n : le nombre de clients se trouvant dans le système G/M/1 juste avant l'arrivée du n^eme client . La variable aléatoire Y_n est une chaàýne de Markov a` temps discret.

Pour vérifier ce résultat, considérons le nombre B_n de clients servis entre les instants d'arrivées consécutives _{(Tn_1,} T_n), les variables aléatoires B_n sont indépendantes entre elles, leur distribution commune est [14] :

P(Dn = k) = Bk = On a alors la relation suivante :

Z0

+00e_ut (mut)k k! dF(t).

Y_n = Tn_1 - D_n + 1,

D_n est une variable aléatoire qui ne dépend que de la durée (T_n - Tn_1).

D'autre part (T_n - Tn_1) est une variable aléatoire indépendante de _{Yn_1} , de l'état du processus avant _{Tn_1} ainsi que de n. Et que T_n ne dépend que de _{Tn_1} et non pas de Tn_2, Tn_3,....

La suite {Y_n : n = 0, 1, ...} forme une chaàýne de Markov induite du processus {Y (t), t = 0} o`u y(t) : le nombre de clients dans le système a` l'instant »t».

Régime transitoire

Les probabilités de transition de la chaàýne de Markov induite {Y_n : n = 0, 1, ...}, sont données par:

qij = P(yn+1 = j/y_n = i) = P(D_n = k),

j.

~P(Dn = i - j + 1), si X_n > 0; 0, si i + 1 < qij = (2.10)

Pi0 = 1 -			Xi+ 1 j=1	Pij.
Q =	? ? ? ? ? ? ? ? ? ? ? ? ? ?

?
? ? ? ? ? ? ? ? ? ? ? ? ?

Ainsi, la matrice des probabilites de transition Q = (qij)i,jinN prend la forme suivante :

1 -- B0 B0 0 0 0 ...

1

_P
j=0

1 --

Pij B1 B0 0 0 ...

2

_P
j=0

1 --

Pij B2 B1 B0 0 ...

3

_P
j=1

1 --

..

Pij B3 B2 B1 B0 .

.· · · · · · · · · · · · · · ·..

R'egime stationnaire

Supposons que le regime stationnaire existe (A/_au < 1).

Notons 7r = (7rn)n>0, le vecteur de probabilitestationnaire de la chaine de Markov induite

(Yn).

On a, 7r = 7rP,

7ri =

?

?? ?

???

+00

k=0

7r0 =

7ri+k-1Bk, si i = 1;

+00

t=0

[7re(1 --

+00

t=0

Bk)].

(2.11)

On utilise la fonction generatrice de la variable aleatoire D_n note par

B(z) =

+00 k=0

Bkz^k,

B(z) = z. (*)

Notons par rj(0 < rj < 1) la j^eme solution de l'equation (*), la solution pour 7ri est :

7ri = E cjrⁱ_j,

j

cj une constante.

En utilisent l'equation (*), z = B(z) et 7ri = Crⁱ ₀, i = 1, on verifie ; 7r0 = 1 -- r0.

D'ou,

7ri = (1 -- r0)rⁱ ₀, n > 0.

Caractéristiques du système d'attente G/M/l

ð_n = P_n, n'est pas vérifiée ici parceque les arrivées sont générales avec

Pn = lim t--++8

P(X(t) = n).

Les mesures de performance juste aux instants d'arrivées, et P_n = ñðn-1. On constate que toutes les caractéristiques stationnaires du système M/M/1 peuvent être déduite a` partir des caractéristique stationnaire de la chaàýne de Markov induite (bien que ð_n =6 P_n).

Les mesures de performance sont donc données comme suit :
- Temps moyen d'attente d'un client dans le système W_q :

r0

W_q = u(1 -- r0)^,

- Temps moyen de séjour d'un client dans le système W :

1 W = Wq + u		1
	=
		u(1 -- r0)^,

- Nombre moyen de clients dans le système L :

ë

L = u(1 -- r0)^,

Nombre moyen de clients dans la file L_q :

1 Lq = u	=	ër0
		u(1 -- r0)^.