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

2.4 Conclusion

Nous avons abordédans ce chapitre, d'une manière générale et claire les notions de base de la théorie des files d'attente. Nous avons étudiéles systèmes de files d'attente Markoviens comme, M/M/1, M/M/m et M/M/1/N de la théorie des files d'attente élémentaire, et les systèmes de files d'attente non Markoviens : M/G/1 et G/M/1 de la théorie des files d'attente intermédiaire (la méthode de la chaàýne induite qui ramène l'étude du processus non Markovien a` celle d'une chaàýne de Markov a` temps discret).

3

Chaàýnes de Markov tronquées

3.1 Chaàýnes de Markov tronquées

Les chaàýnes de Markov constituent l'outil principal pour la mod'elisation et la r'esolution de problèmes dynamiques stochastiques. Dans ce chapitre, nous allons voir certains r'esultats consacr'es aux chaàýnes de Markov tronqu'ees.

Les chaàýnes de Markov sont connues, dans des situations d'applications pratiques qui se trouvent dans les t'el'ecommunications (r'eseaux de files d'attente, de radiodiffusion, de communication par satellite), l''evaluation de performance informatique (r'eseaux informatiques, programmation parallèle, stockage et retransmission en m'emoire tampon), la fabrication (lignes d'assemblage, systèmes de manutention), la fiabilit'e (analyse de panne), et la th'eorie d'inventaire, l'analyse de performances des systèmes informatiques.

Cependant, la mod'elisation des situations r'eelles, en simplifiant les hypothèses et les estimations en utilisant l'analyse de perturbations conduisant a` des erreurs introduites par ces inexactitudes. Nous allons pr'esenter quelques travaux sur le problème de troncature des chaàýnes de Markov.

3.1.1 Principe de troncature

En g'en'eral, le »principe de troncature» peut être 'enonc'e comme suit : »Pour r'esoudre un système infini d''equations lin'eaires a` un nombre infini d'inconnues, on limite le système aux n premières 'equations, et on n'eglige le reste des 'equations». Ce principe à'et'e introduit en 1913 par Riesz [40].

3.1.2 D'efinitions

Nous rappelons d'abord brièvement quelques d'efinitions essentielles des chaàýnes irr'eductibles a` valeurs dans un ensemble d'enombrable S. De nombreux r'esultats suppl'ementaires peuvent être trouv'es dans les ouvrages de Meyn et Tweedie [33] et de Nummelin [34] :

. Soient X et Y deux variables al'eatoires a` valeurs r'eelles de fonction de r'epartition F et G respectivement, X est dite stochastiquement inférieure a` Y, est on note X _st Y , si pour tout t on a :

. P = (p(i,j))i,j>1 est dite stochastiquement inférieure a` Q = (q(i,j))i,j>1, not'e P _st Q, ssi :

Vi = 1,Vm = 1, _Xm p(i,j) = _Xm q(i,j). (3.1)

j=1 j=1

. Q = (q(i, _j))i,j>1 est dite stochastiquement monotone ssi :

i j Vm _Xm q(i,k) = _Xm q(j,k). (3.2)

k=1 k=1

. On appelle »small set» une partie A de S, pour laquelle il existe un m > 0 et une mesure non triviale õ_m sur S tels que, pour tout i dans A et tout j dans S, on ait

p^(m)(i, j) = õ_m(j) (3.3)

Pour une chaàýne irr'eductible a` valeurs dans S, toute partie finie est un »small set»(i,e petite s'erie).

. Soit Z = (Z(k))k>0 une chaàýne irr'eductible et A une partie de S, le temps d'atteinte l'ensemble A est d'efini par :

ôA = inf{k = 1; Z(k) E A}, (3.4)

La chaine Z = (Z(k))k>0 est dite geometriquement recurrente s'il existe un »small set» B et un nombre r > 1, dependant eventuellement de B, tel que

sup

iEEi {r^ôB} < +8. (3.5)

. L'etat i est dit geometriquement recurrent s'il existe r > 1, dependant eventuellement de i, tel que :

Eir^ôi < +8, (3.6)

Si la chaine est geometriquement recurrente, tous les etats sont geometriquement recurrents.

i> La chaine Z = (Z(k))k>0 est dite uniformement recurrente s'il existe un »small set» B et un nombre r > 1, dependant eventuellement de B, tel que

sup Eir^ôB < +8. (3.7)

iEs

3.2 Diff'erentes techniques de la troncature des chaines de Markov

Soit P = (P(i, j))i, j = 1, une matrice stochastique infinie, irreductible et recurrente positive elle admet une distribution stationnaire unique ð_n = (ðn(j))j>1, le calcul de cette distribution etant en general difficile sinon impossible.Pour cela, une solution consiste a` approcher P par une matrice stochastique finie P_n.

»Le Coin Nord-Ouest» d'ordre n de la matrice P :

T_n = (P(i, j))n>i,j>1.

P etant irreductible, il existe au moins une ligne i pour laquelle

Xn j=1

P(i, j) < 1

alors la matrice tronquee T_n n'est pas stochastique.

A partir de T_n, on construit une matrice stochastique (Pn(i, j))n>i,j>1 verifiant P_n = Tn

c'est a` dire P_n(i, j) > P(i, j) pour 1 = i, j = n; cela peut se faire de plusieurs facons, citons les principales :

3.2.1 Augmentation linéaire

La masse de probabilitéperdue lors de la troncature de P est redistribuée sur les colonnes de P_n, plus précisément, soit

A_n = (án(i,j))1<i,j<n,

une matrice stochastique quelconque, on pose pour 1 = i, j = n,

X Pn(i,j) = P(i,j) + án(i, j) k>n En particulier, on obtient :

P(i, k).

- L'augmentation de la première colonne, travaux de Kalashnikov et Rachev [27], seulement si á_n(i, 1) = 1 pour 1 = i = n;

- L'augmentation de la dernière colonne [51], seulement si á_n(i, n) = 1 pour 1 = i = n ; - L'augmentation uniforme á_n(i,j) = n^-1 pour 1 = i,j = n .

- On peut aussi prendre pour A, une matrice dont toutes les lignes sont identiques,c'est un cas considérépar Gibson et Seneta [11].

- Encore plus simplement, on peut comme van Dijk [48], choisir A booléenne.

3.2.2 Renormalisation

On pose s(i, n) = _Pn P(i,j), on choisit alors pour 1 = i,j = n :

j=1

P (i, j) Pn(i, j) = s(i,n) . En prenant n assez grand afin que s(i, n) > 0. Notons que les deux conditions Pn stochastique et Pn = Tn, impliquent lim n-400

Pn(i,j) =

P(i, j). Par consequent si n est grand, P_n et P sont voisines, ce qui amène aux questions suivantes :

(Q1) P_n admet-elle une distribution stationnaire ð_n ? - (Q2) ð_n converge-t-elle, en un sens a` préciser vers ð ?

En ce qui concerne (Q1), l'existence d'une distribution stationnaire ð_n a ^{étéétudié}pour divers types de matrices P_n, en particulier par Seneta [41, 39]. Nous notons que si

l'état 1 est récurrent positif pour P_n, il existe au moins une distribution stationnaire ð_n. En effet, la chaàýne réduite a` la classe de l'état récurrent 1 admet une distribution stationnaire qu'on peut compléter par 0 sur les autres états.

De nombreux travaux ont étéconsacrés a` l'étude de (Q2), parmi les plus intéressants, citons :

(1) Wolf [50], qui s'est intéresséa` l'approximation de la distribution stationnaire d'une matrice infinie P, irréductible, récurrente positive, par ailleurs quelconque, par les distributions stationnaires de matrices finies P_n. Il a examinéquatre types de matrices P_n, obtenues par:

. Augmentation de la première colonne;

. Augmentation de la dernière colonne;

. Augmentation uniforme des colonnes;

. Renormalisation.

et établit la convergence en variation de ð_n vers ð, sous des conditions analogues au critère de Foster.

(2) Seneta [41] a prouvéque ð_n converge faiblement vers ð . Cette prouve a étérepris par Gibson et Seneta [11] pour établir la convergence faible de ð_n vers ð quand P est stochastiquement monotone et P_n construite par augmentation.

(3) Heyman [20] a construit des chaàýnes X_n et X de matrices de transitions respectives P_n et P et il a introduit les temps de retour en 1, C_n et C des chaàýnes X_n et X puis le temps nécessaire pour que la chaàýne X dépasse la barrière n; en s'appuyant sur les résultats de Heyman et Whitt [21], il établit une condition suffisante pour assurer la convergence faible de ð_n vers ð .

(4) Kalashnikov et Rachev [27] ont aussi étudiéle problème d'approximation d'une chaàýne de Markov infinie, l'essentiel de leurs travaux est orientévers l'approximation uniforme de la chaàýne initiale par des chaàýnes finies construites par augmentation de la première colonne.

(5) Tweedie [46] s'est intéressé, en particulier aux chaàýnes géométriquement ergodiques et les chaàýnes de Markov stochastiquement monotone, pour étudier les deux questions. Il a considéréP_n, »la matrice coin nord-ouest de troncature» de P. On connaàýt que les approximations de _ð(j)/ð(0) peut être construite a` partir de P_n, mais seulement dans des cas particuliers, sont celles connues de la convergence de la distribution de probabilitévers elle-même. Il a montre ainsi que cette convergence se produit toujours pour deux autres classes générales de chaàýnes de Markov : les chaàýnes géométriquement ergodiques, et celles dominées par les chaàýnes stochastiquement monotones. Dans les cas particuliers, de

manière uniforme, les chaàýnes ergodiques et les chaàýnes stochastiquement monotones, il a obtenu des estimations d'erreur d'approximation ||ð(n) - ð||.

(6) Zhao et Liu [51] ont prouvéque la la chaàýne de Markov censurée fournit la meilleure approximation dans le sens que, pour une taille de troncature donnée, la somme des erreurs est le minimum et ils ont montré, par exemple, que la méthode d'augmenter la dernière colonne n'est pas toujours la meilleure.

3.2.3 Distance entre les distributions stationnaires

Les résultats établis par Simonot [42] ne concernent que les distributions de probabilité»transitoires», en faisant tendre n vers l'infini nous obtiendrons un majorant de la distance entre les distributions limites. Une comparaison de ce résultat avec les résultats obtenus par d'autres auteurs a étéconsidérépar le même auteur. De même, Gibson et Seneta [11] ont traitéce problème, ils ont établi la convergence faible de ð_n vers ð sous les mêmes hypothèses sur ce qui concerne les matrices P, Q et P_n.

En outre, Heyman [20] considère la même question sous les hypothèses suivantes :

(A1) P est irréductible, récurrente positive et stochastiquement monotone;

(A2) P_n est une matrice stochastique vérifiant P_n(i, j) = P(i, j) pour 1 = i, j = n ;

(A3) L'état 1 est récurrent positif pour P_n ;

(A4) lim n-4+8

Pn(i,j) = P(i,j).

et en déduisant la convergence faible de ð_n vers ð.

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

? ???

,