Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

REVUE FRANÇAISE D’AUTOMATIQUE, D’INFORMATIQUE ET DE RECHERCHE OPÉRATIONNELLE. R

REVUE FRANÇAISE D’AUTOMATIQUE, D’INFORMATIQUE ET DE RECHERCHE OPÉRATIONNELLE. RECHERCHE OPÉRATIONNELLE G. PUJOLLE Réseaux de ﬁles d’attente à forme produit Revue française d’automatique, d’informatique et de recherche opérationnelle. Recherche opérationnelle, tome 14, no 4 (1980), p. 317-330. <http://www.numdam.org/item?id=RO_1980__14_4_317_0> © AFCET, 1980, tous droits réservés. L’accès aux archives de la revue « Revue française d’automatique, d’infor- matique et de recherche opérationnelle. Recherche opérationnelle » implique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/ legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce ﬁ- chier doit contenir la présente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques http://www.numdam.org/ R.A.I.R.O. Recherche opérationnelle/Opérations Research (vol. 14, n° 4, novembre 1980, p. 317 à 330) RÉSEAUX DE FILES D'ATTENTE A FORME PRODUIT (*) par G. PUJOLLE (*) Résumé. — Les réseaux de files d'attente dans lesquels la probabilité jointe à Vétat stationnaire possède une forme produit, ont beaucoup été étudiés sous divers angles. Nous essayons dans cet article d'unifier les propriétés de ces réseaux. Une nouvelle classe de réseaux à forme produit est introduite qui généralise sur certains points et contredit sur d^autres les résultats déjà connus. Abstract. — Networks in which the joint equilibrium distribution of queue sizes is expressed in a product form> has been widely studied. In the present paper, we try to unify the properties of these networks. A new class of product for m networks is derived. 1. INTRODUCTION Les réseaux de files d'attente ont une très grande importance en recherche opérationnelle. Ils servent à modéliser des systèmes physiques. Ils permettent ainsi d'évaluer les performances et de mieux comprendre le comportement de ces systèmes. Peu de réseaux de files d'attente ont une solution simple. Ceci provient de la difficulté d'étudier les propriétés des flux, à l'intérieur du réseau. Les mieux étudiés sont les réseaux de Jackson [1]. Par réseaux de Jackson, nous entendons un ensemble de files d'attente reliées entre elles de façon quelconque, la distribution des temps de service étant exponentielle et le processus des arrivées de l'extérieur étant poissonien. Les files sont de capacité illimitée de telle sorte qu'il n'y ait pas de blocage; la discipline de service est premier-entré — premier-sorti. Ce type de réseau a été étudié par Jackson [1] dans le cas ouvert et par Gordon et Newell [2] dans le cas fermé, ils ont montré que la probabilité jointe, à l'état d'équilibre, défini par le nombre de clients présents dans chaque station, se présente sous la forme produit. Depuis cette époque peu d'intérêt a été porté à ce type de réseau étant donné la forme simple de sa solution. S'il est vrai que du point de vue application peu de progrès peuvent être fait, il en va tout autrement du point de vue compréhension de ce type de réseau. (*) Reçu septembre 1979. C) I.N.R.I.A., 78150 Le Chesnay, France. R.A.I.R.O. Recherche opérationnelle/Opérations Research, 0399-0842/1980/317/$ 5.00 © AFCET Bordas-Dunod 318 G. PUJOLLE En effet si l'on s'intéresse aux flux entre stations, ces flux n'ont pas du tout de bonne propriété, comme on le pensait généralement jusqu'ici. Ce ne sont en général ni des processus de Poisson, ni même des processus de renouvellement. Le but de cet article est d'une part d'apporter au lecteur un nouveau regard sur les réseaux qui ont la propriété d'avoir la forme produit comme les réseaux de Jackson et d'autre part d'essayer de caractériser la nature du processus de sortie d'une file d'attente quelconque. Ces examens nous portent à carac- tériser une nouvelle sorte de réseaux à forme produit qui étend les résultats classiques. Figure 1, — Un réseau général. Soit un réseau général comme celui montré sur la figure 1, qui possède K files d'attente. Les probabilités de routage ptj d'aller de la file i vers la file y sont déterminées par une chaîne de Markov d'ordre 1. La station 0 est une station fictive dénomant à la fois l'entrée et la sortie du système de telle sorte que pQi est la probabilité pour un client arrivant de l'extérieur d'aller vers la file i et pJ0 est la probabilité pour qu'un client finissant son service à la station j , sorte du système. Soit nu n2, ..., nK, le nombre de clients respecti- vement dans la file 1, 2, ..., K. Le comportement du réseau est totalement défini par les valeurs de p (nlt n2, ..., nKi t) : probabilité d'être au temps t dans l'état nun2, ...9nKi que nous appellerons probabilité jointe. Nous emploierons la même notation pour les probabilités marginales p (nt, t ) d'avoir rii clients dans la file i au temps t. Le contexte permet de ne pas confondre entre probabilité jointe et probabilité marginale. Nous dirons que le réseau de files d'attente est markovien si le processus p (nu n2, ..., nK, t) est un processus de Markov avec l'espace d'état {N}K. R.A.I.R.O. Recherche opérationnelle/Opérations Research RÉSEAUX DE FILES D'ATTENTE A FORME PRODUIT 319 Un réseau de files d'attente sera dit en équilibre s'il existe un état stationnaire. Dans ce cas, nous ôterons le temps t des probabilités jointes et marginales. Par définition nous dirons qu'un réseau a la forme produit si K p(nu n2, ..., n*)= Ei P( nà- i=i Nous utiliserons la terminologie suivante : les entrées et les sorties d'une file d'attente sont constituées par les clients entrant et sortant effectivement de la file d'attente; les arrivées et les départs sont constitués par les (ou le) flots pris séparément venant d'autres stations ou de l'extérieur et partant vers d'autres stations ou vers l'extérieur. Les entrées sont une superposition d'arrivées. Les sorties donnent naissance à des départs. 2. LE PROCESSUS DE SORTIE D'UNE FILE D'ATTENTE Un grand nombre de publications concernent ce problème. Nous en résumons les principales étapes avant d'aborder les conditions qui doivent être remplies pour que le processus de départ soit un processus de Poisson. En 1956 Burke [3] montra que le processus de départ d'une file M/M/s était Poissonien. Sa preuve consiste en la démonstration de l'indépendance d'un intervalle entre deux sorties et de l'état du système à la fin de cet intervalle. A peu près au même moment Reich [4] montrait le même résultat en utilisant la réversibilité d'un processus stochastique stationnaire. En 1959 Finch [5] étudia la file M/GI/l/m avec une distribution des temps de service dérivable deux fois. Il montra qu'à l'état d'équilibre le seul cas où les intersorties forment un processus de Poisson indépendant du processus d'entrée est obtenu pour GI = M et m = oo. Enfin Disney et Cherry [6], Disney, Farrel et de Morais [7] montrent le théorème suivant : THÉORÈME : Une file M/GI/l/m a des intersorties qui forment un processus de renouvellement si et seulement si l'une des conditions suivantes est vérifiée : 1) les temps de service sont tous nuls avec probabilité 1; 2) m = 1; 3) m = 2 et les temps de service sont constants (GI = O); 4) m = oo et ^s temps de service sont exponentiels (GI = M), vol. 14, n° 4, novembre 1980 320 G. PUJOLLE Dans ces quatre cas, les distributions de probabilité des intersorties sont respectivement les suivantes : 1) la même que celle du processus d'entrée; 2) la convolution de celle du processus d'entrée et du processus de service; 3) une somme de convolutions; 4) la même que celle du processus d'entrée. De plus, il a été démontré par Daley [8] que parmi les systèmes GI/M/l, le seul qui ait un processus de sortie de renouvellement est encore le système M/Af/1. Plus récemment Laslett [9] a montré qu'aucun système GÏ/M/l/m avec m fini, n'a un processus de renouvellement en sortie. Par l'ensemble de ces résultats, nous pouvons conjecturer que le seul système GI/GI/l/m, m > 0 qui a un processus de sortie poissonien est le système M/M/l/ao. A partir de ce résultat nous trouvons un premier ensemble de réseaux à forme produit : ce sont les réseaux n'ayant que des files du type M/M/l/oo c'est-à-dire des réseaux possédant des files du type ./M/l/oos où il n'y a jamais la possibilité pour un client de passer deux fois par la même station et où les arrivées de l'extérieur sont poissoniennes. Un tel réseau est représenté sur la figure 2. Figure 2. — Un réseau de files d'attente à flux poissonien. Il faut noter que dans de tels réseaux tous les flux sont des processus de Poisson indépendants. Le second type de réseaux que nous allons étudier est constitué de ceux qui satisfont aux équations de balance locale [10] : le flux des clients arrivant dans une station contenant n clients est égal au flux des clients sortant de cette même station en y laissant n clients. Chandy, Howard et Towsley [11] montrent qu'un réseau qui satisfait aux équations de balance locale a une solution en forme de produit, R.AXR.O. Recherche opérationnelle/Opérations Research RÉSEAUX DE FILES D'ATTENTE A FORME PRODUIT 321 La plupart des réseaux qui satisfont aux équations de balance locale sont donnés dans l'article uploads/Industriel/ ujolle-reseaux-de-files-d-x27-attente-a-forme-produit.pdf