'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.
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.
[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.
