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

République Algérienne Démocratique et Populaire
Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
UniversitéA. Mira de Béja·ýa

Facultédes Sciences Exactes

Département de Recherche Opérationnelle

M'emoire de fin d''etudes

Pour l'obtention du Diplôme Master
En
Recherche Opérationnelle

Th`eme

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

Estimation de l'erreur de troncature de

? l'espace d'etats du système d'attente M/M/1 :

? Méthode de StabilitéForte ?

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

Présentépar :

Melle Haoua LARAB

Devant le jury composéde :

Présidente M^me O. LEKADIR M C B

Encadreurs

Mr K. ABBAS M C B

Mr D. A^·ISSANI Professeur

Examinateurs

Mme K. ADEL C C

Melle S. HAKMI M A

Année Universitaire 2010 - 2011

Table des matières

Introduction générale 1 Généralités sur les chaàýnes de Markov			2 5
	1.1	Processus stochastiques	5
		1.1.1 Définitions	6
		1.1.2 Processus Markoviens	6
	1.2	Chaàýnes de Markov a` temps discret	7
		1.2.1 Définitions et propriétés	7
	1.3	Exemples	7
		1.3.1 File d'attente en temps discret	7
		1.3.2 La Gestion des stocks	8
	1.4	Chaàýnes de Markov discrètes	8
		1.4.1 Classification des états d'une chaàýne de Markov	8
	1.5	Classification des chaàýnes de Markov discrètes	10
		1.5.1 Chaàýnes de Markov homogènes	10
		1.5.2 Chaàýnes de Markov irréductibles	10
		1.5.3 Chaàýnes de Markov absorbantes	13
	1.6	Distribution initiale et comportement transitoire	13
		1.6.1 Distribution initiale	13
	1.7	Comportement asymptotique des chaàýnes irréductibles	13
		1.7.1 Comportement asymptotique	13
		1.7.2 Distribution limite	14
		1.7.3 Distribution invariante	14
		1.7.4 Comportement asymptotique des chaàýnes irréductibles et apériodiques 15
		1.7.5 Chaàýnes de Markov ergodiques	16
	1.8	Conclusion	17
2	Systémes de files d'attente		18
	2.1	Introduction et structure d'un système d'attente	18
		2.1.1 Classification et formalisation d'un système de files d'attente . . . .	19
		2.1.2 Analyse mathématique d'un système de files d'attente	21
	2.2	Files d'attente markoviennes	21
		2.2.1 La file d'attente M/M/1	21

2.2.2 La file d'attente M/M/m 23

2.2.3 La file d'attente M/M/1/N 25

2.3 Files d'attente non Markoviennes 28

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

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

2.4 Conclusion 33

3 Chaàýnes de Markov tronquées 34

3.1 Chaàýnes de Markov tronquées 34

3.1.1 Principe de troncature 35

3.1.2 Définitions 35

3.2 Différentes techniques de la troncature des chaàýnes de Markov 36

3.2.1 Augmentation linéaire 37

3.2.2 Renormalisation 37

3.2.3 Distance entre les distributions stationnaires 39

3.3 Exemple de la troncature sur un réseau de files d'attente en tandem avec

blockage 39 3.4 Exemple illustratif sur les techniques de troncature par l'augmentation linéaire 41 3.5 Conclusion 46

4 Calcul de la borne de stabilitéforte pour le cas de troncature de la capacitéd'attente de la file M/M/1 47

4.1 Préliminaires et notations 47

4.1.1 Borne de la stabilitéforte 48

4.2 Troncature de la capacitéd'attente de la file M/M/1 49

4.2.1 Description du modèle et position du problème 49

4.3 L'augmentation de la première colonne 50

4.3.1 Calcul de la borne de stabilitéforte :Augmentation de la premi`ere

colonne 51

4.4 L'augmentation uniforme 57

4.4.1 Calcul de la borne de stabilitéforte : Augmentation uniforme . . 58

4.4.2 Calcul de la borne réelle 62

4.4.3 Bornes de déviation du nombre moyen de clients 62

4.5 Conclusion 62

5 Comparaison des techniques de troncature 63

5.1 Applications numériques 63

5.1.1 Environnement MATLAB 63

5.1.2 Approche algorithmique 64

5.1.3 Algorithme de StabilitéForte 64

5.1.4 Organigramme de stabilitéforte 65

5.1.5 Variation de l'erreur en fonction de 66

5.1.6 Variation de l'erreur en fonction de N 67

5.1.7 Variation de l'erreur en fonction 3 75

5.2 Conclusion 75

Conclusion générale 76

Bibliographie 78

Introduction générale

L

a mod'elisation est un outil de la recherche d'une expression simplifi'ee d'un ph'enomène naturel dans sa complexit'e, et qui permet de pr'evoir le comportement dans un inter-

valle de temps et d''echelle de grandeur. De plus, lorsque la mod'elisation tient compte des facteurs al'eatoires, on parle alors de mod'elisation stochastique et de modèle stochastique. Or la th'eorie analytique des modèles stochastiques s'avère d'une port'e limit'ee en raison de la complexit'e des r'esultats connus. En effet, dans la majorit'e des cas, on se retrouve confront'e a` des systèmes d''equations dont la r'esolution est complexe, qui est en g'en'eral difficile voire impossible, c'est ainsi le cas pour les fonctions g'en'eratrices, les transform'ees de Laplace-Stieltjes.

Par ailleurs, on peut citer le degr'e de difficult'e pour l'obtention de certaines caract'eristiques dans quelques modèles stochastiques tels que les modèles de files d'attente avec vacance, serveur non fiable, arriv'ees par groupe, avec rappel et avec impatience, etc. Pour pallier a` toutes ces difficult'es, les chercheurs ont fait recours a` des m'ethodes d'approximation. Ainsi, lors de l'analyse d'un modèle stochastique, on est souvent amen'e a` remplacer le système r'eel (g'en'eralement complexe), par un système plus simple id'eal dont les r'esultats analytiques sont exploitables.

Dans le même contexte, les chaàýnes de Markov constituent un outil principal pour la mod'elisation et la r'esolution de problèmes dynamiques stochastiques. Elle sont utilis'ees, dans des situations d'applications pratiques telles que 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 pannes), et la th'eorie d'inventaire.

Cependant,en simplifiant quelques hypothèses la mod'elisation des situations r'eelles, est entach'ee par quelques erreurs dues au processus de mod'elisation lui-même. D'o`u la paru-

tion, a` ce niveau du problème, de calcul des bornes de perturbation ou du problème de stabilité.

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 complexitédu calcul, on rencontre alors des problèmes liés a` leur dimension. En effet, des modifications dans le système peuvent être suggérées pour obtenir des bornes simples ou des approximations faciles a` calculer. Dans ce sens, la troncature de l'espace des états est souvent exigée dans les calculs qui concernant les chaàýnes de Markov infinies. L'objectif de ce travail est de trouver la technique de troncature la plus efficace pour l'estimation de l'erreur de troncature de l'espace d'état de la file d'attente M/M/1 par la méthode de stabilitéforte.

Dans la majoritédes travaux, l'attention des chercheurs était plus focalisée sur l'objectif d'analyse des modèles et la stabilitéétait obtenue dans la plupart des cas, souvent pour des hypothèses particulières.

L'étude de la stabilitédans la théorie des file d'attente, consiste a` délimiter le domaine dans lequel le modèle idéal peut être utilisécomme une bonne approximation du modèle réel (perturbé). Ainsi, elle occupe une place remarquable dans la théorie qualitative des systèmes dynamiques, ainsi que dans celle des système stochastiques. On dit qu'un système est stable si une petite perturbation dans ses paramètres entraàýne une petite perturbation dans ses caractéristiques. La stabilitése définie alors comme étant la capacitédu système a` résister aux perturbations .

Depuis les années soixante dix, plusieurs méthodes de stabilitédes modèles stochastiques ont étéélaborées : Méthode des fonctions tests élaborée par Kalashnikov [28], méthode métrique initiée par Zolotariev [52] et Rachev [36], méthode de convergence faible introduite par Stoyan [43] méthode de renouvellement proposépar Borovkov [5], méthode de stabilitéforte élaborée par Aissani et Kartashov [3, 30], méthode de stabilitéabsolue introduite par Ispen et Meyer [25] et la méthode du développement en séries proposépar Heidergott et Hordjik [17, 19].

La méthode de stabilitéforte (ou des opérateurs) a étéélaborée par Aissani et Kartashov au début des années 1980. L'intérêt de cette méthode est que l'ergodicitéuniforme par rapport a` une norme donnée est préservée sous de petites perturbations du noyau de transition. Elle nous donne un calcul exact des constantes dans les estimations quantitatives de stabilité. Les résultats fondamentaux de cette méthode ont fait l'objet de la publication en 1996 de la monographie de Kartashov [30]. Cette méthode a étéappliquée a` plusieurs modèles stochastiques régi par des chaàýnes de Markov : Modèles de files d'attente classiques (Bouallouche et Aissani[6, 7] .

Ce mémoire comprend cinq chapitres, une conclusion générale et enfin une liste de

r'ef'erences bibliographiques.

* Le premier chapitre permet de pr'esenter les g'en'eralit'es sur les chaàýne de Markov .

* Le deuxième chapitre est consacr'ee aux systèmes de files d'attente et aux caract'eristiques de quelques systèmes d'attente classiques tels que : M/M/1, M/M/m, M/M/1/N, M/G/1, G/M/1.

* Ensuite, le troisième chapitre concerne une synthèse sur les r'esultats et les diff'erentes
techniques de troncature connues dans la litt'erature sur les chaàýne de Markov.

* Le quatrième chapitre est l'ossature de notre travail. En effet, dans ce chapitre on s'int'eressera a` l'estimation de l'erreur par la m'ethode de stabilit'e lors de la troncature de l'espace d'etat de la chaàýne de Markov d'ecrivant l'etat de la file d'attente M/M/1, et ce, en consid'erant plusieurs techniques de troncature.

* Enfin, le cinquième chapitre est consacr'e a` la comparaison des deux techniques de troncature par l'application num'erique de l'algorithme de stabilit'e forte.

* Notre m'emoire s'achève par une conclusion g'en'erale, o`u nous mettons l'accent sur quelque perspectives de recherche induites par ce travail.

1

Généralités sur les chaàýnes de Markov

Les chaàýnes de Markov sont un objet essentiel des probabilités modernes. Elles apparaissent et sont utilisées avec succès dans des domaines aussi divers que la physique, la biologie, les sciences sociales ou l'informatique.

L'objet de ce chapitre est de présenter la théorie des chaàýnes de Markov. Nous nous limiterons au cas particulier (essentiel) o`u l'espace des états est un ensemble dénombrable.

Ainsi, nous introduirons quelques concepts fondamentaux des chaàýne de Markov. En particuliers, nous nous focaliserons sur le problème d'existence d'une distribution stationnaire.

1.1 Processus stochastiques

Les processus stochastiques décrivent l'évolution d'une grandeur aléatoire en fonction du temps. Les processus stochastiques ont pris un énorme essor, non seulement en finances, dans la fiabilitédes systèmes, en mécanique statistique ou encore dans les sciences de la vie, mais également dans des techniques appliquées a` des problèmes qui au départ n'ont rien a` voir avec les probabilités ou le risque. Tel est le cas des méthodes d'optimisation globale, ou du traitement de certains problèmes de l'analyse numérique.

1.1.1 D'efinitions

Un processus stochastique _{X(t)}t?T est une fonction du temps dont la valeur a` chaque instant dépend de l'issue d'une expérience aléatoire .

Un processus stochastique est donc une famille de variables aléatoires (non indépendantes).
On appelle espace des états l'ensemble S o`u les variables {Xt} prennent leurs valeurs[15].

L'espace peut être discret ou continu. Le temps peut être discret, continu, temps continu o`u les évolutions n'ont lieu qu'àdes instants discrets.

Une trajectoire d'un processus est décrit par un couple (espace, temps). Par conséquent, on distingue quatre types de processus (si l'ensemble S est fini ou dénombrable le processus est appeléune chaàýne) :

- Suite stochastique a` espace d'états discret; - Suite stochastique a` espace d'états continu; - Processus continu a` espace d'états discret; - Processus continu a` espace d'états continu.

Quelques exemples

- EC/TC : réaction chimique ou le mouvement de particules en interaction;

- EC/TD : modèle journalier de remplissage d'un barrage;

- ED/TC : nombre de particules au cours d'une réaction chimique;

- ED/EvD : nombre de clients dans une file d'attente;

- ED/TD : gain d'un joueur a` chaque étape, somme de variables aléatoires indépendantes.

On peut aussi caractériser un processus {Xt} par les relations qui existent entre les variables Xt qui le compose.

1.1.2 Processus Markoviens

La notion de processus Markovien repose sur le principe de processus sans post action, on entend un processus pour lequel la probabilitéqu'il se trouve dans un état (ou un ensemble d'états) a` l'instant t ne dépend que de son état au dernier instant connu s < t. Plus précisément, il est défini comme suit :

Un processus stochastique {Xt, t = 0} a` valeurs dans l'espace d'états S est satisfait la propriétéde Markov si pour tout instant t, et tout sous ensembles d'états I c S, il est vrai que

P[Xt+Ä E I/X_u, 0 = u = t] = P[Xt+Ä E I/Xt] ?Ä = 0.

Un processus stochastique vérifiant la propriétéprécédente est appeléprocessus de Markov ou processus Markovien.

1.2 Chaàýnes de Markov a` temps discret

Les chaàýnes de Markov sont des processus markoviens a` temps discrets.

1.2.1 Définitions et propriétés

Une chaàýne de Markov a` temps discret {X_n, m = 0, 1, ...} définie sur un espace d'états S satisfait la propriétéde Markov si pour tout m = 1 et pour tout i E S, il est vrai que :

P[X_n = i/Xn_1 = in_1, ..., X0] = P[X_n = i/Xn_1 = i - 1]. (*)

Une chaàýnes de Markov a` temps discret est un processus stochastique {X_n, m = 0} satisfaisant les trois restrictions suivantes :

1. le processus est a` temps discret;

2. l'espaces des états S est fini ou dénombrable;

3. le processus satisfait la propriétéde Markov (*).

1.3 Exemples

1.3.1 File d'attente en temps discret

File d'attente en temps discret [35] : On considère une file d'attente qui se forme a` un guichet. Dans ce cas, X<sub>n</sub> désigne le nombre de clients dans la file en attente ou le nombre de clients entrain de se faire servir a` l'instant n. Entre les instants n et n+1 arrivent Yn+1 clients, et si X_n > 0 partent _Zn+1 clients. On suppose que X0, Y1, _Z1,Y2, Z2, ... sont indépendantes, vérifiant 0 < P(Y_n = 0) < 1, et les Z_n vérifient P(Z_n = 1) = p = 1 - P(Z_n = 0). C'est a` dire que

Xn+1 = X_n + Yn+1 - 1{X_n>0}Zn+1.

1.3.2 La Gestion des stocks

Une entreprise doit g'erer le stock d'un article dont la demande, a` chaque p'eriode n, est une variable al'eatoire D_n de distribution

P[Dk = k] = ak k = 0,1,2,...

Supposons que ce stock soit g'er'e de la manière suivante [4] :

Au d'ebut de la p'eriode n, le niveau X_n du stock est observ'e et un r'eapprovisionnement, dont le d'elai de livraison est suffisamment court pour qu'il puisse servir a` satisfaire la demande de la p'eriode, est d'ecid'e selon la règle :

. Si X_n < s, commander S - X_n unit'es;

. Si Xn = s, ne rien commander.

Une telle règle de gestion est connue sous le nom de politique (s, S) o`u s et S sont deux paramètres donn'es .

Au d'ebut de la p'eriode n + 1, le niveau du stock est

{ S - D_n, si X_n < s;

Xn+1 = (1.1)
x - D_n, si X_n = s.

La suite des niveaux de stock {X_n,n = 0, 1,2, ...} d'efinit donc une chaàýne de Markov dont l'espace des 'etats est 'egal a` S. De plus, pour tout n = 1, nous avons :

P[Xn = j/Xn_1 = i] =

ak, si i < s et j = S - k, k = 0,1,2,... ak, si i = s et j = i - k, k = 0,1,2,... 0, autrement.

(1.2)

1.4 Chaàýnes de Markov discrètes

Pour ce type de chaàýne de Markov, l'espace des 'etats S est un ensemble d'enombrable ou fini. On d'esignera par les lettres i, j, ... les points de cet espace. Une chaàýne de Markov est homogène (dans le temps) si la probabilit'e d'effectuer une transition d'un 'etat dans un autre est ind'ependante de l'instant auquel a lieu cette transition.

1.4.1 Classification des états d'une chaàýne de Markov

Afin d'aborder le comportement a` long terme d'une chaàýne de Markov, il nous faut introduire les diff'erents 'etats d'un processus Markovien.

On peut aussi distinguer les 'etats d'une chaàýne de Markov par une propri'et'e concernant le renouvellement des 'etats.

Un état j ? S est accessible a` partir d'un état i si la probabilitéde transition de i en j en un certain nombre d'étapes est positive, i.e. ?n > 0 tel que;

pij > 0.

(n)

Si j est accessible a` partir de i, et i a` partir de j, les états i et j sont dits communicants. Par définition un état est toujours communicant avec lui-même.

La communication de i et j sera notée i ? j, la relation ? est une relation d'équivalence et les classes d'équivalence forment une partition de S. Chaque classe est composée d'états communicants.

Une classe est persistante si elle correspond a` un sommet sans successeur de graphe réduit, dans le cas contraire la classe est transitoire.

Un état persistant (ou récurrent) s'il appartient a` une classe persistante.

Un état i est récurrent si :

Fii(+00) = 1.

o`u Fij(n) = _Pn fij(k) représente la probabilitépour que la chaàýne passant en i atteigne

i=1

j en moins de n + 1 transitions.

_f(n)

ij la probabilit'e de premier passage.

_f(n)

ij = P(X_n = j,Xk =6 j).

et le temps de premier passage

Tij = min{k > 0 : Xk = j,X0 = i}.

Les états récurrents eux-mêmes se divisent en deux sous-catégories :

'Etats récurrents non nuls :

Un état i est récurrent non nul si, la chaàýne partant de i repassera par i au bout d'un temps fini .ie,

ui = _X8 nfii(k) < 00.

n=1

'Etats récurrents nuls : un état i est récurrent nul si,la chaàýne partant de i repassera par i au bout d'un temps infini.i.e

ui = +00.

- Un état i est transitoire si, la chaàýne partant de i peut ne pas repasser par i,

Fii(+8) < 1.

Plus précisément :

Il existe trois type d'états : transients (on n'y revient pas toujours), récurrents nuls (on y revient toujours, au bout d'un temps moyen infini), ou récurrents positifs (on y revient une infinitéde fois, a` intervalle de temps finis, en moyenne),

- Périodicitéd'un état : un état i est périodique de période d(i) si :

d(i) = PGCD{n,pii > 0},

si d(i)=1 , »i» est dit apériodique.

o`u PGCD est le Plus Grande Commun Diviseur .

Finalement, un état est dit ergodique s'il est récurrent non nul et apériodique. - Un état est absorbant, s'il fait a` lui seul une classe persistante;

- Un état i est absorbant, si seulement si pii = 0 et pij = 1, ?j =6 i.

1.5 Classification des chaàýnes de Markov discrètes

On dit qu'une chaàýne de Markov X est discrète si son espace d'états S est fini ou dénombrable.

1.5.1 Chaàýnes de Markov homogènes

Une chaàýne de Markov est homogène (dans le temps) si la probabilitéd'effectuer une transition d'un état dans un autre est indépendante de l'instant auquel a lieu cette transition [16]. En d'autre termes, pour tout paire d'états (i,j) et pour tout instant n

P[X_n = j/Xn_1 = i] = P[Xn+k = j/Xn+k_1 = i],

quel que soit k = 0.

1.5.2 Chaàýnes de Markov irréductibles

Les notions de récurrence et d'irréductibilitéadmettent une caractérisation simple pour les chaàýne discrètes.

D'efinition 1.1 : Une chaine de Markov est irr'eductible si elle n'est constitu'ee que d'une seule classe d''etats communicants.

On peut aussi faire une classification probabiliste des 'etats d'une chaine de Markov. D'efinissons la probabilit'e de premier passage : ?k = 1, ..., n - 1/X0 = i

_f(n)

ij = P(X_n = j, Xk =6 j),

et le temps de premier passage

Tij = min{k > 0 : Xk = j; X0 = i},

Nous avons alors, Posons :	fi(j n) = P(Tij = n).
Fij(n) =		Xn i=1	fij(k).

qui repr'esente la probabilit'e pour que la chaine passant en i atteigne j en moins de n + 1 transitions.

Th'eor`eme 1.1 [16] : Consid'erons une chaine de Markov X_n irr'eductible. Pour tout i ? S ;

ôi = inf{k > 0; Xk = i}.

On voit que ôi est le temps d'atteinte de l''etat i, i.e, le temps de premier passage. Pour tout i, j ? S, on a

Ei(ôi) =

X+ n=0

Pn(i, j).

C'est l'esp'erance du nombre de passages par j partant de i.

Les conditions suivantes sont 'equivalentes :

1. Il existe un 'etat i ? S tel que Ei(ôi) < +8 ;

2. Pour tout 'etat i ? S, Ei(ôi) < +8;

3. La chaine de Markov poss`ede une probabilit'e invariante ð.

Sous ces conditions, la chaine est dite r'ecurrente positive et ð est la seule probabilit'e invariante. Pour tout k ? S,

1

Ek(ôk)^,

ð(k) =

et pour tout i ? S,

ð(k) = Ei(ôi)Ei(Óô%-1

1 n=0 1k(Xn)).

On dit qu'une suite (x_n) de S tend vers l'infini si pour toute partie finie F de S, x_n n'appartient pas a` F pour tout n assez grand.

Définition 1.2 : Une chaàýne de Markov est irréductible si son graphe représentatif est fortement connexe. Dans le cas contraire la chaàýne est réductible.

Les deux propriétés suivantes qui découlent directement de la définition d'une classe persistante et des états communiquants, auraient également pu servir de définition d'une chaàýne irréductible.

Propriété1.1 : Une chaàýne de Markov est irréductible, si pour tout état i et j, il existe in = 0 (pouvant dépendre de i et j) tel que :

P ^(m)

ij > 0.

Propriété1.2 : Une chaàýne de Markov est irréductible si et selement si toute paire d'états sont communiquants.

Proposition 1.1 : Si S est un espace d'états fini, toute chaàýne irréductible est récurrente.

Théorème 1.2 :

On considère une chaàýne de Markov irréductible. Alors, un et un seul des deux cas suivants peut se produire :

Cas récurrent : Tous les états sont récurrents et partant de tout point, la chaàýne visite une infinitéde fois tous les autres, presque sàurement.

Cas transitoire : Partant de tout état, X_n tend vers l'infini, presque sàurement.

Quelques autres propriétés [4]

. Une chaàýne de Markov irréductible ne possédant qu'une seule classe et tous ses états ont la même période. Nous dirons qu'une telle chaàýne est périodique. Apériodique dans le cas contraire.

. Une chaàýne de Markov irréductible est fortement irréductible si et seulement si elle est irréductible et apériodique.

. Si P est la matrice de transition d'une chaàýne de Markov irréductible, alors tous les états ont même nature (récurrents positifs ou bien récurrents nuls ou bien récurrents).

1.5.3 Chaàýnes de Markov absorbantes

Une chaàýne de Markov est absorbante si tous ses états persistants sont absorbants, c'est a` dire si chacune de ses classes persistantes ne comporte qu'un seul état.

- Une chaàýne possédant des états absorbants n'est pas irréductible (sauf si l'espace d'états est réduit a` un point).

- Une chaàýne irréductible qui est transiente ou récurrente nulle, ne possède pas de probabilitéinvariante.

1.6 Distribution initiale et comportement transitoire

1.6.1 Distribution initiale

La distribution des états d'une chaàýne de Markov après n transitions est notée ð⁽ⁿ⁾. Cette distribution est un vecteur de probabilités contenant la loi de la variable aléatoire X_n

ð_i = P [X_n = i],

⁽ⁿ⁾ Vi E S.

En l'occurrence, ð⁽⁰⁾ est la distribution initiale.

Remarque 1.6.1 : Si l'état initial est connu avec certitude et égal a` i, on a simplement ð_i = 1 et ð(0)

(0) j = 0 pour tout j =6 i.

Comportement transitoire

Théorème 1.3 [13] : Soit P la matrice de probabilités de transition d'une chaàýne de Markov et ð⁽⁰⁾ la distribution de son état initial. Pour tout n = 1, on a :

ð(n) = ð^(n--1)P, et ð⁽ⁿ⁾ = ð⁽⁰⁾Pⁿ.

1.7 Comportement asymptotique des chaàýnes irréductibles

1.7.1 Comportement asymptotique

L'étude du comportement a` long terme d'une chaàýne de Markov cherche a` répondre a` des questions aussi diverses que :

. La distribution ð⁽ⁿ⁾ converge-t-elle, lorsque n ? 8?

. Si la distribution ð⁽ⁿ⁾ converge lorsque n ? 8, quelle est la limite ð et cette limite est-elle indépendante de la distribution initiale ð⁽⁰⁾ ?

. Si l'état i est persistant, quelle est la proportion du temps passédans cet état et quel est le nombre moyen de transitions entre deux visites successives de cet état?

. Si l'état i est transitoire, quel est le nombre moyen de visites de cet état?

1.7.2 Distribution limite

On dit qu'une chaàýne de Markov converge vers ð ou possede une distribution limite ð

si

lim n?8

ð(n) = ð.

indépendamment de la distribution initiale ð⁽⁰⁾ et si ð est une distribution de probabilité. La convergence d'une chaàýne de Markov est donc une propriétéqui ne dépend que de la matrice de transition P.

Théorème 1.4 (Théorème d'existence des distributions limites [37]) :

Si la matrice de transition P est telle qu'une au moins de ses puissances n'a que des termes

strictement positifs, alors

ð(n) = ð.

quelle que soit la distribution initiale ð⁽⁰⁾,et

Pn = P^*,

lorsque n --* 00. ð est un vecteur de probabilitéstrictement positif, et p^* une matrice dont toute les lignes sont identiques au vecteur limite ð. En plus

ðP^* = ð.

1.7.3 Distribution invariante

Une distribution de probabilitédiscrete ð = (ð1, ð2, ...) est appelée invariante ou stationnaire par rapport a` une matrice stochastique P si

ð = ðP.

En particulier, si la loi de X0, notée í0, est une probabilitéinvariante, alors la loi de X1
est í1 = í0P = í0, et en itérant, on obtient que X_n a même loi que X0. La loi de X_n est

donc constante, on dit aussi stationnaire, au cours du temps, d'o`u le nom de ^probabilitéstationnaire [10].

Propriété1.3 :Si lim n?8

ð(n) existe, alors la limite est une distribution invariante.

Théorème 1.5 (Théorème d'existence des distributions stationnaires [37]) : Une chaàýne de Markov possède toujours au moins une distribution invariante, ce qui n'est plus nécessairement vrai si l'espace des états est infini.

Théorème 1.6 :Une chaàýne de Markov possède autant de distributions invariantes linéairement indépendantes que la multiplicitéde la valeur propre 1 de sa matrice de transition.

Théorème 1.7 [37] : Une chaàýne de Markov finie admet une unique distribution stationnaire si et selement si elle comprend une seule classe récurrente.

Théorème 1.8 [16] : La distribution ð⁽ⁿ⁾ des états d'une chaàýne de Markov converge vers une distribution (invariante) ð^* indépendante de la distribution initiale ð⁽⁰⁾, si et seulement si la suite des puissances de la matrice de transition P de la chaàýne converge vers une matrice (stochastique) P * dont toutes les lignes sont égales entre elles. De plus, si tel est le cas, chaque ligne de P * est égale a` distribution limite ð^*.

Théorème 1.9 [37] : Si ð est la distribution limite d'une chaàýne de Markov, alors ð est l'unique distribution stationnaire de cette chaàýne.

1.7.4 Comportement asymptotique des chaàýnes irréductibles et apériodiques

Le théorème suivant résume le comportement asymptotique des chaàýnes irréductibles et apériodiques.

Théorème 1.10 [13] : Soit P la matrice de transition d'une chaàýne irréductible et apériodique. Les propriétés suivantes sont vérifiées : - La matrice P ⁿ tend vers une matrice stochastique

P* lorsque n tend vers l'infini; - Les lignes de P * sont toutes égales entre elles; - P ij * > 0 pour tout i; j ? S; -Pour toute distribution initiale ð⁽⁰⁾,

lim n?8

ð(n) = lim n?8

ð(0)Pn = ð*

-ð^* est la solution unique du système :

{ ðP = ð;

(1.3)

ð1 = 1.

ð* égal a` n'importe quelle ligne de la matrice P *; -Pour tout i ? S, ð* i = ui 1 o`u ui est l'espérance du nombre de transitions entre deux visites successives de l'état i.

1.7.5 Chaàýnes de Markov ergodiques

Ce qu'on appelle propri'et'es ergodiques pour une chaàýne de Markov concerne l''etude de ces comportements a` l'infini, soit de la chaàýne elle-même, soit de ses probabilit'es de transition P n.

Une chaàýne de Markov est ergodique si elle admet une distribution asymptotique, i.e. si lim ð(n) existe, unique et ind'ependante de la distribution initiale.

n-400

Propriété1.4 Les chaàýnes irr'eductibles et ap'eriodiques sont ergodiques.

Théorème 1.11 (Théorème ergodique en moyenne [26]) :

Lorsque n ? 8, la matrice ðⁿ converge ('el'ement par 'el'ement) vers la matrice ð de composantes ðij = fij//ij ^(avec ðij = 0 si /ij = 1). o`u /ii est l'esp'erance du nombre de transitions entre deux visites successives de l''etat i.

Théorème 1.12 (Théorème ergodique [16]) :

Soit {X_n;n = 0, 1, ...} une chaàýne de Markov ergodique de distribution stationnaire ð^* et f une fonction r'eelle d'efinie sur l'espace des 'etats S de la chaàýne. Alors,

lim n-400	1	Xn k=0	X f(Xk) = i?S	ð* i f(i),	presquesàurement.
	n + 1

La moyenne temporelle est donc 'egale a` la moyenne spatiale par rapport a` la probabilit'e invariante.

Théorème 1.13 [26] : Si X est une chaàýne irr'eductible, il existe une probabilit'e invariante
si et seulement si la chaàýne est positive. Dans ce cas, la probabilit'e invariante est unique et

donn'ee par

1

ði =

, /ii

Théorème 1.14 [16] : Une chaàýne de Markov irr'eductible poss'ede au plus une probabilit'e invariante ð et alors ð⁽ⁱ⁾ > 0 pour tout i E S.

Si S est fini, alors toute chaàýne de Markov irr'eductible possède une et une seule probabilit'e invariante.

1.8 Conclusion

Dans ce chapitre, nous avons pr'esent'e les 'el'ements de base de la th'eorie des chaàýnes de Markov, et quelques types des chaàýnes de Markov (chaàýnes irr'eductibles, r'ecurrentes, 'ergodiques,...) qui seront utilis'ees dans la suite de ce m'emoire.

L''etude de comportement a` long terme d'une chaàýne de Markov, nous permet de r'epondre a` quelques questions aussi diverses que, la convergence d'une distribution ð⁽ⁿ⁾ lorsque n --* +8.

2

Systémes de files d'attente

2.1 Introduction et structure d'un système d'attente

Les premiers résultats sur les systèmes de files d'attente ont étéproposés par l'ingénieur électricien Erlang au début du vingtième siècle, dans le but de décrire les phénomènes de congestion et d'attente ont étéutilisées dans la modélisation des systèmes de production et des systèmes informatique [14].

D'une manière générale, une file d'attente est la donnée d'une (ou plusieurs) unitéde service o`u arrivent des clients qui demandent une certaine durée d'utilisation de cette unité. Quand les clients ne peuvent accéder a` cette unitéde service, ils attendent dans une file d'attente (qui peut être éventuellement de capacitélimitée).

FIGURE 2.1 - Système de files d'attente a` un seul serveur

2.1.1 Classification et formalisation d'un système de files d'attente

En g'en'eral, une file d'attente est d'efinie par :

1) Un processus d'arriv'ee de clients, i.e. une suite croissante {T_n, m = 0}, o`u T<sub>n</sub> est l'instant d'arriv'ee du <sup>m`eme</sup> client. Le processus d'arriv'ee est alors la fonction de comptage associ'ee aux temps d'inter-arriv'ees. Si de plus la loi est une exponentielle, alors le processus des arriv'ees est un processus de Poisson, et on utilise la notation M pour souligner le caractère markovien.

2) Une suite de r'eels {S_n, m = 0} avec S_n est la dur'ee de service requise par le ^m`eme client. Nous verrons que dans ce cas, si le processus d'arriv'ee est un processus de Poisson, alors l''evolution de la taille de la file d'attente est une chaàýne de Markov.

3) Une discipline de service . Distributions des inter-arrivées

Les symboles utilis'es pour d'ecrire les processus d'entr'ee et de service sont :

- M : Loi exponentielle (processus de Markov);

- G : Loi g'en'erale;

- GI : Loi-g'en'erale ind'ependante;

- D : Loi constante (d'eterministe);

- Ek : Loi Erlang-k;

- Hk : Loi hyper exponentielle d'ordre k;

- Ck : Loi de Cox-k.

Discipline de service

- FIFO(First In First Out) : Les clients sont servis suivant leur ordre d'arriv'ee; - LIFO(Last In First Out) Le dernier client arriv'e est le premier servi;

- Services partagées Tous les clients sont servis en même temps, mais avec une vitesse inversement proportionnelle au nombre de clients;

- Aléatoire Le prochain client de la file d'attente a` être servi est choisi au hasard;

- SPT (Shortest Processing Time) Le prochain client de la file d'attente a` être servi est celui qui a la requête la plus courte;

-

...

Ces trois 'el'ements sont consid'er'es comme les paramètres essentiels du système, Kendall [15] a propos'e de repr'esenter les modèles stochastiques de files d'attente sous forme d'un sextuplet

A/S/Ns/Nc/K/Z,

. A concerne la loi du processus des inter-arriv'ees {E_n, m = 0} = {Tn+1 - T_n, m = 0};

. S concerne la loi des dur'ees de service S_n ;

. N_s est le nombre de guichets ou serveurs;

. N_c est la capacit'e de la file d'attente;

. K concerne la source des clients;

. Z est la discipline de service.

Lorsque les trois derniers 'el'ements ne sont pas mentionn'es, il est sous-entendu que la capacit'e et la source sont infinies et que la discipline est FIFO (premier arrivé, premier servi).

Caractéristiques d'un système de files d'attente

La th'eorie des systèmes d'attente a comme objectif d'en 'etudier les structures et de calculer les valeurs caract'eristiques permettant de d'ecrire les performances d'un tel système : L : Nombre moyen de clients dans le système de files d'attente;

L_q : Nombre moyen de clients dans la file;

W : Temps moyen de s'ejour d'un client dans la file (attente + service);

W_q : Temps moyen d'attente d'un client dans la file.

Ces valeurs sont li'ees les unes aux autres par les relations suivantes [37] :

L = ë_eW ;

L_q = ëeWq;

;

1

W = W_q + u

ë_e

L = L_q + .

u

Les deux premières relations sont appel'ees Formules de Little, avec : ë_e : Taux d'arriv'ees dans le système;

u : Taux de service;

1 : Intervalle de temps moyen s'eparant deux arriv'ees cons'ecutives;

ë_e

i : Dur'ee moyenne de service j;

u

p = ëeu : Taux d'occupation du système.

2.1.2 Analyse mathématique d'un système de files d'attente

La description mathématique d'une file d'attente se fait par l'introduction des processus stochastiques suivants :

. {Xt, t = 0} o`u Xt correspond au nombre de clients dans le système a` la date t; . {W_n, m = 1} o`u W<sub>n</sub> correspond a` la durée d'attente du ^mieme client;

. {At, t = 0} o`u At est le nombre d'arrivée a` la date t;

. {Nt, t = 0} o`u Nt est le nombre de clients pouvant être servis si le serveur travaillait sans interruption durant la période [0,t];

. {Dt, t = 0} o`u Dt est le nombre d'arrivées a` la date t.

Ces quantités peuvent être considérées comme les caractéristiques essentielles du système.

2.2 Files d'attente markoviennes

Les files d'attentes makoviennes sont celles pour lesquelles les inter-arrivées et les durées de service sont exponentielles. Leur notation de Kendall sera de la forme M/M/... (M comme markovien).

2.2.1 La file d'attente M/M/1

Pour ce système, le plus simple de la théorie des files d'attente, le flux des arrivées est poissonnien de paramètre ë et la durée de service est exponentielle de paramétre u.

Régime transitoire

Soit le processus stochastique {X(t), t = 0} : »le nombre de clients dans le système a` l'instant t ». Gràace aux propriétés fondamentales du processus de Poisson et de la loi exponentielle suivante :

. P(exactement une arrivée pendant At) = At + o(At);

. P(aucune arrivée pendant At )= 1 - At + o(At); . P(2 arrivées ou plus pendant At)= o(At);

. P(exactement 1 départ pendant At/X(t) = 1 )= ut + o(At);

. P(aucun départ pendant At/X(t) = 1 )= 1 - ut + o(At);

. P(2 départs ou plus pendant At )= o(At).

Dans ce cas, la matrice des taux de transition P = (Pij)i,j?N prend la forme suivante :

?
? ? ? ? ? ?

P=

?
??????

-A A 0 . .

-( + A) A 0

0 -( + A) A 0

...
...

0 -( + A) A

... 0 ...

Et le graphe représentatif du processus de naissance et mort de la file d'attente M/M/1 est donnésous la forme:

FIGURE 2.2 - Graphe représentatif du processus de naissance et de mort

{

P ' ₀(t) = -AP0(t) + P1(t); (2.1)
P ' _n(t) = -(A + )P_n(t) + _{APn_1(t)} + Pn+1(t), m = 1, 2, ...
o`u P_n(t) = P(Xt = m).

Si A < , le processus {Xt, t = 0} converge vers une variable aléatoire X dont la distribution ð est définie par [9] :

ð_n = (1 - p)pⁿ,

o`u p = A/ , m = 0,1,...

Caractéristiques de la file M/M/1

La file M/M/1 est stable (A < , c'est-à-dire p < 1).

- Le nombre moyen de clients dans la file L_q :

Le nombre moyen de clients dans la file ne dépend que du taux de charge p :

> E[m] = n>0

mð(m) = p 1 - p = Lq,

- Temps moyen de séjour W est obtenu par:

L W = ë			1
		=
			u(1 -- ñ)^,
qui peut se décomposer en :	1 W = u	ñ + u(1 -- ñ)^.

On déduit alors, le temps moyen passédans la file d'attente W_q :

ñ

W_q = u(1 -- ñ)^,

- D'après la formule de Little, le nombre moyen de clients dans le système de la file d'attente

stable M/M/1 est donnépar le produit de leur taux d'arrivée ë_e et leur temps de séjour moyen W :

L = ë_eW = ñ2 .

1 -- ñ

2.2.2 La file d'attente M/M/m

On considère un système identique a` la file M/M/1 exceptéqu'il comporte m serveurs identiques et indépendants les uns des autres.

On conserve les hypothèses : processus d'arrivées des clients poissonnien de taux u et temps de service exponentiel de taux ë (pour chacun des serveurs). Ce système est connu sous le nom de file M/M/m. L'espace d'états S est, comme pour la M/M/1 infini, S = {0, 1, 2, ...}. On a un processus de naissance et de mort de taux :

ë_n = ë.

un =

0, si n = 0;

nu, si 0 < n < m; (2.2)

mu, si n = m.

La condition de stabilitéici est ë < mu, et exprime le fait que le nombre moyen de clients qui arrivent a` la file par unitéde temps doit être inférieur au nombre moyen de clients que les serveurs de la file sont capables de traiter par unitéde temps.

On peut donner ð_n comme suit [15] :

ðk = ñkmm

{ (mñ)k

m! , k = m, m + 1, ...

k! , k = 0, 1..., m -- 1; (2.3)

avec,

m-1_X
k=1

mñ)^k k! ].

mñ)^m

ð0 = [1 + m!(1 - ñ) +

Le graphe représentatif du processus de naissance et mort est :

FIGURE 2.3 - Graphe de la file d'attente M/M/m

Caractéristiques de la file M/M/m

La file M/M/m, est plus simple (au niveau des calculs). On calcule d'abord le temps moyen de séjour et on déduit le nombre moyen de clients.

- Temps moyen de séjour W :

Le temps moyen de séjour d'un client se décompose en un temps moyen dans la file d'attente, plus un temps moyen de service. Il suffit alors d'appliquer la formule de Little a` la seule file

1 W = Wq + u

Lq = ë +

1 u

,

Il reste alors a` calculer le nombre moyen de clients en attente dans la file, L_q :

L_q = _X8 ð_n,

n=m+1

L_q = ñ (ë/u)ⁿ

(1 - ñ²) m!mn-m ð0.

o`u, ñ = ë/mu.

On en déduit l'expression du temps moyen de séjour

W = ñ (1 - ñ^2)

(ë/u)^n ð0 + m!m^n-m

1 u

,

- Nombre moyen de clients L :

Le nombre moyen de clients s'obtient alors par application de la formule de Little:

L = WA = A( p (A/u)

⁽¹

n 1

ð0 + ).

- p²) m!m^n-m u

2.2.3 La file d'attente M/M/1/N

On considère un système a` serveur unique identique a` la file M/M/1 exceptéque la capacitéde la file d'attente est finie. On a donc toujours les hypothèses suivantes :

Le processus d'arrivées des clients dans la file est un processus de Poisson de taux A et le temps de service d'un client est une variable aléatoire exponentielle de taux u.

Soit N la capacitéde la file d'attente, c'est le nombre maximal de clients qui peuvent être présents dans le système, soit en attente, soit en service.

Quand un client arrive alors qu'il y a déjàN clients présents dans le système, il est perdu.

Ce système est connu sous le nom de file M/M/1/N, l'espace d'états S est maintenant fini
S = {0, 1, 2, ..., N}, le nombre de clients dans la file ne peut donc jamais »partir» a` l'infini.

De plus, dès qu'un client est autoriséa` entrer, il sortira avec un temps de séjour dans la file fini, puisqu'il correspond au temps de service de tous les clients devant lui et que ce nombre est limitéa` N. Sur un temps très long, le débit de sortie sera donc bien égal au débit d'entrée, ce qui correspond bien a` la stabilitéinconditionnelle du système.

FIGURE 2.4 - Graphe de la file M/M/1/N

On décrit un tel système par le processus {X(t), t = 0} représentant le nombre de clients dans le système a` l'instant »t».

Le processus de naissance et de mort modélisant ce type de file d'attente est alors défini de la façon suivante :

{ A, n < k;

A_n = (2.4)
0, n = k.

{ u, n =6 0;

u_n = (2.5)
0, n = 0.

Régime transitoire

Le graphe représentatif de la file M/M/1/N est donné:

FIGURE 2.5 - Graphe de la file M/M/1/N

D'après ce graphe, on extrait les équations différentielles de Kolmogorov correspondantes au processus X(t) du système M/M/1/N qui sont identiques a` celles du système M/M/1 sauf pour n = N :

P0 0(t) = --ëP0(t) + uP1(t); P ^0 n(t) = --(ë + u)Pn(t) + ëPn-1(t) + uPn+1(t), n = 1, N; (2.6) P ^0 N(t) = --uPn(t) + ëPN-1(t).

Régime stationnaire

On note ð_n = P_n(t) la probabilitéstationnaire d'être dans l'état n (probabilitéque le système contient n clients). Ces probabilités peuvent être calculées en écrivant les équations

d'équilibre, o`u lim n?8

P ^0 n(t) = 0 :

ë

ð_n = u

ðn-1; n = 0...N,

o`u ñ = ë/u.

En appliquant n fois cette relation:

ð_n = ð0ñⁿ n = N,

ð0 :	1					1 - ñ
ð0 =
			N E n=0	ñn			1 - ñN+1 ,
Ou obtient finalement :		ðn = ( 1 - ñ 1 - ñN+1 )ñn.

N

En se servant de la condition de normalisation E ð_n = 1, on peut deduire la probabilite

n=0

Caract'eristiques du syst`eme M/M/l/N

-Nombre moyen de clients dans le syst`eme (L) :

L = ñ 1 - ñ	(N + 1)ñ^N+1
	1 - ñN+1 ,

A nouveau, lorsque N tend vers l'infini et ñ < 1, on retrouve les resultats de la file M/M/1 :

_L = ñ

1 - ñ.

Pour le syst`eme dont la capaciteest limit'ee a` N, le calcul de ë_e se fait comme suit :

ë_e = ë(1 - ð_n),

o`u, (1 - ð<sub>n</sub>) represente la probabilitede »non refus d'un client dans le syst`eme».

ñ L= (1 - ñ)	(N + 1)ñ^N+1
	1 - ñN+1 ,

A l'aide des formules de Little , on obtient

(N + 1)ñ^N+1 1 - ñN

-Nombre moyen de clients dans la file (L_q) :

L_q = L - ñ(1 - ðN) = (1 ^ñ ñ) - 1 - ñN+1 - ñ( 1 - ñN+1),

ñ Nñ^N+1 + ñ

L=

q (1 - ñ) 1 - ñ^N+¹ .

-

textbfTemps moyen de s'ejour el d'attente d'un client dans le syst`eme (W et W_q) : W = L/ë_e , on obtient [14] :

W = (1 + Nñ^N+1 - (N + 1)ñ^N u(1 - ñ)(1 - ñN) ,

W_q

-Nñ^N + (N - 1)ñ^N+1 + ñ

u(1 - ñ)(1 - ñ^N) .

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)^.

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

? ???

,

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 E_k>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 =

p4k

? ???????

.

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)

3.5 Conclusion

Dans ce chapitre, nous avons introduit une synthèse bibliographique sur le concept de la chaàýne de Markov tronquée. Ensuite, nous avons donnédeux exemples différents sur l'application de la technique de troncature, que nous avons illustrépar quelque exemples. Dans le prochain chapitre, nous nous intéressons a` l'application de ces techniques de troncature sur le cas de la file d'attente M/M/1, o`u nous estimerons également l'erreur due a` ces troncatures a` l'aide de la méthode de stabilitéforte.

4

Calcul de la borne de stabilitéforte pour le

cas de troncature de la capacitéd'attente de

la file M/M/1

Ces dernière ann'ees, la m'ethode de stabilit'e forte a 'et'e appliqu'ee pour divers problèmes et sur plusieurs modèles stochastiques qui peuvent être r'egis par des chaàýnes de Markov homogènes.

Dans ce chapitre, on s'int'eressera au cas d'application de la m'ethode de stabilit'e tout en consid'erant le problème de la troncature de l'espace des 'etats de la chaàýne de Markov d'ecrivant la file M/M/1. Notre objectif est de faire une 'etude comparative entre deux techniques de troncature (augmentation de la première colonne et augmentation uniforme) pour le cas de calcul de la borne de stabilit'e forte.

4.1 Préliminaires et notations

L'outil principal utilis'e dans notre travail est la norme v not'ee .k_õ, o`u v est un vecteur dont les 'el'ements v(s) > 1 pour tout s ? S (S est l'espace des 'etats de la chaàýne de Markov) et pour tout w ? R^S on a par d'efinition:

kwkõ = sup i?S

w(i) v(i) .

Soit ,t une mesure de probabilit'e dans S, alors la norme v de ,t est d'efinie comme suit:

Calcul de la borne de stabilit'e forte pour le cas de troncature de la capacit'e d'attente de la file M/M/1 Page 48

X kukõ = i?S

v(i)ui.

La norme v est 'elargie aux noyaux de transition dans S. Dans ce cas, soit A ? R^S×S alors :

MAIõ = sup i,kwk=1	PS j=1	|A(i,j)w(j)|
		v(i) .

Supposons que ^-7 et 7 possedent une norme v finie, alors

|e7f - 7f| = ke7 - 7kõkfkõ inf i?S

v(i).

4.1.1 Borne de la stabilit'e forte

Le critere de stabilit'e forte est donn'ee dans le th'eoreme suivant.

Th'eor`eme 4.1 (Aissani et Kartashov 1983 [3]) :

Soit X une chaine de Markov de noyau de transition P et de mesure invariante 7, cette chaine est dite v - fortement stable par rapport a` la norme 11 · k_v, si elle existe une mesure invariante ó et une fonction mesurable non n'egative h sur N, satisfaisant les conditions suivantes :

a) 7h > 0, ó1I = 1, óh > 0, et

b) T = P - h ? ó est non n'egatif,

c) ||T||_v < 1,

d) 1P1_v < 8.

O`u ? repr'esente le produit de la convolution entre la mesure ó et la fonction h et 1I est un vecteur dont tout les 'el'ements sont 'egaux a` 1.

Ce r'esultat nous permet de d'elimiter le domaine des valeurs de perturbation de la norme v (]1, â0]) pour lequel la chaine de Markov en question est v-fortement stable.

La borne de la m'ethode de stabilit'e est donn'ee dans le th'eoreme suivant.

Th'eor`eme 4.2 ([31]) :

Soit P un noyau de transition v - fortement stable si :

|| Pe -P|| 1 - 11T11_õ

õ < ||I

- Ð||õ, (4.1)

alors la borne de la stabilit'e forte peut s''ecrire sous la forme suivante :

||e7 -- Ð||_v || 7||_õ = Dr||õ ||I

P^e- P||_õ

(4.2)

P- P||_õ^.

1 - kT k_õ - ||I - Ð||_õ ||

En g'en'eral, la constante ||I - Ð||_õ est estim'ee par 1 + 171_õ.

4.2 Troncature de la capacitéd'attente de la file M/M/1

Dans cette section, nous introduisons les résultats théoriques obtenus lors de l'étude de la stabilitéforte de la chaàýne de Markov dans un système de files d'attente M/M/1 après la troncature de la capacitéde la file d'attente par les deux techniques : augmentation de la première colonne et augmentation uniforme.

4.2.1 Description du modèle et position du problème

Considérons un système de files d'attente M/M/1, le flux des arrivées est poissonnien de paramètre A, et le temps de service est une variable aléatoire suivant une loi exponentielle de paramètre u.

Notons par Q = A/u la charge (ou l'intensitédu trafic) de ce système

Le noyau de transition Pe = (^fPij)i,j>0 associéau modèle d'attente M/M/1 est défini comme suit :

^ePij =

? ??? ???

a, si i = j = 0; a, si j = i + 1; a, si j = i - 1,i > 0; 0, ailleurs,

o`u a = A/(A + u) et a = (1 - a) = u/(A + u).

On a, Pe = (^fPij)i,j>0, une matrice stochastique infinie, irréductible et récurrente positive, elle admet donc une distribution stationnaire unique eð = (eð(j))j>0.

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

a

0

0

Pe =

a

a 0 a 0

0 a 0 a 0

0 0 a 0 .. . 0

0 0 a .. . a

.. 0 . 0 a

.. . a 0 a

.. 0 ... ... ... . ... 0 a 0 .

.... 0 ... ... ... ... 0 a ..

··· · · · ? · · · · · · · · · . · · · · · · ··· ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ..

Considérons »le Coin Nord-Ouest» T d'ordre N de la matrice ^Pe , TN = (Tij)i,j>0 donnécomme suit :

Tij =

^ePij,si 0 = i = N ; 0 = j = N.

.

a ? a 0 0 ? ? ? ? ? ? ? ? ? ? Tij =

a 0 a 0

0 a 0 a 0

0 0 a 0 ... 0

0 0 a ... a

0 ... 0 a

? ?????????? ... a 0

D'après l'irréductibilitéde la matrice de transition du système M/M/1,

si on considère leur Coin-Nord-Ouest, il existe au moins une ligne i pour laquelle PN j=1 T(i, j) < 0, alors la matrice tronquée TN n'est pas stochastique.

Afin de rendre T stochastique, on construit une nouvelle matrice stochastique (P(i, j))N=i,j=0 vérifiant P = T c'est a` dire P(i,j) > P^e (i,j) pour 0 = i,j = N. Cela peut se faire en utili-

sant plusieurs technique.

La masse perdue dans chaque ligne est estimée par _>k>N P(i, k). On pose pour 0 = i, j = N,

P(i,j) = Pe (i, j) + A_n(i, j) _>1 P(i, k),

k>N

avec A est une matrice stochastique quelconque, qu'on construit par des techniques d'augmentation linéaire, déjàmentionnées précédemment. En effet, on s'intéressera juste aux techniques suivantes : Augmentation de la première colonne et augmentation uniforme.

4.3 L'augmentation de la premi`ere colonne

Dans ce cas, la matrice stochastique A est donnée sous la forme suivante :

Calcul de la borne de stabilitéforte pour le cas de troncature de la ^capacité

d'attente de la file M/M/1											Page 51
1 ? 1 1 1 A = ? ? ? ? ? ? ? ? ? ? ? ? 1 1 1 1 et la matrice P devient : á ? á 0 P= ? ? ? ? ? ? ? ? ? ? á			0 0 0 0 ... ... 0 0 á 0 á 0 0	0 0 0 0 ... ... 0 0 0 á 0 á 0 0	0 0 0 0 ... ... 0 0 0 0 á 0 ... 0 0	··· ··· ··· ··· ... ... 0 0	0 0 á ... á 0	··· ··· ··· ··· ... ... 0 0	... 0 0 á	0 0 0 0 0 0 0 0	0 0 ? 0 0 0 , 0 0 ? ? ? ? ? ? ? ? ? ? ? ? 0 ? , ?????????? ... á 0
Pij =	? ? ?	^ePij, si 0 = i = N - 1 ; 0 = j = N; á, si j = N - 1 ; i = N; á, si j = 0 i = N.

4.3.1 Calcul de la borne de stabilitéforte :Augmentation de la premi`ere colonne

v- Stabilitéforte de la chaàýne de Markov X

Pour prouver la v- Stabilitéforte de la chaàýne de Markov X pour une fonction test v(k) = â^k pour â > 1, il est suffisant de trouver une mesure ó, et une fonction mesurable h sur N tels que :

a) ðh > 0, ó1I = 1, óh > 0,

b) Tij = Pij - óihi, est non négatif,

Calcul de la borne de stabilit'e forte pour le cas de troncature de la capacit'e d'attente de la file M/M/1 Page 52

c) ?ñ < 1 tel que Tõ(k) = ñõ(k), pour k ? {0,1, ..., N},

d) 1P1_õ < 8.

Pour notre cas, on choisit :

· õ(k) = â^k , â > 1 avec k ? N.

· h(i) = Pi0 :

~ 1, si i = 0;

h(i) = 1Ii=0= 0, sinon.

· ój = P0j :

ój = P0j =

? ? ?

á, si j = 0; á, si j = 1; 0, sinon.

V'erifions maintenant les conditions a), b), c) et d) :

Condition a) ðh = ð0 > 0,

ðh = ð0 = (1 - 0)/(1 - Q^N+1) > 0. (4.3)

· ó1I = á + á + 0 = 1, o`u 1I est le vecteur unit'e,

· óh = á + (0 × á) + 0 = á > 0.

Condition b) V'erifions que le noyau T est non n'egatif, on a :

T = P - h ? ó, ie T = P - {1^ereligne}

~ P0j - ój = P0j - P0j = 0, si i = 0; Tij = Pij - h(i)ój = Pij - 0 × ój = Pij, sinon,

Donc, T est un noyau non-n'egatif, ?i, j = 0 : Tij = 0.

Condition c) Montrons l'existence d'une certaine constante ñ < 1 telle que : Tõ(k) = ñõ(k), pour k = 0.

Par d'efinition,

Tõ(k) =

XN j=0

õ(j)Tkj.

Calcul de la borne de stabilit'e forte pour le cas de troncature de la capacit'e d'attente de la file M/M/1 Page 53

En effet, on a :

Pour k=0 : (Tv)(0) = Pour 1 = k = N - 1 :		XN j=0	v(j)T0j =	XN j=0	âj × 0 = 0.
(Tv)(k) =	XN j=0	v(j)Pkj = á v(k - 1) + á v(k + 1)

= á â^k-1 + á âk+1
âk{á + áâ}

= ñ1(â) v(k),

Posons

ñ1 (â) á = _â+ áâ. (4.4)

(Tv)(N) =

XN j=0

â^jPNj = v(0)PN,0 + v(N)PN,N-1

= áâ⁰ + _â^áâ^N = á + â^N{_â}

N{ á + á
_â}

âN â

= ñ2(â)v(k),

Posons

ñ2(â) = á âN + _â^á. (4.5)

On a,

á á á

ñ1(â) - ñ2(â) = _â+ áâ -

âN -

á

â

= áâ - > 0

âN

Donc, 0 < ñ2(â) < ñ1(â).

Calcul de la borne de stabilit'e forte pour le cas de troncature de la capacit'e d'attente de la file M/M/1 Page 54

Alors, il suffit de prendre ñ(â) = ñ1(â) = max{ñ1(â), ñ2(â)} verifiant :

(Tv)(k) = ñ1(â) × v(k).

Il nous reste a` demontrer que,

ñ1(â) = á â + áâ < 1,

Pour tout â > 1,

2

ñ1(â) u ëâ 1 + 0

(ë + u)â (ë + u) (1 + e)â, (4.6)

Si on suppose que pâ < 1 ? (ë/u)â < 1. Alors :

ñ(â) < 1,

En effet, on a :

1 + Qâ²

ñ(â) = (1 + Q)â^.

Pour que ñ(â) < 1 , il faut que,

(1 + 0â²) < ((1 + p)â) 1 + %â² -- â -- âp < 1

(1 -- â) + (âp(â -- 1)) < 0

(âp(â -- 1)) < (â -- 1)

âp < 1.

D'o`u, ñ(â) < 1.

Condition d) Verifions que 11P11_v < cc .

T = P -- h ? ó P = T + h ? ó

11P11_v = 11T + h ? ó11_v

= 11T 11_v + 11h11_v11ó11_v.

Par definition, on a,

11T11v = sup 0<i<N		1	XN j=0	õ(j) | Tij |
		õ(i)
= sup 0<i<N	1 õ(i)^ñõ(i)

= ñ(â) < 1.

Calcul de la borne de stabilit'e forte pour le cas de troncature de la capacit'e d'attente de la file M/M/1 Page 55

et

Ihl_v = sup õ(i)|hi| = 1,

0<i<N

1ó1v =

XN j=0

õ(j)|ój| =

XN j=0

â^jP0j

= õ(0)ó0 + õ(1)ó1 + 0 = á + áâ

= á + áâ0 < 8,

avec : â0 = sup{â : ñ(â) < 1}

Donc, 1P1_v < 8.

Ainsi, toutes les conditions sont vérifiées.

In'egalit'es de stabilit'e forte

Estimation de la d'eviation du noyau de transition

Pour pouvoir estimer numériquement l'écart entre les distributions stationnaires des états des chaines de Markov (^fX_n), (X_n), estimons au préalable la norme de déviation du noyau de transition P de la chaine de Markov de système M/M/1/8 par rapport au noyau de transition P associéa` la chaine de Markov du système M/M/1/N (modèle tronqué).

L'estimation de 1 P^e - P1_v est énoncée par le lemme suivant

Lemme 4.1 : Si p < 1 , pâ < 1 et 1 < â < â0. Alors,

1 P^e - P1_v = Ä(â) = (1â+ _N e) . (4.7)

Preuve

Par définition, on a :

e MP - PMv = sup 0<k<N		1		XN j=0		v(j)|		Pkj- - Pkj|.
		v(k)
Pour 0 = k < N - 1 : Ä0(â) = sup 0<k<N-1	1		XN j=0		v(j)|		Pkj- - Pkj| = 0.
	v(k)

Calcul de la borne de stabilit'e forte pour le cas de troncature de la capacit'e d'attente de la file M/M/1 Page 56

Pour k = N :

1 Ä1(â) = v(N)

XN j=0

v(j)|

PNj - PNj|

âN {v(0)| 1³N0 - PN0| - 1)| 1³NN-1 - PNN-1|}

1

= âN {á + 0}

á

=

âN .

On a : Ä1(â) > Ä0(â),

1 P^e - P1_v = max{Ä0(â),Ä1(â)},

Donc ;

IIP - PM_v = Ä1(â) = á âN = (1 âN A + = (â). (4.8)

D'etermination de l'erreur due a` la troncature

L'estimation de la déviation des distributions stationnaires est donn'ee par le théoreme suivant

Th'eor`eme 4.3 Soient ^-ð et ð les distributions stationnaires des chaines de Markov décrivant respectivement les états des systemes d'attente M/M/1 et M/M/1/N. Supposons que les hypotheses du Lemme 4.1 soient vérifiées. Alors, pour tout Q < 1, et sous la condition :

Ä(â) < 1 - ñ(â)

c(â) ,

nous avons l'estimation de la borne de la stabilitédans ce cas est donn'ee par :

c0(â)c(â)Ä(â)

|if - ð||_v = = Be1.

1 - ñ(â) - Ä(â)c(â)

o`u Ä(â) est défini en (4.8) et ñ(â) en (4.7) et

â(1 - 0)(1 + â0

(4.9)

c0(â) = (â - 1)(1 - Q^N+¹)(1 -

â(1 - 0(1 + â0

c(â) = 1 + (â - 1)(1 - %^N+¹)(1 - â%). (4.10)

1

Calcul de la borne de stabilit'e forte pour le cas de troncature de la capacit'e d'attente de la file M/M/1 Page 57

Preuve

Afin de d'emontrer ce r'esultat, il suffit d'estimer ||ð||_v, et ||1I||_v , o`u 1I est la fonction identiquement 'egale a` l'unit'e.

Supposons que âp < 1 , alors la norme de la distribution stationnaire peut àetre estim'ee par la formule qu est donn'ee par :

(óõ)(ðh)(óõ)(ð0)

|_v = (4.11)

1 - ñ(â) 1 - ñ(â)^.

o`u ð0 est celle obtenue pour la file d'attente M/M/1/N tronqu'ee qui est donn'ee par :

(1 - p)

ð0 = (4.12)

(1 - Q^N+¹)^.

Donc, on obtient :	á + áâ ||ð||v = 1 - (1+â2% (1+%) )		(1 - p) (1 - QN+1) (4.13)
=		â(1 - %)(1 + â%)		= c0(â). (4.14)
		(â - 1)(1 - e^N+^1)(1 - â%)

Par d'efinition, on a :

||1||_v = sup

0<k<N

âk = 1.

Donc, nous avons

c(â) = 1 + â(1 - e)(1 + âp)

(â - 1)(1 - e^N+¹)(1 - â%)^.

Ainsi, pour tout Ä(â) < ¹V⁾, nous obtenons :

c

||if - ð||_v = 0(â)c(â)Ä(â)

=

1 - ñ(â) - Ä(â)c(â) Be1.

4.4 L'augmentation uniforme

Dans ce cas, on choisit la matrice stochastiques A de telle sorte que tous ses 'el'ements sont 'egaux a` 1/N. Ainsi, la matrice P sera obtenue sous la forme :

Calcul de la borne de stabilitéforte pour le cas de troncature de la ^capacité

d'attente de la file M/M/1							Page 58
a ? a 0 P= 0 ?????????? á N	a 0 a 0 á N	0 a 0 a 0 á N	0 0 a 0 ... 0 á N	0 0 a ... a á N	0 ... . 0 a + á N	.. a á N	? ??????????

Explicitement P s''ecrire :

? ?

?

Pij =

^ePij, si 0 = i = N - 1; 0 = j = N;

N ,

á si i = N; 0 = j = N;

a+ 1 N , sii=N; j=N-1.

4.4.1 Calcul de la borne de stabilitéforte : Augmentation uniforme

õ-Stabilitéforte de la chaàýne de Markov X

De même, en suivant la même d'emarches, que celle du cas pr'ec'edent (augmentation de la premi`ere colonne), et pour le même choix de la fonction test õ, et de la fonction h et de la mesure ó, on constate que la v'erification des conditions a), b) et d) est la même. Donc, a` ce niveau on mentionnera que les 'etapes diff'erentes du cas pr'ec'edent. Ainsi :

· Montrons l'existence d'une certaine constante ñ < 1 telle que :

Tõ(k) = ñõ(k), pour k = 0?

Par d'efinition,

Tõ(k) = _XN õ(j)Tkj.

j=0

Pour k = 0 :

(Tv)(0) = _XN v(j)T0j = _XN âj × 0 = 0.

j=0 j=0

Calcul de la borne de stabilit'e forte pour le cas de troncature de la capacit'e d'attente de la file M/M/1 Page 59

Pour 1 = k = N - 1 :

(Tv)(k) =

XN j=0

v(j)Pkj = á v(k - 1) + á v(k + 1)

= á â^k-1 + á âk+1
âk{á + áâ}

= ñ1(â) v(k),

Posons alors,

á

ñ1(â) = _â+ áâ. (4.15)

Pour k = N :

(Tv)(N) =

XN j=0

â^jPNj

= v(0)PN,0 + v(1)PN,1 + v(2)PN,2 + v(3)PN,3 + ... + v(N - 1)PN,N-1 + v(N)PN,0, = â^{0 á}_N+ â^1á_N + â^2á_N + ... +â^N-1(á + á N ) +â^Ná_N,

âN á [1 1 1 á

N âN + _âN-1 +...+_â +1 + _â,

â^Ná

=

N

" â,;,'+11

â

= ñ2(â)v(N), De même, posons :

1 - (¹)^N+1

ñ2(â) = N 1 - 1+ âN+1.

{â

á

á â

1 á

ñ2(â) = 1 âá

[N(â - 1) (1 - _âN+1 ) + âN+1. (4.16)

Dans ce cas, nous constatons que : 0 < ñ2(â) < ñ1(â).

Donc, il existe une constante ñ(â) = ñ1(â) = max{ñ1(â),ñ2(â)} v'erifiant

(Tv)(k) = ñ1(â) × v(k).

Calcul de la borne de stabilit'e forte pour le cas de troncature de la capacit'e d'attente de la file M/M/1 Page 60

Nous avons dejàdemontreque si, pâ < 1 et pour tout â > 1, On a

ñ(â) = á â + áâ < 1. (4.17)

In'egalit'es de stabilit'e forte

Estimation de la d'eviation de noyau de transition Lemme 4.2 Si p < 1 et 0â < 1 et 1 < â < â0, alors

11/3- = A(â) = NâN-1(â (1 - a +

-- 1) \ fiN ^1). (4.18)

Preuve Par definition, on a : II		Pe - P1v = sup 0=k=N			1 v(k) Lv(j)| ^13kj - j=0
Pour 0 = k < N - 1 : A0(â) = sup 0=k=N-1 Pour k = N :						1	XN j=0	v(j)|	^-Pkj - Pkj| = 0.
						v(k)
1 A1(â) = v(N)	XN j=0		1 - v (j)|-13NjPNj|= âN (0)|PN0 - PN0| + v(N) + |^ePN1 - PN1|
+ v(N) + ... + |				^ePNN-1 - PNN-1| + v(N) + |						^ePNN - PNN|}

1{ á á á

= â^NN N ... + N

1 - (¹_â)^N+1

1 - ¹

â

=

+

á

âN+1

~ ~

á 1 - 1

= .

Nâ^N-1(â - 1) âN+1

On a : Ä1(â) > Ä0(â), donc;

k P^e - P k_v = max{Ä0(â), Ä1(â)}

( )

á

k P^e - P M_v = Ä1(â) = 1 - 1 = Ä(â). (4.19)

Nâ^N-1(â - 1) âN+1

.

Détermination de l'erreur due a` la troncature

L'estimation de la déviation des distributions stationnaires est donnée par le théoreme suivant

Théorème 4.4 Supposons que les hypotheses de Lemme 4.2 soient vérifiées. Alors, pour tout < 1, et sous la condition:

1 - ñ(â)

Ä(â) < c(â) ,

nous avons l'estimation de la borne de la stabilitédonnée par:

||eð - ð||_v = c0(â)c(â)Ä(â)

1 - ñ(â) - Ä(â)c(â) = Be2.

o`u Ä(â) est défini en (4.19) et ñ(â) en (4.15) et

â(1 - %)(1 + â%)

c0(â) = (â - 1)(1 - %^N+¹)(1 - â%), (4.20)

c(â) = 1 + â(1 - %)(1 + â%)

(â - 1)(1 - Q^N+¹)(1 - âQ). (4.21)

Preuve

Dans ce cas, la seule différence de la nouvelle borne due a` la même perturbation réside dans la constante qui estime la déviation entre les deux matrices de probabilités de transition.

4.4.2 Calcul de la borne reelle

La définition suivante nous permet de déterminer l'écart entre les distributions stationnaires des états des chaàýnes de Markov.

Supposons que < 1. Alors

k eðk - ðkMõ = ÓN k=0âk| eðk - ðk|,

O`u

eðk =

1 - %

1 - %N+1 ñ^k. (4.22)

avec = ë/u.

4.4.3 Bornes de deviation du nombre moyen de clients

La déviation du nombre moyen de clients pour les différentes perturbations est donnée comme suit : Si on choisit la fonction caractéristique f(s) = s (fonction identique), alors l'estimation de l'erreur due a` la troncature de la capacitéd'attente du système M/M/1 est définie par:

|ðf - eðf| = |eði - ði|_õ.kfk_õ, (4.23)

o`u

kfk_õ = ln(â) × â-[ 1

1 ln(6) ]. (4.24)

4.5 Conclusion

Dans ce chapitre, on a calculéla borne de la méthode de stabilitéforte dans le cas de la troncature de l'espace des états de la chaàýne de Markov décrivant la file d'attente M/M/1. Cette borne de perturbation est calculée de deux manières différentes : augmentation de la première colonne et augmentation uniforme. Ainsi, en considérant ces deux techniques, on peut comparer les deux bornes obtenues.

Dans le chapitre prochain, on considérera quelques exemples numériques afin de comparer ces bornes de perturbation.

5

Comparaison des techniques de troncature

Dans le chapitre pr'ec'edent, nous nous sommes int'eress'es a` l''etude th'eorique de la stabilit'e forte dans un système de files d'attente M/M/1 o`u on a consid'er'e deux techniques de troncature. Nous avons pu exhiber les conditions suffisantes de la stabilit'e forte li'ees au système. Dans ce chapitre, nous nous int'eresserons a` l'aspect pratique du problème. Pour ce faire, nous avons 'elabor'e un algorithme qui permet d'estimer les deux bornes de perturbation obtenues dans le chapitre pr'ec'edent, et de v'erifier les conditions ainsi que la d'etermination de leurs domaine de stabilit'e optimal. Enfin, une comparaison entre les deux bornes obtenues et la borne r'eelle sera effectu'ee.

5.1 Applications numériques

Dans cette section, nous pr'esentons quelques r'esultats num'eriques qu'on obtient par application de l'algorithme de stabilit'e forte, sous l'environnement Matlab et ce tout en consid'erant les deux techniques de troncature de l'espace des 'etats de la chaàýne de Markov d'ecrivant la file d'attente M/M/1.

5.1.1 Environnement MATLAB

Notre choix s'est port'e sur l'utilisation de l'environnement MATLAB qui nous permet, gràace a` la richesse de sa bibliothèque math'ematique, d'optimiser les instructions dans les programmes r'ealis'es dans le cadre de ce travail. En effet, MATLAB est un système interactif et convivial de calcul num'erique et de visualisation graphique destin'e aux ing'enieurs et

scientifiques qui possède un langage de programmation a` la fois puissant et simple. De plus, il intègre des fonctions d'analyse numérique, de calcul matriciel, etc.

5.1.2 Approche algorithmique

Nous avons élaboréun algorithme qui permet d'estimer les deux bornes de perturbation présentées précédemment, et de vérifier les conditions, ainsi que la détermination de leur domaine de stabilitéoptimal.

5.1.3 Algorithme de StabilitéForte

'ETAPE 1

- Introduire le nombre de troncature N;

- Introduire le taux d'arrivées A;

- Introduire le taux de service u ;

- Introduire le pas h.

'ETAPE 2

- Déterminer 30, en construisant un intervalle I1 = [1 + h, 30], o`u 30 est le réel 3 > 1 vérifiant la condition p(3) < 1.

- Déterminer un sous intervalle I2 = [3min, 3max] ? I1, pour lequel Ä < 1-ñ(â)

c(â) soit vérifiée

'ETAPE 3

- Déterminer une valeur optimale de 3 noté3opt ? I2 qui minimise la valeur de l'erreur.

'ETAPE 4 - Fin.

5.1.4 Organigramme de stabilitéforte

Les différentes étapes de notre algorithme peuvent être présentées dans un organigramme suivant :

FIGURE 5.1 - Organigramme de l'algorithme

Comparaison des résultats et discussion

* Afin de comparer les résultats obtenus des deux bornes de stabilitéforte par les deux techniques de troncature, nous implémentons l'algorithme pour les différentes valeurs du niveau de la troncature pour laquelle une valeur optimale _âopt sera calculée.

* La même valeur de _âopt sera considérée afin de comparer ces deux techniques de troncature et d'évaluer la borne réelle.

* Nous avons implémenténotre algorithme pour une valeur de la charge de système = 0.25 et l'exécution de cet algorithme avec un pas h = 0.01 nous permet d'obtenir les résultats représentés dans des tableaux suivants :

5.1.5 Variation de l'erreur en fonction de %

D'après les résultats obtenus, nous pouvons constater le domaine de stabilitéliéau différentes valeurs de , la borne _âmax atteint son maximum ensuite elle diminue progressivement lorsque le paramètre prend de petites valeurs comme le montre le tableau suivant (par exemple pour N = 15).

Q	âmin	âmax	âopt	SSBP	SSBU
0.1	1.0100	9.9900	8.3273	1.4477e - 012	1.0968e - 013
0.25	1.0100	3.9900	3.3602	4.6188e - 006	4.3839e - 007
0.4	1.0100	2.4900	2.1268	0.0130	0.0016
0.5	1.0100	1.9800	1.7242	0.6987	0.1070
0.6	-	-	-	-	-

TABLE 5.1 - Tableau des variations de l'erreur en fonction de Q

C'est pour cela que notre choix se portera sur la valeur Q = 0.25 et N > 4 pour la suite de l'application, et le graphe suivant illustre qu'àl'augmentation de Q, l'erreur augmente et elle tend vers l'infinie a` partir de Q > 0.6.

FIGURE 5.2 - Graphe des erreurs Be1 et Be2 : en fonction de Q

5.1.6 Variation de l'erreur en fonction de N

Approximation de la d'eviation des distributions stationnaires et l'approximation du nombre moyen de clients dans le système

1er Cas : Augmentation de la premi`ere colonne :

L'implémentation de l'algorithme dans ce cas permet d'obtenir les résultats pour la technique d'augmentation de la premi`ere colonne représentés dans le tableau suivant :

% = 0.25	\	||eð -ð||v		|eðf - ðf|
N	âopt	SSBP	Re'el	SSBP	Re'el
5	2.7134	0.3974	0.2711	0.1465	0.0999
6	2.8189	0.1381	0.1994	0.0490	0.0708
7	2.9144	0.0475	0.1669	0.0163	0.0574
8	2.9983	0.0160	0.1472	0.0054	0.0493
9	3.0716	0.0053	0.1335	0.0017	0.0438
10	3.1356	0.0017	0.1209	0.0005	0.0389
11	3.1918	5.3593e-004	0.1112	0.0002	0.0352
12	3.2415	1.6658e-004	0.0988	0.0001	0.0309
13	3.2855	5.1037e-005	0.0901	0.0000	0.0279
14	3.3249	1.5440e-005	0.0755	0.0000	0.0231
15	3.3602	4.6188e-006	0.0672	0.0000	0.0204
16	3.3921	1.3680e-006	0.0510	0.0000	0.0154
17	3.4210	4.0155e-007	0.0437	0.0000	0.0131
18	3.4473	1.1692e-007	0.0284	0.0000	0.0084
19	3.4714	3.3796e-008	0.0233	0.0000	0.0069
20	3.4935	9.7044e-009	0.0120	0.0000	0.0035
21	3.5138	2.7697e-009	0.0094	0.0000	0.0028
22	3.5326	7.8610e-010	0.0034	0.0000	0.0010
23	3.5500	2.2197e-010	0.0025	0.0000	0.0007
24	3.5661	6.2384e-011	4.7730e-004	0.0000	0.0001
25	3.5812	1.7456e-011	3.3040e-004	0.0000	0.0001
26	3.5952	4.8648e-012	0	0.0000	0
27	3.6084	1.3506e-012	0	0.0000	0
28	3.6207	3.7366e-013	0	0.0000	0
29	3.6323	1.0303e-013	0	0.0000	0
30	3.6431	2.8324e-014	0	0.0000	0

TABLE 5.2 - Tableau des erreurs Be1 : l'augmentation de la premi`ere colonne

Même remarque que celle de la variation de , mais dans ce cas c'est le contraire. Le fait que l'augmentation de la valeur du N induit une diminution de l'erreur commise comme le montre le tableau ci-dessus.

Ceci est illustr'e par le graphe suivant :

FIGURE 5.3 - Graphe des erreurs Be1 : avec l'augmentation de la premi`ere colonne

Pour l'approximation du nombre moyen de clients dans le système

On peut s'int'eresser a` des caract'eristiques pr'ecises, dans le but d'avoir une id'ee sur la pr'ecision des r'esultats. Dans cette partie, nous nous int'eressons au nombre moyen de clients dans le syst`eme. Les r'esultats obtenus sont ainsi repr'esent'es dans le tableau pr'ec`edent. Et ceci peut être illustr'e par le graphe suivant :

FIGURE 5.4 - Graphe de variation du nombre moyen de clients en fonction de N

On voit que le nombre moyen de clients dans le système original (tronqué) est inférieur a` celui du système étudiéM/M/1/N (idéal) pour N < 9. De plus, l'augmentation du N induit une diminution de l'erreur sur le nombre moyen de clients a` partir de N > 12 et pour âopt ? [3.2855, 3.6431] le nombre de clients dans le système est nul.

2er Cas Augmentation uniforme :

Même comportement que le premier cas, mais il y a une amélioration de la valeur de l'erreur obtenue par la technique d'augmentation uniforme et les résultats sont donnés dans le tableau suivant :

% = 0.25	\	||eð -ð||v		|eðf - ðf|
N	âopt	SSBU	Re'el	SSBU	Re'el
5	2.7134	0.1203	0.2711	0.0443	0.0999
6	2.8189	0.0351	0.1994	0.0125	0.0708
7	2.9144	0.0103	0.1669	0.0035	0.0574
8	2.9983	0.0030	0.1472	0.0010	0.0493
9	3.0716	8.6730e-004	0.0003	0.0003	0.0438
10	3.1356	2.4898e-004	0.1209	0.0001	0.0389
11	3.1918	7.0947e-005	0.1112	0.0000	0.0352
12	3.2415	2.0075e-005	0.0988	0.0000	0.0309
13	3.2855	5.6437e-006	0.0901	0.0000	0.0279
14	3.3249	1.5772e-006	0.0755	0.0000	0.0231
15	3.3602	4.3839e-007	0.0672	0.0000	0.0204
16	3.3921	1.2124e-007	0.0510	0.0000	0.0154
17	3.4210	3.3377e-008	0.0437	0.0000	0.0131
18	3.4473	9.1497e-009	0.0284	0.0000	0.0084
19	3.4714	2.4985e-009	0.0233	0.0000	0.0069
20	3.4935	6.7981e-010	0.0120	0.0000	0.0035
21	3.5138	1.8436e-010	0.0094	0.0000	0.0028
22	3.5326	4.9840e-011	0.0034	0.0000	0.0010
23	3.5500	1.3436e-011	0.0025	0.0000	0.0007
24	3.5661	3.6123e-012	4.7730e-004	0.0000	0.0001
25	3.5812	9.6876e-013	4.7730e-004	0.0000	0.0001
26	3.5952	2.5920e-013	0	0.0000	0
27	3.6084	6.9201e-014	0	0.0000	0
28	3.6207	1.8437e-014	0	0.0000	0
29	3.6323	4.9026e-015	0	0.0000	0
30	3.6431	1.3013e-015	0	0.0000	0

TABLE 5.3 - Tableau des erreurs Be2 : Augmentation uniforme

Ceci est illustrepar le graphe suivant :

FIGURE 5.5 - Graphe des erreurs Be2 : l'augmentation uniforme

Pour l'approximation de l'erreur sur le nombre moyen de clients dans le système

On voit bien que l'erreur sur le nombre moyen de client dans le système ideal est inferieur a` celui du nombre moyen de clients dans le système reel pour N < 10, et a` partir de N > 10, le nombre est nul.

FIGURE 5.6 - Graphe de variation de l'erreur sur le nombre moyen de clients en fonction de N

Interprétation des résultats

L'application numérique de la technique de troncature sur la capacitéde la file d'attente, nous a permis d'observer le comportement de l'erreur relative aux deux bornes obtenues par les deux techniques de troncature. Il est alors aiséde constater d'apres ces deux approches que la borne obtenue par l'augmentation uniforme est meilleure par rapport a` celle obtenue par l'augmentation de la premiere colonne.

FIGURE 5.7 - Graphe comparatif des erreurs Be1 et Be2

D'après ce graphe, nous pouvons constater que l'erreur obtenue par l'augmentation uniforme est plus petite que celle de l'augmentation de la première colonne, et celle de l'erreur réelle, et a` partir de N = 26 toutes les erreurs sont nulles, ce qui signifie que les deux modèles (originale et tronqué) coincident.

Pour l'approximation de l'erreur sur le nombre moyen de clients dans le système

FIGURE 5.8 - Graphe comparatif de variation de l'erreur sur le nombre moyen de clients en fonction de N

3	SSBP	SSBU
2	0.9344	0.3268
2.3	0.5205	0.1712
2.7	0.3975	0.1206
2.7134	0.3974	0.1203
2.769	0.3994	0.1197
2.9	0.4209	0.1232

TABLE 5.4 - Tableau des variations de l'erreur en fonction de 3

5.1.7 Variation de l'erreur en fonction 3

Pour N = 5 et = 0.25, on a

L'erreur sur la distribution stationnaire par augmentation uniforme SSBU qui est obtenue pour 3opt = 2.7690 est SSBU = 0.1197, et l'erreur obtenue pour 3opt = 2.7134 par augmentation de la première colonne est SSBP = 0.3974.

Donc, d'après ce tableau, on peut bien comparer les résultats obtenus par les deux techniques par la variation de 3. Ainsi, l'erreur obtenue par la technique d'augmentation uniforme est plus petite que celle obtenue par l'augmentation de la première colonne. Alors ,la croissance de 3 entraàýne une diminution de l'erreur.

5.2 Conclusion

Après l'étude théorique de l'applicabilitéde la méthode de stabilitéforte dans le système M/M/1/N, dans ce chapitre, nous avons pu réaliser une application numérique dans le cas de la troncature de la capacitéde la file d'attente de ce système, tout en exploitant les résultats présentés dans le quatrième chapitre.

Le but de cette troncature est d'analyser la qualitédes bornes de stabilitéforte via les deux techniques, et cela ce réalise quand la charge de système < 1. On remarque dans tous les cas que la perturbation effectuée sur les paramètres introduits, les erreurs obtenues par la technique d'augmentation uniforme est meilleure que celle d'augmentation de la première colonne et ces erreurs obtenues par les deux techniques tendent vers zero quand N tend vers l'infini.

On remarque ainsi, dans le cas o`u la charge de système est proche de 1, que la condition d'optimalitén'est pas vérifiée et on conclut que le système devient instable d'o`u l'inutilitéde l'application de la méthode stabilitéforte a` ce niveau.

Conclusion générale

L

'objectif de ce travail est de montrer l'utilitédes techniques de la troncature dans la théorie des files d'attente et d'élargir le champs d'applicabilitéde ces techniques au cas de certains systèmes de files d'attente.

L'étude des phénomènes réels est de plus en plus complexe. Plusieurs chercheurs ont développédes méthodes d'approximation pour l'analyse des systèmes complexes. Parmi les principales approches, on rencontre celle de la méthode de stabilitéforte, que nous avons appliquédans notre cas au problème d'estimation de l'erreur de la troncature de l'espace d'états de la chaàýne de Markov décrivant l'état de la file d'attente M/M/1.

Dans ce travail, nous nous sommes intéressés a` la comparaison des techniques de troncature, tout en utilisant la méthode de stabilitéforte. Nous nous sommes servis d'une approche algorithmique et numérique afin de comparer ces techniques de troncature sur la cas de la file d'attente M/M/1. Dans un premier temps, nous avons synthétiséles différents résultats obtenus sur les chaàýnes de Markov tronqués. Puis, nous nous somme tardes sur la présentation de quelques techniques de troncature, les plus utilisées en littérature, ainsi que quelques concepts de base de la méthode de stabilitéforte. En deuxième temps, nous nous sommes intéressés a` l'applicabilitéde la méthode de stabilitéforte dans le cas o`u nous avons considéréles deux techniques de la troncature : augmentation de la premiere colonne et augmentation uniforme. Enfin, nous avons implémentéun algorithme afin d'évaluer numériquement les estimations des erreurs induites par ces deux techniques de tronature, que nous avons comparéa` l'erreur réelle.

Ce travail ouvre plusieurs perspectives de recherche importantes, entre autres :

A Elargir le cas d'applicabilitéde ces techniques de troncature a` d'autres cas de modèles stochastiques, tels que les réseaux de files d'attente;

A Considération d'autres bornes de perturbation pour le cas des problèmes de la troncature, telle que la méthode de développement en séries de Taylor;

A Envisager des études comparatives appropriées a` ces bornes de perturturbation, tout en considérant d'autres techniques de la troncature telles que : la renormalisation, augmentation de le dernière colonne, . . .

A Comparaison des deux approches, stabilitéforte et celle de Van Dijk, sur le cas des réseaux de files d'attente.

Bibliographie

[1] Abbas, K., Heidergott. B., and A·ýssani, D. Series expansion and strong stabilite : a comparative analysis. Technical Report, Lamos Ed., 2009.

[2] Abbas, K., A·ýssani,D. and Aproximation in an M/G/1 queueing system with breakdowns and repairs. British, EWIC Review Ed.,Computer Society, 139-147, 2007.

[3] A·ýssani, D., Kartashov. N. Ergodicity and stability of Markov chain with respect to opertor topology in the space of transition kernels, 1983.

[4] Benaim, M. and El Karoui, N. Promenade Aléatoire Chaàýnes de Markov et Simulations; Martingales et Stratégies. Ecole Polytechnique.Ed, Palaiseau, 2007.

[5] Borovkov, A. Asymptotic Methode in Queuing theory, Springer Verlag, New York, 1976.

[6] Bouallouche, L. and A·ýssani, D. Estimation of the storing stability in an M/M/1 queueing systems. Proceedings of The XX International Seminar on Stability Problems for Stochastics Models, Dublin(Poland), 1999.

[7] Bouallouche, L. and A·ýssani, D. Measurment and performance of the storing stability method. Theory of Prob and Math.stat., 17, 1-9, 2005.

[8] Boxma, O., and Konheim, A. Approximate analysis of exponential queueing systems with blocking. Acta Inform, 15, 19-66, 1981.

bibitemcoa Cao, X. The maclaurin series for performance functions of Markov chains. Advanced in Applied Probability, 30, 676-692, 1998.

[9] Chabriac, H. 'Eléments de Théorie des Files D'attente. Supaero, Ed., Janvier 2008.

[10] Franccois, J.and Benjamin, D. Modèles Aléatoires Mathématiques et Applications, Springer,Ed., France 2006.

[11] Gibson, D.and Seneta, E. Augmented truncations of infinite stochastic matrices. Journal of Applied Probability , 24, 600-608, 1987.

[12] Glynn, P. and Meyn, S. Lyapounov,A. Bound for Solutions of Poisson's equation, Ann.probab.

[13] Gross, D.and Harris, C. Fundamentals of Queueng Theory. Wiley, New york 1985.

[14] Hamoudi, Z. Developpement en série et stabilitéforte du système M/M/1/N. Mémoire de Magister, UniversitéA.Mira, Bejaia, 2008.

[15] Hêche, J. Résumésur les les d'attente et les réseaux. Recherche Opérationnelle 2004.

[16] Hàeche, J.F., Liebling,T.M. and de Werra,D., Recherche Opérationnelle Pour Ingénieurs Il, Presses Polytechniques Et Universitaires Romandes, 2003.

[17] Heidergott,B., Hordjik, A., and Leder, N. Taylor series expansions for stationary Markov chains. Advances in Applied Probability, 29, 1046-1070, 2003.

[18] Heidergott,B., Hordijk,A. and Leder,N.. Series expansions for continuous-time Markov chains. Operations Research.

[19] Heidergott,B., Hordjik,A., and Uitert,M.V. serties expansions for finite-state markov chaàýnes. Vrije Universiteit Departement of Econometrics. Amsterdam 2006.

[20] Heyman, D. Approximating the stationary distribution of an infinite stochastic matrix. J. Appl. Probab., 28, 96-103, 1991.

[21] Heyman, D., and Whit, W. Limits of queues as the waiting room grows Questa 5, 381-392, 1989.

[22] Hillier, F., and Boling, R. Finite queues in series with exponential or Erlang service times a numerical approach. 15, 286-303, Oper.Res 1967.

[23] Hordijk, A., and Spieksma, F. M. A New Formula for the Deviation Matrix ,Chapter 36 in Probability, Statistics and Optimization. Wiley, 1994.

[24] Hordjk, A., and Van Dijk, N. Networks of Queues With Blocking In Peformance. North-Holland, Amsterdam, 1981.

[25] Ispen, C. and Meyer. Uniform Stability of Markov chains. SIAM J.Matrix anal. Appl 3, 15, 1061-1074, 1994.

[26] Jacod, J. Chaàýnes de Markov, Processus de Poisson et Applications. DEA de probabilités et applications, 2003-2004.

[27] Kalashnikov, V., and Rachev, S. Mathematical Methods For Construction of Queueing Models. Wadsworth and Brooks Cole, 1990.

[28] Kalashnikov, V. and Tsitsiashvili, G. On the stability of queueing systeme with respect to disturbances of their distribution functions. Queuing Theory and Reliability 211- 217, 1971.

[29] Kartashov, N. V. Criteria of uniform ergodicity and storing stability of markov chain with a common phase spase. Theor.Prob. and Math. Statist, 30 , 71-89, 1984 .

[30] Kartashov, N. V. Strongly stable Markov chains. VSP, Utrecht; Tbimc Scientificn Publisher 1986.

[31] Kartashov, N. V. Strongly stable Markov Chains. Stability problems for stochastic models. VNISS, Vsesayouzni Seminar on Stability Problems for Stochastic Models, Journal of Soviet Mat, 1986.

[32] Latouche,G. and Neuts,M.F. Effici·ent algorithmic solutions to exponential tandem queues with blocking, SIAM J. Alg. Disc. Meth, 1, 93105, 1980.

[33] Meyn, S., and Tweedie, R. Markov Chains and Stochastic Stability. Springer, Berlin, 1993.

[34] Nummelin, E. General Irreducible Markov Chains and Non-negative Operators. Univ. Press, Cambridge, Cambridge, 1983.

[35] Pardoux,'E., Processus de Markov et applications algorithmes, Réseaux, Génome et Finance, 2006.

[36] Rachev, S. The problem of stability queuing theory. Queuing Systems, 4, 287-318, 1989.

[37] Ruegg, A. Processus Stochastique. Presse Polytechnique Rromandes, Suisse, 1988.

[38] Saneta, E. Finite approximations to infinite non-negative matrices. Proc.Cambridge, 15, 983-992, 1967.

[39] Seneta, E. Nonnegative Matrices and Markov Chains. Springer,Ed., 1881.

[40] Seneta, E. The principle of truncations in applied probability. Commentationes Mathematicae Universitatis Carolinae 1968.

[41] Seneta, E. Computing the stationary distributon for infinite Markov chains. Linear Algebra Appl, 34 , 259-267, 1980.

[42] Simonot, F. Sur l'approximation de la distribution stationnaire d'une chaàýne de Markov stochastiquement monotone. Universit'e Henri Poincar'e 1993.

[43] Stoyan, D. Ein stetigkeitssatz für einlinige wartemodelle der bedienungstheorie. Maths. Operation Forsch. Statist, 3, 103-111 , 1977.

[44] Tijms, H. Stochastic Modelling and Analysis A Computational Approach. Wiley, New York, 1986.

[45] Trân, M. Insensibilitédans les Réseaux de Files d'Attente et Applications au Partage de Ressources Informatiques. Doctorat, Ecole Nationale Sup'erieure des T'el'ecommunications, rued'Ulm , 29 Octobre 2007.

[46] Tweedie, R. Truncation approximations of invariant measures for Markov chains. Colorado State University.

[47] Valois, F. Modélisation et evaluation de performances de réseaux chapitre 5 : réseaux de files d'attente (la forme produit).

[48] Van Dijk, N. Truncation of Markov chains with applications to queueing. Operation Research, 39, 1018-1026, 1991.

[49] Willig, A. A Short Introduction to Queueing Theory. Berlin, 1999.

[50] Wolf, D. Approximation of the invariant probability distribution of an infinite stochastic matrix. Adv.Appl.Probab, 12, 710-726, 1980.

[51] Zhao,Y.Q. and Liu,D. The censored Markov chain and the dest augmentation. Journal of Applied Probability,33, 623-629, 1996.

[52] Zolotarev, V. On the continuity of stochastic sequence generated by reccurent processes. Theory of Probability and its Applications , 20 , 819-832, 1975.