C. R. Acad. Sci. Paris, t. 330, Série I, p. 893–897, 2000Probabilités/Probability Theory(Statistique/Statistics)

Régénération et intégrabilité pour des réseaux ouvertsFrançois CHARLOT a, Bénamar CHOUAF b

a LAMS UPRES-A 6085, Université de Rouen, 76821 Mont-Saint-Aignan cedex, FranceCourriel : Francois.Charlot@univ-rouen.fr

b Département de mathématiques, Université Djilali-Liabès, 22000 Sidi Bel-Abbès, AlgérieCourriel : Chouafb@yahoo.fr

(Reçu le 20 avril 1999, accepté après révision le 20 avril 2000)

Résumé. Le but de ce travail est de mettre en évidence des cycles de régénération pour unecascade stable de files d’attente, d’étudier les propriétés d’intégrabilité et d’en déduiredes théorèmes limites. 2000 Académie des sciences/Éditions scientifiques et médicalesElsevier SAS

Regeneration and integrability for some open networks

Abstract. The aim of this paper is to put in evidence the regeneration cycles for stable queue tandems,to study the properties of integrability and to deduce the limit theorems. 2000 Académiedes sciences/Éditions scientifiques et médicales Elsevier SAS

Abridged English version

In this Note we are interested in the regeneration phenomena for stable tandem queues with multiserversand the properties of integrability of the regeneration cycles. The last stage is devoted to limit theorems.The study of the regeneration points for tandem queues with multiservers has already been undertakenin [17]. The method described herein is quite different from those quoted before. The works concerning theproblems of integrability for single queue, have been principaly reported by [14], and [1,3–10,19,20]. Thereference [1] is the only paper where the integrability conditions of the regeneration cycles have been themain subject, which allows to obtain limit theorems (see[11,12] and [4]).

We consider a system of tandem queues ofm stations. The “input-service” process is a renewalmarked punctual process, with marks inRm+ , N =

∑n∈Z δTn ⊗ δBn , on a real flow

(Ω,A,P,Θ

), where

Bn = (B1n, . . . ,B

mn ) represents the periods of time when them stations are occupied by the customer

and we suppose that(B`n; n ∈ N, 1 6 ` 6 m) are some independent random variables. We denoteAn = Tn − Tn−1, a = ess supA and b = ess infB = (b1, . . . , bm). The customer arrived in the systemat the instantTn passes successively in each of them services at the instantsTn, T 1

n , . . . , Tm−1n .

LetW (x, t) = (W 1(x, t), . . . ,Wm(x, t)) the load vector of the system with initial statex= (x1, . . . , xm)∈Rq+. Under the stability hypothesis, for each` such that16 `6m, E(B`)< q`E(A), this system possess

Note présentée par Paul DEHEUVELS.

S0764-4442(00)00293-7/FLA 2000 Académie des sciences/Éditions scientifiques et médicales Elsevier SAS. Tous droits réservés. 893

F. Charlot, B. Chouaf

an unique stationary regime, noted byW(t) = (W1, . . . ,Wm) and the processW = (W (x, t); x∈Rq+, t ∈R+) is stable well self coupled on the flow(Ω,A,P,Θ).

The forgetting property of the initial state of this system is etablished and we construct the regenerativephenomenon which we denote by(Lk; k ∈ Z).

The limit theorems are obtained under the conditions of integrability of the regeneration cycles. Ourresults are the following.

LEMMA 1. –For eachε > 0, there exists a compact subsetVε ofRq such thatVε =∏m`=1 Vε` , where for

each` such that,16 `6m, Vε` is a compact subset ofRq` and ifx ∈ Vε, then for alln> 1,

Hn ⊆n⋂k=1

W (x,Tk) ∈ Vε

.

Moreover, ifj represents the minimum number of occupied servers, then for everyk such thatj+16 k 6 n,and onHn, we have:

W (x,Tk) =W (0q, Tk) = f((Ar,Br−1); k− j 6 r 6 k

),

wheref is a Borel function(Rm+1+ )j+1 −→Rq+.

THEOREM 1. –For eachp ∈N,(i) if B ∈Lp+1(P) and ifA ∈Lp+1(P), then

W(T0) ∈Lp(P), W(0) ∈ Lp(P), L1

(W(T0)

)∈Lp

(P), L1 ∈ Lp

(P)

andL1 ∈ Lp+1(P),

(ii) if B ∈L2p(P) and ifA ∈L2p(P), then

L1∑i=1

W(Ti) ∈ Lp(P),

L1∑i=1

Wi ∈ Lp(P)

andL1∑i=1

Bi−1 ?Π(W i) ∈ Lp(P).

1. Introduction et généralités

L’étude des phénomènes régénératifs pour une cascade stable de files d’attente à plusieurs serveurs adéjà été faite dans [17], mais notre méthode est différente. Si des problèmes d’intégrabilité dans les filesd’attente sont étudiés dans la littérature (voir par exemple [14,1,3–10,19,20]), on ne trouve que dans [1] desconditions d’intégrabilité des cycles de régénération. Nous nous intéressons dans ce travail à un phénomènerégénératif pour ce type de système et aux propriétés d’intégrabilité des cycles de régénération ainsi définis.Ces propriétés d’intégrabilité sont cruciales pour démontrer des théorèmes limites (voir [12,11] et [4]). Nousdonnons un de ces théorèmes en exemple.

Nous considérons un système de files d’attente en cascade àm stations et àq serveurs, la stationayantq` serveurs identiques (q` ∈ N∗). Le processus des « entrées-services » est un processus ponctuel marquéstationnaire (ppms) de renouvellement [16], à marques dansRm+ , N =

∑n∈Z δTn ⊗ δBn , sur un flot réel

(Ω,A,P,Θ), oùBn = (B1n, . . . ,B

mn ) représente les durées des services réclamés successivement auxm

stations par le client arrivé à l’instantTn ; les (B`n; n ∈ N, 1 6 `6m) sont supposées être des variablesaléatoires indépendantes, indépendantes des(Tn, n ∈ Z). On note

(Ω, A, P, (θn, n ∈ Z)

)le flot de Palm

(voir [16]) associé au processus ponctuel∑

n∈Z δTn etAn = Tn−Tn−1 l’inter-arrivée des clientsn etn−1.

894

Régénération et intégrabilité pour des réseaux ouverts

Le client arrivé dans le système à l’instantTn passe successivement dans chacun desm services auxinstantsTn, T 1

n , . . . , Tm−1n . Soit,W (x, t) = (W 1(x, t), . . . ,Wm(x, t)) le vecteur « charge du système »

d’état initialx= (x1, . . . , xm) ∈Rq+. Sous l’hypothèse de stabilité,

∀`, 16 `6m, E(B`)< q`E(A),

ce système possède un unique régime stationnaire [2], notéW(t) = (W1(t), . . . ,Wm(t)), ce qui signifiequ’il existe une unique variable aléatoireW à valeurs dansRq+ telle que, pour toutt ∈ R+, W (W , t) =W θt =W(t).

2. Regénération

Soienta= ess supA, pour16 i6m, bi = ess infBi, etb= (b1, . . . , bm). Sous l’hypothèse de stabilité,on a l’alternative suivante :(i) si

∑m`=1 b

` < a, le système se vide une infinité de fois ;(ii) si

∑m`=1 b

` > a, il y a toujours au moins une station occupée, c’est-à-dire que,∀x ∈ Rq+, x 6= 0,∀t ∈R+,W (x, t) 6= 0.

L’hypothèse (i) est celle qui est faite ordinairement dans les systèmes de files d’attente. Les temps deretour deW (x, ·) ou deW en0 forment alors une suite de temps régénération pour notre système. Maison peut avoir des temps de régénération sans cette hypothèse. C’est ce que nous décrivons maintenantrapidement. L’idée est la suivante et elle se trouve à l’origine dans un papier de J. Kieffer et J. Wolfowitz[13] ; partant de n’importe quel pointx ∈ Rq , si on impose aux temps de services d’être assez petits etaux inter-arrivées d’être assez grandes, alors le système va se trouver au voisinage d’un point qui est unesorte de point minimum pourW (x, ·) et bien sûr indépendant dex ; de plus, si on reste assez longtemps auvoisinage de ce point, alors le système « oublie » d’où il est parti.

Soit ε > 0. Pourn ∈N∗, soitHn =⋂nk=1Bk 6 b+ ε~em,Ak > a− ε, où~em = (1, . . . ,1) ∈Rm. On a

P(Hn)> 0.

LEMME 1. –Pour ε > 0 assez petit, il existe un sous-ensemble compactV deRq tel que six appartientà V , n> 1 etω ∈Hn, alors pour toutk ∈N, 16 k 6 n,W (x,Tk(ω)) ∈ V . De plus, il existej ∈N tel quesi n > j et pour toutk tel quej + 16 k 6 n,W (x,Tk(ω)) est indépendant dex ∈ V et ne dépend que desvariablesAr,Br−1 pourk− j 6 r 6 k.

On peut construire un processus ponctuel stationnaire∑k∈Z δLk sur

(Ω, A, P, (θn, n ∈ Z)

)tel que,

pour toutk ∈ Z, W(TLk−p) ∈ V , 0 6 p 6 j, Lk − Lk−1 > j etW(TLk) ne dépend que des variablesAr,Br−1 pourLk − j 6 r 6 Lk.

Soit, pour toutk ∈ Z, Yk =(Lk −Lk−1; W(TLk−1+1), . . . ,W(TLk)

).

LEMME 2. –La suite(Yk, k ∈ Z) est une suite strictement stationnaire et2-dépendante par rapport àP = P(/L0 = 0). La suite(Yk, k > 2) est une suite strictement stationnaire et2-dépendante par rapportaux probabilitésP et P, de même loi queY1 sousP.

3. Intégrabilité

Si X et Y sont deux éléments deRm, on note parX ? Y le vecteur deRm défini parX ? Y =(X1Y1, . . . ,XmYm). On désigne parΠ la projection deRq1×· · ·×Rqm surRm qui à toutx= (x1, . . . , xm)∈Rq1 × · · · ×Rqm fait correspondre(x1

1, . . . , x1m) ∈Rm. En régime stationnaire, le vecteur

W =(Wi, i ∈ Z

)=((W1(Ti),W2

(T 1i

), . . . ,Wm

(Tm−1i

)), i ∈ Z

)désigne le temps d’attente dans lesm stations du client arrivé à l’instantTi dans le système.

895

F. Charlot, B. Chouaf

Le théorème suivant donne des propriétés d’intégrabilité des cycles de régénération pour une cascadestable. C’est le résultat principal de cette Note.

THÉORÈME 1. –Pour toutp ∈N :(i) siB ∈ Lp+1(P) et siA ∈ Lp+1(P), alors

W(T0) ∈ Lp(P), W(0) ∈Lp(P), L1

(W(T0)

)∈ Lp

(P), L1 ∈Lp

(P)

etL1 ∈ Lp+1(P);

(ii) siB ∈ L2p(P) et siA ∈L2p(P), alors

L1∑i=1

W(Ti) ∈ Lp(P),

L1∑i=1

Wi ∈Lp(P)

etL1∑i=1

Bi−1 ?Π(W i) ∈Lp(P).

On sait [1] que le résultat est vrai pour un système ne comportant qu’une station et donc pour la premièrestation du système en cascade. On procède station après station. Nous décrivons comment on passe dela première à la seconde station, la méthode étant identique pour les stations suivantes. On se place enrégime stationnaire. La difficulté provient d’une part de ce que les sorties ne forment pas un processus derenouvellement, d’autre part que les clients ne sortent pas dans leur ordre d’arrivée. Mais les instants derégénération décrits ci-dessus sont des instants de « remise en ordre » en ce sens que les clients de numérocompris entreLk−1 + 1 etLk sortent tous avant les clients de numéro compris entreLk + 1 etLk+1. Les(TLk , k ∈N) ne forment pas un processus de renouvellement puisqu’ils sont seulement2-dépendants. Pourpallier à cette difficulté, on utilise le procédé de discrétisation Kiefer et Wolfowitz sur la première station ; leprocessus de charge de la première station est alors une chaîne de Markov à valeurs dénombrables. LesLckrelatifs à cette station et à cette discrétisation forment une sous-suite desLk avant discrétisation et sont unprocessus de renouvellement. On peut alors étudier la seconde files aux instants où les clients «Lck » entrentdans la seconde station. On utilise alors des procédés de majoration comme dans [1], et on obtient desrésultats d’intégrabilité pour le processus à ces instants. Puis, par des calculs « à la Palm » nous démontronsles résultats cherchés. Pour plus de détails,voir [3].

4. Théorèmes limites

Sous la condition de stabilité et l’existence de moments d’ordre suffisant pour les temps de service et lesinter-arrivées, des théorèmes limites (lois fonctionnelles des grands nombres, théorèmes centraux limiteset lois fonctionnelles du logarithme itéré) sont obtenus pour des processus générés par les charges desserveurs, les longueurs des files, la somme des travaux des serveurs ou encore les processus des sorties desclients. Les démonstrations sont semblables à celles que l’on trouve dans [12]. Elles se trouvent dans [4].La nouveauté des énoncés réside dans les conditions sur les moments deB1 et A1 qui remplacent leshypothèses d’intégrabilité sur les cycles de régénération.

Nous donnons à titre d’exemple, le théorème central limite pour le processus généré par la charge dusystème en régime stationnaire(Wn;n ∈N∗) et transitoire(W x

n ;n ∈N∗).

THÉORÈME 2. –Sous l’hypothèse de stabilité, siB ∈ L4(P) etA ∈ L4(P) et si pour touti, 1 6 i6 q,σi,i 6= 0, où

σi,i = E((Zi0)2)

+ 2E(Zi0Z

i1

)avec

Z0 =

L1∑i=1

W(Ti)−L1E(W(T0)

),

896

Régénération et intégrabilité pour des réseaux ouverts

alors, pour toutx ∈Rq+, les suites de processus:((∑[nt]i=0W(Ti)− E(W(T0))(

nE(L1))1/2 , t ∈R+

), n> 1

)

et ((∑[nt]i=0W

x(Ti)− ntE(W(T0))(nE(L1)

)1/2 , t ∈R+

), n> 1

)

convergent en loi, sousP, P et P, dans l’espace de SkorohodDq(R) vers un mouvement brownienq-dimensionnel quandn tend vers+∞.

Références bibliographiques

[1] Charlot F., Intégrabilité des temps de renouvellement des files d’attente et applications, Ann. Sci. ClermontFerrand-II 87 (1985) 1–41.

[2] Charlot F., Chouaf B., Guellil A., Sur la stabilité et la récurrence des chaînes de Markov et de systèmes de filesd’attente, Ann. Sci. Clermont Ferrand-II 93 (1989) 13–47.

[3] Charlot F., Chouaf B., Regeneration and integrability cycles in tandem queues with identical multiservers,Prépublication, Université de Rouen, 1999.

[4] Chouaf B., Renouvellement, intégrabilité et théorèmes limites pour des files d’attente en cascade, Thèse dedoctorat, Université de Rouen, 1990.

[5] Dai J.G., Meyn S., Stability and convergence of moments for multiclass queueing networks via fluid limit models,IEEE Trans. on Autom. Contr. 40 (11) (1995).

[6] Daley D.J., The serial correlation coefficient of waiting time in a stationary single server queue, J. Austral. Math.Soc. 8 (1968) 683–699.

[7] Daley D.J., The correlation structure of the output process of some single server queueing systems, Ann. Math.Statis. 39 (1968) 1007–1019.

[8] Daley D.J., Rolski T., Finiteness of waiting-time moments in general stationary single-server Queues, Ann. Appl.Probab. 2 (1992) 987–1008.

[9] Daley D.J., Foley D.R., Rolski T., Conditions for finite moments of waiting time in G/G/1 queues, Queueing Syst.Th. Appl. 17 (1994) 89–106.

[10] Daley D.J., Some results for the mean waiting-time and workload in GI/GI/k Queues, Frontiers in Queueing,Probab. Stoch. Ser., CRC, Boca Raton, FL, 1997, pp. 35–39.

[11] Ghidouche M.A., Irréductibilité, récurrence au sens de Harris et théorèmes limites fonctionnels pour des filesd’attente GI/G/q, Thèse de troisième cycle, Université de Rouen, 1978.

[12] Iglehart D., Functional limit theorems for the GI/G/1 in light traffic, Adv. Appl. Probab. 3 (1971) 269–281.[13] Kiefer J., Wolfowitz J., On the theory of queues with many servers, Trans. Amer. Math. Soc. 78 (1955) 1–18.[14] Kiefer J., Wolfowitz J., On the characteristics of general queueing process with application to random walk, Ann.

Math. Statis. 29 (1956) 147–161.[15] Nafidi A., Irréductibilité, petits ensembles et régénération des réseaux de Jackson généralisés, Thèse de

l’Université de Rouen, 1997.[16] Neveu J., Processus ponctuels, École d’Été de probabilités de Saint-Flour, Lect. Notes in Math. 598, Springer-

Verlag, 1976.[17] Sigman K., Regeneration in tandem with multiservers, J. Appl. Probab. 25 (1988) 391–403.[18] Sigman K., Yao D.D., Finite moments for inventory processes, Ann. Appl. Probab. 4 (1994) 765–778.[19] Sigman K., Scheller-Wolf A., New bounds for expected delay in FIFO GI/GI/c queues, Queueing Syst. Th. Appl.

26 (1997) 169–186.[20] Sigman K., Yao D.D., Finite moments for inventory processes, Ann. Appl. Probab. 4 (1994) 765–778.

897