3.3 Exemple de la troncature sur un réseau de
files d'attente en tandem avec blockage
Dans la pratique, l'espace d'états rencontréest
souvent grand ou infini, c'est le cas par exemple d'une file d'attente a`
capacitéd'attente infinie. Lors d'évaluation des performances de
tels systèmes et pour des raisons de la complexitédu calcul, on
rencontre alors des problèmes liés a` leur dimension. Alors, la
troncature de l'espace d'états devient a` ce niveau nécessaire.
Dans cette section, nous présentons un exemple illustratif de la
troncature d'espace d'états d'un réseau de files d'attente en
tandem avec blockage.
Considérons un réseau de files d'attente en tandem
constituéde deux files : la première est la file M/M/1/8 et la
seconde est la file M/M/1/N. Supposons que lorsque la deuxième
file est saturée, alors le premier serveur sera
bloqué. Chaque station contient un seul serveur et la discipline de
service est FIFO (le premier arrivépremier servi).
Les durées de temps de service des deux serveurs suivent
des lois exponentielles de pa-
rametres /t1 et /t2 respectivement.
Les temps d'inter-arrivées dans le réseau sont
également exponentielles de parametre ë(i) qui dépend de
nombre de clients présents dans la premiere file.
La distribution stationnaire conjointe de la taille de ce
réseau en tandem avec blockage (nombre total de clients présents
dans le réseau) n'existe pas sous forme explicite (voir par exemple
Hordijk [24] et Van Dijk [48]).
Ainsi, plusieurs auteurs ont proposédifférentes
approches d'approximation de celle-ci. Entre autres, on peut citer les
approximations numériques : Boxma et Konheim [8], Hillier et Boling [22]
et Latouche et Neuts [32], les approximation par bornes de perturbation : Van
Dijk [48]. Ce dernier auteur a considéréun cas de troncature de
l'espace d'états de la chaàýne de Markov décrivant
l'état de ce réseau de files d'attente, et cela tout en limitant
la capacitéd'attente de la premiere file a` Q buffers.
Dans ce cas, l'auteur [48] a démontréque sous
certaines hypotheses supplémentaires que la distribution stationnaire de
la taille de ce réseau peut-être exhibée sous forme
explicite.
|
A4 =
|
?
???
|
á11 á12 á13 á14 á21
á22 á23 á24 á31 á32 á33 á34
á41 á42 á43 á44
|
?
???
|
,
|
3.4 Exemple illustratif sur les techniques de
troncature par l'augmentation linéaire
Soit P = (P(i,j))i,j>1, une matrice stochastique infinie,
irréductible et récurrente positive. Elle admet donc une
distribution stationnaire unique ðn = (ðn(j))j>1.
?
? ? ? ? ? ?
P=
.
?
??????
p11 p12 p13 p14 . . . p21 p22 p23 p24 . . . p31 p32 p33 p34 .
. . p41 p42 p43 p44 . . . ... ... ... ... ...
Exemple pour m = 4
Considérons » le Coin Nord-Ouest» d'ordre 4 de
la matrice P qui est donnée par:
T4 = (P(i,j))4>i,j>1.
?
???
T4 =
,
?
???
p11 p12 p13 p14 p21 p22 p23 p24 p31 p32 p33 p34 p41 p42 p43
p44
P étant irréductible, il existe au moins une ligne
i pour laquelle 4 j=1 pij < 1, alors la matrice tronquée T4 n'est pas
stochastique.
Afin de rendre la matrice T4 stochastique, on construit une
nouvelle matrice stochastique (P4(i, j))4>i,j>1
vérifiant P4 = T4 c'est a` dire P4(i, j) > P(i, j) pour 1 i, j 4.
Cela peut se faire de plusieurs facons. La masse de
probabilités perdue lors de la troncature de
P est redistribuésur les colonnes de T4.
Soit A4 une matrice stochastique quelconque,
A4 = (á4(i,j))1<i,j<4,
4
|
telle que
|
P
j=1
|
áij = 1, i.e.
|
á11 + á12 + á13 + á14 = 1;
á21 + á22 + á23 + á24 = 1; á31 +
á32 + á33 + á34 = 1; á41 + á42 +
á43 + á44 = 1.
L'estimation de la masse perdue dans chaque ligne est obtenue par
Ek>4 P(i, k). Pour notre exemple :
X Xp1k = (á11 + á12 + á13 +
á14) p1k,
k>4 k>4
Donc,
P p1k = á11 E p1k + á12 E p1k +
á13 E p1k + á14 E p1k. k>4 k>4 k>4 k>4 k>4
P p2k = á21 E p2k + á22 E p2k +
á23 E p2k + á24 E p2k. k>4 k>4 k>4 k>4 k>4
P p3k = á31 E p3k + á32 E p3k +
á33 E p3k + á34 E p3k. k>4 k>4 k>4 k>4 k>4
|
P
k>4
|
p4k = á41 E
k>4
|
p4k + á42 E
k>4
|
p4k + á43 E
k>4
|
p4k + á44 E
k>4
|
p4k.
|
On construit notre nouvelle matrice et pour cela on pose pour 1
< i, j < 4,
P4(i,j) = P(i,j) + á4(i,j)E pik.
k>4
|
Posons s(i,k) = E
k>4
|
pik, et P4 s'écrit :
|
?
???
P4 =
|
p11 + á11s(1,k) p12 + á12s(1,k) p13 +
á13s(1,k) p14 + á14s(1,k) p21 + á21s(2,k) p22 +
á22s(2,k) p23 + á23s(2,k) p24 + á24s(2,k) p31 +
á31s(3,k) p32 + á32s(3,k) p33 + á33s(3,k) p34 +
á34s(3,k) p41 + á41s(4,k) p42 + á42s(4,k) p43 +
á43s(4,k) p44 + á44s(4,k)
|
?
? ? .
?
|
|
Xp11 + p12 + p13 + p14 + (á11 + á12 + á13 +
á14)
k>4
|
p1k = p11 + p12 + p13 + p14
+E
k>4
|
p1k,
|
o`u, (á11 + á12 + á13 + á14) = 1.
En particulier, on obtient A4 par les techniques d'augmentation
linéaire qu'on a déjàcite dans la section
(3.2), et on commence par :
* L'augmentation de la première colonne(voirles travaux de
Kalashnikov et Rachev [27]).
Si et seulement si á4(i, 1) = 1 pour 1 < i < 4;
Alors A4, s'écrit sous la forme :
,
|
?
|
1
|
0
|
0
|
0
|
?
|
|
1
|
0
|
0
|
0
|
|
|
A4 = ???
|
1
|
0
|
0
|
0
|
???
|
|
1
|
0
|
0
|
0
|
|
et la matrice p4 est donnée comme suit :
|
P4 =
|
?
???????
|
p11 + P
k>4
p21 + P
k>4
p31 +
P
k>4
p41 + P
k>4
|
p1k p12 p13 p14 p2k p22 p23 p24 p3k p32 p33 p34 p4k p42 p43
p44
|
?
???????
|
.
|
* L'augmentation de la dernière colonne [51], si et
seulement si á4(i, 4) = 1 pour 1 < i < 4 ;
Alors,
,
|
?
|
0
|
0
|
0
|
1
|
?
|
|
0
|
0
|
0
|
1
|
|
|
A4 = ???
|
0
|
0
|
0
|
1
|
???
|
|
0
|
0
|
0
|
1
|
|
|
et P4 sera donnée comme suit :
p11
?
p21
P4 =
???????
p31
p41
|
p12 p22 p32 p42
|
p13 p23 p33 p43
|
p14 + P p1k
k>4 ?
p24 + P p2k
k>4
.
???????
p34 + P p3k
k>4
p44 + P p4k
k>4
|
|
* L'augmentation uniforme : dans ce cas la matrice A4 est
construite de sorte que
|
|
toutes les composantes á4(i, j) = 1 4pour 1
|
i, j
|
4.
|
|
|
1/4 1/4
?
|
1/4
|
1/4
|
?
|
|
1/4 1/4
|
1/4
|
1/4
|
|
|
A4 = ??? 1/4 1/4
1/4 1/4
|
1/4
1/4
|
1/4
1/4
|
??? ,
|
et P4 sera donnée sous la forme:
?
???
P4 =
|
p11 + 1 4s(1,k) p12 + 1 4s(1,k) p13 + 1 4s(1,k) p14 + 14s(1,k)
p21 + 1 4s(2,k) p22 + 1 4s(2,k) p23 + 1 4s(2,k) p24 + 14s(2,k) p31 + 1 4s(3,k)
p32 + 1 4s(3,k) p33 + 1 4s(3,k) p34 +1 4s(3,k) p41 + 1 4s(4,k) p42 + 1 4s(4,k)
p43 + 1 4s(4,k) p44 + 1 4s(4,k)
|
?
? ? .
?
|
* On peut aussi considérer que A comme étant une
matrice dont toutes les lignes sont identiques, c'est un cas
considérépar Gibson et Seneta[11].
Dans ce cas;
|
A4 =
|
?
???
|
á11 á22 á33 á44 á11
á22 á33 á44 á11 á22 á33 á44
á11 á22 á33 á44
|
?
???
|
,
|
avec; á11 + á22 +
á33 + á44 = 1. et P4 est donnée comme suit :
?
???
P4 =
|
p11 + á11s(1,k) p12 + á22s(1,k) p13 +
á33s(1,k) p14 + á44s(1,k) p21 + á11s(2,k) p22 +
á22s(2,k) p23 + á33s(2,k) p24 + á44s(2,k) p31 +
á11s(3,k) p32 + á22s(3,k) p33 + á33s(3,k) p34 +
á44s(3,k) p41 + á11s(4,k) p42 + á22s(4,k) p43 +
á33s(4,k) p44 + á44s(4,k)
|
?
? ? .
?
|
D'o`u,
P4(i,j) = T4 + (I - T4)e4a, a = (a11, a22, a33, a44).
* Ou encore plus simplement, on peut choisir A booléenne,
comme Van Dijk [48] : Dans ce cas, si par exemple on prendre A comme une
matrice unitaire telle que :
.
|
?
A4 = ???
|
1 0 0 0
|
0 1 0 0
|
0 0 1 0
|
0 0 0 1
|
?
? ?
?
|
Alors,
?
???????
P4 =
p11 + P p1k p12 p13 p14
k>4
p21 p22 + P p2k p23 p24
k>4
p31 p32 p33 + P p3k p34
k>4
p44 + P
p41 p42 p43
k>4
* Renormalisation :
On pose s(i, 4) = /4 j=1 P(i, j), on choisit alors pour 1 i, j 4
:
P (i, j)
P4(i, j) = s(i,4) .
En prenant n assez grand afin que s(i, 4) > 0.
Exemple :
s(1,4) = p11 + p12 + p13 + p14, s(2,4) =
p21 + p22 + p23 + p24, s(3,4) = p31 + p32 +
p33 + p34, s(4, 4) = p41 + p42 + p43 + p44.
D'o`u
|
?
? ? ? ? ? ? ? ? ? ? ? ?
P4 =
|
p11
|
p12
|
p13
|
p14
|
?
.
? ? ? ? ? ? ? ? ? ? ? ?
|
|
s(1,4)
p21
|
s(1,4)
p22
|
s(1,4)
p23
|
s(1,4)
p24
|
|
s(2,4)
p31
|
s(2,4)
p32
|
s(2,4)
p33
|
s(2,4)
p34
|
|
s(3,4)
p41
|
s(3,4)
p42
|
s(3,4)
p43
|
s(3,4)
p44
|
|
s(4,4)
|
s(4,4)
|
s(4,4)
|
s(4,4)
|
|
|
