Sur quelques problèmes d'attente récents

$ U R Q U E L Q U E S PIIOBL~,,MES D'ATTENTE II]~CENTS*

par Pierre LE GALL Ing6nieur des T616communications **

SoMM~ia~. - - L'auteur rgsume les rgsuhats principaux obtenus concernant divers probl~mes d'attente de~,ant un ~ guichet ~, duns le cas d'hypoth~ses tr~s larges concernant le processus des arriv~es et la [onction de r@artition de la durde de service. Ces probl~mes, d'applicatlons [r~quentes, sont, en /ait, encore peu abord~s. - - On d~finit les deux types de guichets ~ ordinaires ~ or, ~ permanents ,, ainsi que trois types de services par groupes. On envisage ensulte le cos des arrivdes en groupe. - - Ces probl~mes sont trait~s duns le cas du choix des ~ visiteurs ~ dans l'ordre des arriv~es, aussl bien que duns le cas du ehoix au hasard. - - L'extension est [aite au cas de s guichets pour des dur~es de service exponentielles ou constantes. - - En t~l@honle, les guichets permanents correspondent au cas de la commutation ~lectronique, dot~e d'organes de commande ayant leur propre ~ horloge ~. - - De m~me, la commutation ~lectronique, comme la commutation classique, pose le cas du choix au hasard. A ce su/et, les courbes bien eonnues de Crommelin donnent souvent des rgsultats trop optimistes. II est plus prudent de prendre les r~sultats

donngs par l'hypoth~se du choix au hasard.

PLXN. --- Introduction. D~finitions. Hypotheses et notations. B~[grences bibliographlques. - - A I: Cas de 1 g u i e h e t . (1 o) Arrivdes isol$es et service par groupes de s visiteurs. (2 o) Arriv~es en groupes avee service ordinaire. - - B : Cas de s g u i e h e t s ordinai~ 'es avee s e r v i c e o r d i n a i r e ( arri~,ges isolges) ; choix au hasard ; (1o) Durge deservice exponentielle. (2 ~ Durge de service constante avec arrivges poissonniennes. - - A p p l i c a t i o n ~t la t d l d p h o n i e . - Annexes ; (I) Bappel des principaux r~sultats clans le cas du choix des visiteurs dans leur ordre d'arriv~e. (II) Rappel des prineipaux rgsultats duns le cas du choix des visiteurs au hasard. (III) Cas des guicbets ?t duroc

de service constante avec arriv$es poissonniennes isol~es. - - Bibliographic (16 r~[.).

INTRODUCTION

Les techniques modernes de commutat ion t616- phonique, et sp6cialement celles de la commutation t616phonique 61ectronique, posent des probl~mes d 'a t tente encore h peine 6tudi6s.

Tout d 'abord la rapidit6 accrue des organes permet de simplifier le m6canisme de choix, et de se borner h prendre prat iquement les appels au hasard.

Ensuite, il peut exister, dans le cas d'organes de commande 61ectroniques, utilisant la technique mul- tiplex h impulsions, un syst~me d'horloge, appel6 encore ~c t:m!ng ~, contrblant tous ces organes, de sorte que plusieurs, remplissant la mgme fonction, peuvent servir s imuhan6ment chacun un appel. Ce fonctionnement est identique au cas d 'un seul organe servant simultan6ment plusieurs appels: service par groupes.

De mgme, ce syst~me d'horloge 6tant ind6pen- dant des arriv6es des appels, il y a at tente, mgme en l'absence de queue, comme un visiteur a t tendant devant un tourniquet automatique et ne pouvant passer que lorsque celui-ci se pr6sente dans la posi- t ion lui permet tant de passer: nous dirons plus loin qu'il s 'agit d 'un ~c gulchet permanent ~.

Ces sortes de probl~mes se t rouvent aussi fr6- quemment en recherche op6rationnelle.

D]~FINITIONS

Nous prenons les termes, habituels cn recherche op6rationnelle, de ~ visiteurs ~ a t tendant devant des cc guichets ~, au lieu d'appels a t tendant devant un faisceau de circuits, d'enregistreurs, de marqueurs,..., encombr6s. D'habitude on consid~re des visiteurs a t tendant devant des guichets, de sorte qu 'un guichet, devenu libre, est prgt h servir un visiteur en attente. En particulier, dbs l'arriv6e d 'un premier vislteur, celui-ci est servi par l 'un des guichets. Ces guichets sont au repos en l'absence de visiteurs. Nous disons qu'il s'agit, dans ce cas, de guichets

ordinaires. En outre, chaque guichct ne sert qu 'uu visitcur h

la lois. Nous disons qu'il effectue un service ordinaire. Consid6rons maintenant l 'image du tourniquet

automatiquc utilis6e pr6c6demment. Le temps de rotat ion complet de cet organe correspond h une dur6e de service, alors qu'i! peut ne pas servir effec- t ivemcnt un visiteur, s'il n 'y en a pas. I1 est toujours au travail, mgme en l'absence de visiteurs. Lcs instants off il peut commencer h servir un visiteur sont ind6pendants de la fa~on dont arrivent los visiteurs. Nous disons qu'il s'agit d 'un guichet permanent . I1 n'est jamais au repos, et, de fa~on g6n6rale, ses dur6es de service peuvent ~tre al6atoires, les instants de fin

* Communication pr6sent6e au 3 e Congr6s International de T616trafic, Minist~re des Postes ct T616communications, Paris, 1t-16 septembre 1961.

** Au C. N. E. T., D6partement RECnEaCaES SUn MACHINES I~,LECTRONIQUES. [] En r~gle g6n6rale pour tout renvoi entre crochets au eours du texte d'un article, pri~re dc sc reporter h la biblio-

graphic compl6tant l'article in fine.

214 - -

t. 16, n ~ 9-10, 19611

de service 6tant ind6pendantss du proeessus des arriv6es de visiteurs.

Ce guichet (r permanent )~ s'oppose done au guichet (( ordinaire )).

Par opposition au cas du service (( ordinaire )), un guichet, susceptible de servir jusqu'~ s visiteurs simultan6ment, est dit effectuer un (( service par groupes )).

Nous distinguons trois types de service par groupes :

a) le (ou les) guichet est permanent ; b) le (ou les) guichet d6marre, ou fonctionne, d~s

l'arriv6e d 'un premier visiteur ; c) le (ou les) guichet ne d6marre, ou ne fonctionne,

qu'en pr6sence d 'un groupe complet de s visiteurs. Enfin, nous envisageons deux lois de choix des

visiteurs : le choix clans l'ordre des arrivdes et le choix au hasard. Dans ce dernier cas, h une fin de service, t o u s l e s visiteurs en at tente ont la m~me chance d'etre choisis.

Habituellemen L on consid~re les arri~,des isol/es, ce qui est le cas du t616phone ; mais en recherche op6rationnelle, dans des probl~mes de livraison par exemple, on peut 6tre amen6 ~ consid6rer le cas d'arri~,des en groupes, off plusieurs visiteurs peuvent arriver simultan6ment (*).

Ces probl~mes sont d'applications fr6quentes dans la pratique. Par exemple, l 'a t tente des automobiles devant un feu de signalisation h un carrefour de rues correspond au cas d 'un guichet avec service par groupes de s visiteurs, s 6tant le nombre de voitures pouvant passer durant le feu vert. La dur6e de service correspond h l 'intervalle s6parant les d6buts de deux feux verts successifs. Le choix est dans l 'ordre des arriv6es. Si le feu de signalisation a sa propre horloge, il s 'agit d 'un guichet permanent. Si, au contraire, il est pr6vu un dispositif inerrant le feu au vert d6s l'arriv6e d'une premiere voiture, nous avons un guichet ordinaire fonctionnant d6s l'arriv6e d 'un premier visiteur. L'6tude de ce pro- bl6me d 'a t tente permet de pr6ciser, suivant ]es trafics ~ 6couler sur les deux voles qui se croisent, les dur6es des feux rouges et verts, pour une cer- taine longueur de queue h admettre.

Cet exemple montre les probl~mes communs qui peuvent se poser en t616phonie et en recherche op6rationnelle.

H Y P O T H E S E S E T N O T A T I O N S

Nous faisons les trois hypotheses les plus fr6- quentes et donnant lieu aux calculs les plus simples, bien que d6jh tr~s complexes en g6n6ral.

t ~ Les diverses durdes de service al6atoires ol36issent h la m~me fonction de r6partition Fl(t) avec

(*) En fair, le eas de l '6 tabl lsscment d 'une conversat ion entre deux abonn6s d 'un m6me concen t ra teur t616phonique est un cas d 'arriv6es simultan6es de deux appels pour le con- cent ra teur , puisqu'elle n6cessite l 'oecupat ion simultan6e de deux circuits du concentra teur .

SUB QUELQUE$ PROBLEMES D'ATTENTE RI~CENTS 2/12 FI(0) = 0, st nous posons (trans~orm6s de Laplace) :

(1) q~1(z) = e"t .dFl( t ) .

Cette fonetion se r6duit h la fonetion earact6ris- t ique de Fl(t ) sur l 'axe imaginaire du plan eom- plexe z, fonetion qui existe toujours. Pour la eom- modit6 du langage, nous l'appellerons fonetion earaet6ristique pour les autres valeurs de z off ells est encore d6finie.

2 o Dans le cas d'arriv6es isol6es, ou d'arriv6es de groupes, les intervalles d'arriv~es sont mutuellement ind6pendants et ob6issent h la m~me fonction de r6partition F2(t ) avec F2(0 ) ~--- 0, qui a pour fonetion earaet6ristique :

(2) q~2(z) = e"t.dF2(t).

Nous disons que le processus d'arrivdes est rdgdnd- rati[.

3 ~ Les dur6es de services et d'intervalles d'arri- v6es sont mutuellement inddpendantes.

Nous prenons la dur6e moyenne des services pour unit6 de temps :

(3) ~;(0) = 1.

Rappelons que le cas d 'une dur6e de service exponentielle correspond h :

(4) F~(t) = t - - O -l , ~.~I(Z) " 1/(1 -- z).

De m6me, le cas d'une dur6e de service constante correspond 5 :

(5) F~( t )=0 s i t < 1, q~(z)=e z. = 1 si t > t .

Le cas des arriv6cs poissonniemlcs de dcnslt6 c correspond 5 :

Le cas des arriv6es en groupes sera pr6cis6 au paragraphe r6serv~ h ce sujet.

Nous d6signons par F(t) la /onction de rgpartition de l'attente, subie par un visiteur quelconque, dans le cas du rdgime stationnaire. Sa /onction caractdristique est :

(7) 49(z)= .~_2 ~ e~t.dF(t).

La probabilit6 pour que le d61ai d'attente soit supgrieure ~t t donnd est :

(s) P(> t)= I - l~(t).

Nous supposons essentiellement q~l(z) et ~2(z) holomorphes au point z = 0, ou, ce qui revient au mgme, nous supposons qu'il existe un nombre r6el positif tel que ces fonctions soient analytiques pour [R(z)[ < ~, R(z) d6signant la valeur r6elle de z. Cette hypoth~se, peu restrictive, correspond aux probl~mes pos6s dans la pratique, et permet d'utiti- set la th6orie f6conde des fonctions analytiques.

2 1 5 - -

3/12 1,. tu CALL [ANNAn~S DSS T~.L~co~mrmcATmNs

B]~FI~I1RENCES B I B L I O G R A P H I Q U E S tantes. Soulignons que le service ordinaire n'est

Le cas du choix au hasard a d6j~ 6t6 6tudi6 dans le cas des guichets avec arriv6es poissonniennes, et dur6e de service exponentielle, par C. Palm (vers 1938), puis E. Vaulot [14]. Les 6quations ont 6t6 r6solues par F. Pollaczek [12]. Le cas d 'un seulgui- chet avec dur6e de service constante, susceptible d 'une solution simple par r6currence, a 6t6 ~tudi6 par P. J. Burke [2] et par nous-m~me [7].

Ensuite, nous avons trait6 le cas des arriv6es poissonniennes avec dur6e de service ob6issant h une loi Fl(t ) quelconqne [8], puis le cas relatif h un processus d'arriv6e rdg6n6ratif quelconque [8 bis].

Enfin, nous avons trait6 le cas de s guichets avec dur6e de service exponentielle et processus d'arri- v6es r6g6n6ratif quelconque, ainsi que celui de s guichets h dur6e de service constante avec arriv6es poissonniennes [9].

Le cas du service par groupes pour I guichet a 6t6 6tudi6 h l'origine par N. T. J. Bailey [1] et F. Down- ton [5] dans le cas d 'un guichet permanent avec arriv6es poissonniennes, et choix dans l'ordre des arriv6es.

Nous avons ensuite 6tudi6 le cas g6n6ral des trois types de service par groupes avee choix dans l 'ordre des arriv6es ou au hasard pour des arriv6es poissonniennes, ainsi que le cas d 'un processus d'arri- v6es r6g6n6ratif quelconque pour un choix dans l'ordre des arriv6es [10].

Le cas des arrivdes en groupes a 6t6 6tudi6 h l'origine par D. P. Gaver [6]. B. W. Conolly [4] a trait6 le cas de groupes de taille constante avee dur6e de service exponentielle, et J. W. Cohen [3] a trait6 le cas des arriv6es de groupes poissonniennes avee dur6e de service ob6issant h une loi quelconque. C'est d'ailleurs le travail de ce dernier auteur, travail pr6sent6 comme une application int6ressante de sa thdorie des chaines de Markoff d6riv6es, qui nous a donn6 l'id6e d'envisager ce type d'arriv6es [10 bis]. Nous indiquons, plus loin, comment ce problbme, pour 91(z) et q%(z) arbitraires, se ram6ne au cas des arriv6es isol6es.

L'ampleur du sujet nous force '~ supprimer toutes les d6monstrations. Elles sont rassembl6es dans un ouvrage en pr6paration [lJ], avec de nombreuses eourbes.

Signalons que la m6thode qui nous a paru la plus f6conde et qui nous a permis de traiter toutes ces questions est celle utilis6e h l'origine par F. Pol- laczek : cf., par exemple, [13]. Elle repose essentiellement sur les propri6t6s de sommes de variables al6atoires ind6pendantes, et sur la notion d'indiea- teur d'6v6nement.

Nous nous bornons h donner les r6sultats prineipaux ~ l 'annexe I pour le choix dans l 'ordre des arriv6es et h l 'annexe II pour le choix au hasard. Nous en faisons l 'application, h l 'annexe III , au cas fr6quent de la dur6e de service constante avec arri- v6es poissonniennes. Dans le texte proprement dit, nous allons nous limiter h quelques formules impor-

qu 'un cas particulier du service par groupes (s = t).

A. CAS DE I G U I C H E T .

1. Arrivfies isolfies et service par groupes de s visiteurs.

La densit6 des arriv6es est :

(9) c = s7 I.

Dans le cas du choix dans l'ordre des arriv6es, il nous sera commode d' introduire la fonction r t6ristique (l)o(z) de l 'a t tcnte subie par un visiteur quelconque devant s guichets avec affectations pr6- d6termin6es : cf. annexe I A. D6signons par P o e t T o la probabilit6 d 'a t tente et le d61ai moyen d 'a t tente correspondants. (I)0(z), P o e t T o sont donn6s respee- t ivement par les formules (IV.8.1), (IV.8.2) et (IV.8.3) de l 'annexe I.

Dans le cas de s guichets ordinaires avec dur6e de service constante, nous avons automat iquement le m6canisme de l 'affectation pr6d6termin6e. ~o(z), Po et T o ont alors les expressions, bien connues, donn6es jadis par F. Pollaczek, puis Crommelin.

a) Guichet permanent. La formule (IV.8.6), annexe I, nous donne pour

la [onction caract&istique de l'attente, dans le cas du choix dans l'ordre des arriv&s :

( lo) �9 o~(~) = ~ (~) - 1 -r

?l(z) et ?2(z) sont quelconques. Nous d6signons par Fv(t) la fonction de r6parti-

t ion de l 'a t tente correspondant h r et nous posons :

Pv(> t) = i -- Fv(t).

Dans le cas du choix au hasard nous indiquerons une [ormule asymptotique tr6s pratique valable pour ~ voisin de 1, (1 - - 7 ) n'~tant pas trop grand.

Posons :

(11) �9 y(x) = 2k/~. KI(2V~),

off Kl(z ) est la fonetion cyclindrique de Schl~ifli, d'ordre I :

fo (12) �9 Kl(z) = e--zcbt.cht.dt.

Dans la r6f6rence [11], la fonction y(x) est donn6e par la courbe de la figure IV.9.7.

Dans le cas des arriv&s poissonniennes, nous trouvons en g6n6ral, d'apr~s (IV.12.20), annexe II :

�9 Pv(> t) N y(~ot),

2(1 - 7) 2(1 - 7 ) (i3) ~3 o ~ ' ~ ( o ) - ( , - t ) [ , = , ~ + t / ~

oh ~2 est la variance de la dur6e de service.

�9 Ce signe typographique est utilis6 pour distinguer le~ formules principales encadr6es sur le manuscrit.

- - 216

t. 16, n~ 9-10, 1961]

Cette formule convient en fait pour v I > 0,7 et mfime pour ~ > 0,6.

Prenons le cas d'une dur& de service constante. Par suite d 'une particularit6 pr6sent6e par la fonc- t ion caraet6ristique [eL annexe III, A)], la formule pr6c6dente devient

(14) P~(> t) ~ y[~3o(t + 1)] = y[2(l -- ~q)s(t + 1)].

Par comparaison avec les courbes 6tendues, dres- s6es par P. J. Burke [2], pour s = I et au facteur ~q pros, nous trouvons que, pour une erreur relative (par exc6s) de 50 % environ sur la valeur de Pv(> t), la zone d'application de la formule pr6c6dente pour s ~ 1, est :

I p o u r ~ = 0 , 6 : 0 , 5 < t < 1 0 ;

p o u r B = 0 , 8 : 0 , 4 < t < 2 5 ;

p o u r B = 0 , 9 : 0 ,3< t < 1 0 0 .

Dans le eas de la dur6e de service exponentielle, la zone d'application est encore plus 6tendue.

Dans le cas du service par groupes, nous avons normalement ~ > 0,6, et les valeurs de t envisag6es sont g6n6ralement comprises entre I e t t0. La/ormule asymptotique (13) et les /ormules apparent&s comme 14 suffisent donc largement.

Notons que, dans le Gas du choix dans l'ordre des arriv6es, les formules (IV.8.5) et (IV.8.11) nous donnent :

(t5) Pv (> ~') ~ A .e-~o(tl.

O~ Lo~ P#(> t)

,u ~asard

c h o t ~ ,4a..r ~ t o r d r e

~eY: a r r l ~ , d e ~

Fro. I . ~ Formes compar6es de la fonction de r6partition de l 'a t tente (en ordonn6es logarithmiques), dans le cas des r dans l 'ordre des arriv6es et au hasard.

La figure i , oft nous portons en ordonn6es Log Pv ( > t ) d6duit de (13) et de (15), montre que Pv(> t) est plus grand dans le cas du choix au hasard, pour t assez grand. Le choix au hasard est plus dd/avorable pour les attentes assez longues. (Rappelons que le d61ai moyen d 'a t tente ainsi que la probabilit6 d'attente ont m~me valeur pour les deux lois de choix).

b) Guichet ordinalre [onctionnant di's l'arrivde d'ttn visiteur.

Pour 9x(z) et ~2(z) quelconques, les d6veloppe- ments math6matiques sont tr~s longs.

Toutefois, dans le cas des arriv&s poissonniennes ou d'une dur& de service exponentielle, nous avons :

(16) �9 P(> t) = p , . p~ (> t),

s u n QUELQUES PROBLEMES D'ATTENTE RI'CENTS 4/12

oh Pv(> t) correspond au cas du guichet permanent. Cette relation est valable pour les deux lois de choix : choix dans l'ordre et choix au hasard.

Dans le cas des arriv&s poissonniennes, Fl(t ) 6rant quelconque, nous trouvons pour la probabilit6 d 'a t ten te [cf. formule (IV.8.23), annexe I[ :

C (17) p~ - =

+ ~ , ( - ~).Oo(- c)" Dans le Gas d'une dur& de service exponen-

tielle, F2(t) 6tant quelconque, nous trouvons :

I V.~(_ 1 ) (18) P , = l + [?2(-- 'l ) -- ?2(-- d)]l(t -- d) '

d 6tant le nombre r6el unique tel que :

i - - ~t = [ ~ , ( - - d)i', (t9) 0 < d < I.

Nous avons alors :

(20) P v ( > t) = e -at .

Dans la r6f6renee [ l i] , nous donnons d, dans le cas des arriv6es poissonniennes, par les courbes de la figure (IV. 2.3).

e) Guichet ordinaire ne [onctionnant qtt'en prdsence d'un groupe complet de s visiteurs.

La probabilitd d'attente P a pour expression, d'apr~s la formule (IV.8.16), anuexe I :

(21) �9 i - - P = ( l--Po)/S.

De m~me, la formule (IV.SAT), annexe I, donne l'expression suivante, pour le ddlai moyen d' attente T:

(22) �9 T = T O + (s-- l)12s-q. Dans le cas du clioix dans l'ordre des arriv6es,

P ( > t) est donn6e par (IV.8.15), et dans le cas des arriv6es poissonniennes par (IV.8.19) pour t grand.

Dans ce cas des arriv&s poissonniennes, nous avons g6n6ralement [~o < c, pour ~ > 0,7. Dans ces conditions, nous trouvons pour l'expression asymptotique de P ( > t), dans le cas des deux lois de choix :

(23) P(> t) ~ ~.Pv(> t),

off Pv(> t) correspond au eas du guiehet permanent.

2. Arr iv6es e n g r o u p e s a v e e serv ice ord ina ire .

Nous nous limitons all cas (Pun guichet ordinaire. La taille d 'un groul)e d'arriv6es a une proba-

bilit6 r d'etre 6gale h k, probabilit5 ind6pendante du processus d'arriv6cs el de la la;/le des groupes pr6c6dents.

Nous posons pour [u I < ] :

oo (24) ~(u) = Y ~k . , , ~.

1;=l

La taille moyenne des groupes est :

(25) a = g' (t)

La dur6e moyenne d 'un intervalle d'arriv6es de groupes est : al~. Le taux d'oecupation du guichet est donc "q.

- - 2 t 7

5/12

Le rdsultat /ondamental est le suieant, pour un choix dans l'ordre des arriv~es :

pour l'dtude du d61ai d'attente subi par le pre=

mler visiteur choisi dans le groupe, tout se passe comme si nous at, ions des arrivdes isoldes et un service ordinaire, ~ condition de/aire les substitutions :

I ~,(~) -~ g[~(~)], (%) ~(=) -~ ~(=).

B . - CAS D E S G U I C H E T S O R D I N A I R E S AVEC S E R V I C E O R D I N A I R E

(Arriv~es isol6es) - - Choix au hasard.

Nous ne parlerons que des deux cas simples et fr6quents, eorrespondant h des dur6es de service exponentielles et constantcs.

Le cas du choix daBs l 'ordre des arriv6es 6taut eonnu, nous n'envisagerons que le cas du choix au llasard.

La densit6 des arriv6es est : c = s~. Aut rement dit, nous avons :

(27) q)~(O) - ] It,

est alors lc taux d 'occupat ion de chaque guichct.

i . Durfie de service exponentielle.

~. est quelconque. La formule 03) est encore valable, avec

(2s) ~0 ~_ 2(1 - ~)/ ,~(0) . Autrement dit, si P c s t la probabilit6 d 'a t ten te ,

nous avons l 'expression asymptot ique, pour v~ > 0,7 environ :

(29) . P (> t) ~ P.y(~ot).

2. Dur~!e de service constante avee arriv~es poissonniennes.

D6signons P ( > t) par P~(> t) daBs le cas de s guichets. Nous avons le r6sultat impor tan t sui- van t [formule (5a), annexe III l , pour t > 5Is environ :

(30) �9 P~(> t) ~< P , ( > st)lK~ , off K,, d6fini par la formule (3a), annexe III , est donn6 par les courbes des figures u et V.4.7, r~f6rence [11].

Nous avons d'ailleurs pra t iquement l'6galit6 pour ~l > 0,7, ainsi que daBs le cas du choix dans l 'ordre des arriv6es.

L a relation (30) permet d'utiliser, pour le cas de s guichets, les courbes 6tendues donnant P a (> t) dabs le cas d 'un guichet, Stablies par P. J. Burke [2] (*).

A P P L I C A T I O N A LA TI~.L~PHONIE

En commuta t ion t616phonique automatique, l'u- sage des courbes de Crommelin est classique pour le dimensionnement des organes de commande, notam-

(*} DaBs [7], nous avions 6tabli les courbes P (> t), pour t < t5, daBs le cas d'un guichet permanent, doric au facteur ~l.pr6s, le visiteur 6taut suppos6 arriver apr6s une fi,, de service.

P. LE GALL [ANNALES DES T~,L~.COMMUNICATIONS

ment dabs les syst~mes crossbar. Elles correspondent au cas de s guichets ordinaires avec dur6e de service constante et arriv6es poissoniennes et service ordinaire, mais avec un choix daBs l 'ordre des arriv6es. DaBs la pratique, cette loi de choix est loin d'gtre r6alis6e, et les courbes de Crommelin donnent mal- heureusement des r6sultats t rop optimistes. II est plus prudent de prendre l 'hypoth~se du choix au hasard.

Consid6rons, par cxemple, 2 marqueurs contrS- lant un groupe de s61ection conjugu6e h trois 6tages de liaisons, c'est-h-dire h 4 6rages de commutateurs . Ils r%oivent les appels venant des enregistreurs h travers 1 ou 2 6tages de commutateurs . Le m6eanisme est pra t iquement tel que, pour plus de i ou 2 appels en at tente, le cholx se fait p ra t iquement au hasard.

Le temps d'op6ration des marqueurs est suppos6 g t re : 0,4 s. Combien d'appels peuvent-ils 6couler h l 'heure charg6e, avec la condition

P2(> t s) = 10 - 4 ?

En prenant pour unit6 de temps le temps d'op6- rat ion, nous avons : t = I / 0 f t = 2,5. Nous pouvons appliquer (30) :

t P~(> 2,5) ~ ~ . P I ( > 5).

Si nous avions le cas du choix daus l 'ordre des arriv6es, nous devrions prendre ~1 = 0,4 ; d'ofi:

7 200 appels 6coul6s h l 'heure charg6e. Au contraire, nous devons prendre le cas du

choix au hasard, et nous avons : ~ = 0,24 ; d'od : 4 300 appels h l 'heure charg6e. DaBs cet exemple, les courbes de Crommelin

donnent un hombre d'appels dcoulds presque deux lois plus grand que le nomlre d'appels ef[ecti~e- ment dcoulds. Le /ait de dgdoubler systdmatiquement les marqueurs, pour des raisons de sdcuritd m~cani- que, peut ~tre aussi une n&essitd pour des moti/s d'ordre statistique.

A N N E X E I

Ex t ra i t de la R6ffirenee t J Section IV.8

R A P P E L D E S P R I N C I P A U X R ~ , S U L T A T S D A N S LE CAS D U CHOIX D E S V I S I T E U R S

D A N S L E U B O R D R E D'ARRIVi~,E

Signalons tou t d 'abord que la r@artitlon de la longueur de la queue, le ddlal moyen d'attente, et la probabilitg d'attente, daBs le cas du r6gime stationnaire, sont ind@endants de la Ioi de choix des r teurs.

I1 suffit, pour le volt, de se met t re fi la place du ou des serveurs.

Ceux-ci out h effectuer un travail , lequel est ind6pendant de cette loi de choix. I1 en est ainsi de la rdpart i t ion des pdriodes d'occupation ininterrom- pues 6tudi6es h la section (IV.2) (*) et de celle relat ive h la longueur de la queue.

(*) De la r~f6rence [I1].

- - 2 i 8 - -

t. 16, n ~ 9-10, 19611

Mals il en est de m6me des deux quantit6s pr6c6- dentes : la probabilit6 d 'a t tente correspond h l'occupation des serveurs, et le d61ai moyen d 'a t tente correspond h la longueur moyenne de la queue.

Ces quantit6s, dont nous avons donnd les expressions dans le cas du choix des visiteurs dans l'ordre des arriv6es, seront donc valables dans le cas du choix au hasard. De sorte que nous ne les calculerons plus dans les sections suivantes.

Rappelons les principaux r6sultats obtenus dans le cas du choix dans l'ordre des arriv6es.

ARRIV~.ES I S O L E E S

SUR QUELQUES PROBLE/vIES D'ATTENTE Rs 6/12

Le taux d'occupation du guichet est ~ ; 1'unit6 de temps est la dur6e moyenne de service ; la densit6 des arriv6es est donc ~ dans le cas d 'un guichet avec service ordinaire, et c = s~ dans le cas du service par groupes de s visiteurs, ou dans le cas de s guichets avec service ordinaire.

Le d~lai moyen d'attente T O se d6duit de (IV.2.11) :

- -1 (IV.8.3.) T O = ~ - i x

f _ + i c ~ - - 0 ~+o Log [1 -- $~(-- ~).[~,(~)]s] d~.

Dans le cas des arriv&s poissonniennes, nous avons : qa2(z) --~ z).

(IV.2.28) donne alors : S--1

(IV.SA) Oo(~)= (~+ z),-o.~(~)

off les a~ se calculent h partir de (IV.2.29). Nous d6- duisons l'expression asymptotique de la [onction de rgpartition de rattente :

t �9 Fo(t ) ~__ i -- K(s, :q).e-~o t, I $--1

(IV.8.5) avec ~ a . . ( l + ~olC)'~

K(s, ~) = _ s(l + ~olc) 8-~ + coi(~o)'

, e t : ( l + ~ o l c ) " = ~(~o). Po et T o sont donn6s respectivement par les d6ve- lol3pements en sdrie (IV.2.33) et (IV.2.34).

A. Cas de s guichets ordinaires avec service ordinaire et affectation prfidfiterminfie des guichets.

Nous rappelons que le visiteur de num6ro (vs + i), oh ve t i sont des entiers positifs ou nuls [l ~< i ~ s], est affect6 automatiquement au guichet de num6ro i.

Dans le probl~me ordinaire de s guichets, le premier visiteur de la queue est servi par le guichet devenu libre le premier. Ici, au conraire, si ce guichet n'est pas celui affect6 d'avance au visiteur consid6r6, ce dernier a t tend encore.

Le processus envisag6 cst donc plus d6favorable que dans le cas ordinaire de s guichets, les at tentes 6tant plus longues. Toutefois, son avantage r6side dans le fait qu'il peut ~tre 6tudi6 simplement, alors que l 'autre probl~me n'a pas encore 6t6 r6solu de fa~on explicite, vu sa complexit6, mgme dans le cas important des arriv6es poissonniennes (pour une r6partition quelconque de la dur6e de service). Le processus envisag6 donne d'ailleurs des valeurs approch6es par exc~s (ce qui est sufflsant) pour les at tentes relatives au cas ordinaire des s guichets.

Signalons que, dans le cas d'une durde de service constante, les visiteurs, dans le cas ordinaire des s guichets, se t rouvent automat iquement affect6s suivant le processus que nous envisageons.

La rdpartition de l'attente est alors la m~me dans les deux types de processus.

Remarquons enfin que la th6orie ordinaire d 'un guichet correspond h : s = 1.

Dans le cas du processus limite stationnaire, la [onction caractdrlstique de l'attente est donn6e par (iV.2.25), pour R(z) ~< 0 :

(IV.8.1) O o(z) =

l z< t, -- 1 f + ~ - O L o g [ l _ q g , ( _ ~).[~(~)],]~(~ + z)] cxp ~ i ' . / - i ~ - 0

La probabiIit~ d'attente Pose d6duit de (IV.2.9) :

(IV.8.2) Po =

t -- e x p } 9 ~ l i . / 7 i ~ : 0 Log [1 --~01(-- ~).[~0.(~)]$] '~I"

219

UN GUICHET AVEC SERVICE PAR GROUPE DE S VISITEURS

La densit6 des arriv6es est toujours : c = s~.

B. Guichet permanent.

Un tel guichet fonctionne mgme en l'absence de visiteurs, les 6poques de d6but de service 6rant ind6- pendantes du processus des arriv6es.

(IV.4.2) donne la [onction caract&istique de Vat- tente, en r6gime stationnaire :

(IV.8.6) �9 (I)v(z)= ~01(z)--I .r Z

off Oo(Z ) est donn6e par (IV.8A). La fonetion de r6partition de l 'a t tente peut s'6crire :

(IY.S.7) Fv(t ) - -

Fo(u ) et Fl(u) eorrespondant respeetivement ~ O0(z ) et Ol(z).

La probabilit6 d 'a t tente est 6videmment 6gale h t . Le dglai moyen d'attente est donn6 par (IV.4.3) :

(IV.8.8) �9 Tv = To + ~(0)/2,

T O 6tant donn6 par (IV.8.3). La r@artition de la Iongueur de la queue ~ une fin de

service est d6finie par la suite des probabilit6s ff~ ; probabilit6 pour qu'il y ait, en r6gime stationnaire,

visiteurs en a t tente h une fin de service quelconque. Nous posons, pour I x] < 1 :

a~= ~ fix; ),=0

(IV.8.9) ~v(x) = N f~.x~ ; ~=0

oO g~(x) _ Z a~.x~. t - -X ~=0

7/12

(IV.4.i4) nous donne, pour N < ~"

(IV.8A0) fi '(x) 1 t - - x - t - - x

+ ~-~ 'J- ,oo-0 - " " ' i - [ ~ , ( O ] '

x i _ ~,~,(~) �9

Cos des arri~,~es poissonniennes.

L'expression asymptot ique de la fonetion de r6par- t i t ion de l 'a t tente est donn6e par (IV.4.17) et peut s'6crire sous la forme :

(IV.8AI) i -- F,(t) N qh(~0) -- i .[i - - Fo(t)], - - ~o

oh ~o et Fo(t ) sont d6finies par (IV.7.5). ~ (x) est donn6e par (IV.4.20) :

$--1

( i - ~). Z ~x" (IV.8.12) 8,(x) = t - - x. . [~a[-- c (t -- x)]] -x

Nous avons d'ailleurs la relation :

(IV.S.i3) ~ (x ) = Oo[-- c(i -- x)]. ~t[-- c(l -- x)].

P. LE G A L L [ANNALE$ DES TI~LI~COMMUNIedATION$

l (IV.8.18) 9(x) = i + ~ x

I - - x d~ j r + t ~ 1 7 6 1 7 6 r 1 7 6 ~)" ~ ( - ~)" ~"(~1" i - ~,(~)"

Cos des arrivdes poissonniennes.

Nous avons, d'apr6s (IV.5A4) :

Yo(t) = t,

fix(t)= i - - e - a . E x! t t - -O

(IV.5A4) donne, pour l'expression asymptotique de F(t) :

(IV.8A9) �9 t -- F(t) _~ ~ . [ t -- F~(t)l ,-3 (a)'.

t: _ t). E e -a x! + l--s/e-a(st)'2,'-- ( ' t + s =-o "

Fv(t), donn6e par (IV.8AI), correspond au cas du guichet permanent. (IV.8.18) devient, d'apr~s (IV.5.i6) :

(IV.8.20) ~(x) = ~,(x),

o6 %(x), d6finie par (IV.8.i2), correspond au cas du guiehet permanent.

C. Guichet ordinaire, ne d6marrant qu'en pre- sence d'un groupe complet de s visiteurs.

l~ous rappelons que nous entendons par gulehet ordinaire un guichet au repos en l 'absence de visiteur. Ici, le guichet est mgme au repos quand il y a moins de s visiteurs.

La [onction caract&istique de l'attente est donn6e par (IV.5.4), pour R(z) < O :

1 f + ' ~ + O O o ( - ~ ) x (IV.8.14) O(z) = 2-~i" j - l ~ + o s

(Px(-- ( ) . s [r + z)], - - [~,(()]s zd~

Oo(Z ) est toujours donn6e par (IV.SA). Si nous d6signons par Yx(t) la convolution de

num6ro ), de F2 (t), correspondant h la fonction caraet6ristique [O~(z)] x, la /onction de r@artitlon de l'attente est donn6e par (IV.5.8) :

(IV-8-t5) V(t) = ,=t ~ ~',_,(t). 2-~1 x

/ +'~176 *0(-~_~)). ~,(_ ~).[~,(~)],. ~ ' !oo+0 8

La probabilit~ d'attente P e s t d6finie par la rela- t ion (IV.5.5) :

(IV.SA6) �9 l - - P = ( l - - P o ) # ,

off P0 est donn6e par (IV.8.2). Le d~lai moyen d'attente est donn6 par (IV.5.7) :

(IV.SA7) T = T O + (s -- 1)/2c,

off T O est donn6 par (IV.8.3). Pour la r@artltlon de la longueur de la queue, h

une fin de service, la relation (IV.8.t0) a pour homo- logue (IV.5.11) :

D. Guichet ordinaire, d6marrant d~s la pr&ence d'un visiteur.

Le guiehet, susceptible de servir s vlsiteurs simul- tan6mcnt, d6marre, en fait, d6s l'arriv4e d 'un premier visiteur.

(IV.6.9) donne, pour la [onctlon caractgristlque de l'attente :

(IV.8.2t) O(z) = (t -- P) + zD(z).e,(z).

r d6finie par (IV.8.6), correspond au cas du guichet permanent. D(z) est une fonetion holomorphe pour R(z) ~ 0, diilleile h expliciter dans le cas g6ndra].

Si s est rationnelle, r a pour expression : (IV.6.t6). Si 01(z) est rationnelle, r a pour expression �9 (IV.6.27).

Pour la longueur de la queue, & une fin de service, la relation reliant 9(x) et r est donn6e par (IV.6.30).

Cas des arrivges poissonniennes.

(IV.6.21) donne pour la [onctlon de rgpartltion de l'attente :

(IV.8.22) �9 F(t) = ( l - - P ) + P.F~(t),

off Fv(t), correspond au eas du guichet permanent. La probabilltg d'attente P e s t

donn6e par (IV.6.22) :

(IV.8.23) �9 P = ~/[~ + ~, ( - ~).r ~)3, off Oo(-- c) se ealcule h l'aide du d6veloppement en s6rie (IV.6.23). Le dr moyen d'attente est donn6 par (IV.6.24) :

(IV.8.24) �9 T- - P.Tp,

--- 220 - -

t. 16, n ~ 9-10, 1961]

off T~, donn6e par (IV.8.8), est la duroc moyenne de l 'a t tente dans le cas du guichet permanent.

Pour la longueur de la queue, (IV.6.31) donne nouveau :

(~v.8.25) ~(~) = g,(~)

off 9~(x), d6finie par (IV.8.12), correspond au eas du guiehet permanent.

SUB QUELQUES PROBLEMES D'ATTENTE II~CENTS 8/t2

N o t a . - - t o Les relations (IV.8.22) h t(IV.8.25) sont ind6pendantes de la loi de ehoix des visiteurs, saul Fv(t).

2 ~ Nous verrons, h la section (IV.13), que les relations (IV.8.22) et (IV.8. 25) sont encore valables (pour d 'autres expressions de F,(t), 9~(x) et P) darts le eas de la dur6e de service exponentielle, O,(z) 6taut quelconque.

ARRIV]~,ES E N G R O U P E S

Le guiehet est ordinalre (done au repos en l 'absence de visiteur) et le service est ordinaire.

La taille des groupes d'arriv6es est variable. La probabilit6 pour qu'elle soit 6gale h k est n~.

Nous posons, pour [u I < t.

g(u) • ' "~__t ~ . u ~,

(IV.8.26) ~ oo u~ f ~ g ( ~ )

Nous avons :

c o

g( l ) = G ' 0 ) = I ; g ' 0 ) = Z A~k = . . k~l

a est la taille moyenne des groupes d'arrlvdes. Les 6poques d'arriv6es de groupes sont celles d 'un

processus r6g6n6ratif, ~02 (z) 6taut toujours la fonction caract6ristique des intervalles entre arriv6es successives, ceux-ci ayant pour dur6e moyenne : a[~.

Le taux d'occupation du gulchet est done toujours : ~ ( < t).

La taille des groupes est suppos6e ind6pendante du proeessus des arriv6es de groupes.

Pour l'~tude des pdriodes d'oeeupation ininterrom- pues, et pour eelles de l'attente du premier vtsitetn" ehoisi dans ehaque groupe, tout se passe eomme si nous avions un service ordinaire avee les substitutions :

de l 'a t tente subie par un vlslteur quelconque est donn6e par (IV.TA0) :

(IV.8.29) �9 O(z)= ,:I),(,.). I c[,~,(,.)] - C(t) II['P,(") - - q.

Le ddlal moyen d'attente est donn6 par (IV.7.1t) :

(IV.8.30) T = T~ + (a - - 1)12 ,

off T 1 est l 'a t tente moyenne subie par le premier visiteur ehoisi dans le groupe.

La r6partitlon de la longueur de la queue h une fin de service queleonque, toujours d6finie par la fonction g(x) [ef. (IV.8.9)], est donn~e par (IV. 7.t7) pour Ix] < 1 :

1 (Iv.8.3~) g(~) = ~ i x

f + ~ + 0 r r~ ~ [ ~ ' ( - ~)] - g(x)

t - g(~) .d~

Cas des arrivdes polssonniennes.

(IV.7.20) donne pour le premier vislteur choisi dans ]e groupe :

(IV.8.32) �9 (I),(z) = (1 --B) •

azlJ ~ + az - - "0. g[~,(z)] }~

Le ddlal moyen d'attente, subi par ce vlsiteur est :

(IV.8.33) T1 ffi 2(t ~ [-g"(t) ] - - + + ; ( o ) . �9

Par analogie avec (IV.2.18), l'expresslon asymptotique de la fonction de r6partition de l 'a t tente de ce premier visiteur du groupe est :

(IV.8.34) ~-,(t) ~ i - (~la)~i(Po).g'[q)i(Po)]-I oO--~o'

off ~o, r6el et positif, est tel que :

(IV.S.35) g[~,(P0)] = t + aP0/~.

La r6partition de ]a longueur de la queue, h une fin de service queleonque, est donn6e par (IV.7.23).

t--v} y%(--y) g(x)= "q <p , ( - - y ) - - x

avec : Ixl < 1,

(IV.8.36) y = (n /a) .V -- ~-(x)].

( I V . 8 . 2 7 )

Dans le cas du processus llmlte statlonnalre, nous trouvons done, compte tenu de (IV.8.1) avec s = 1, pour la fonetion caract6ristique de l 'a t tente subie par le premier vlslteur choisi dans chaque groupe :

(IV.8.28) �9 q)l(z)=

~ - t f + ~ o o - 0 zd~ 1 exPt 2-~iJ-ioo-0 Log [1 -- g[?,(-- ~)]. ~s(~)]. ~(~ + z)',

Dans le cas off les visiteurs d'un m~me groupe sont cholsis au hasard, ]a fonction caract6ristique

ANNEXE I[

Extra i t de la R6f6rence t t Section IV. t2

R A P P E L DE S P R I N C I P A U X B ] ~ S U L T A T S D A N S LE GAS

D U C H O I X DES V I S I T E U R S A U H A S A R D

S'il y a v visiteurs h choisir h un d6but de service, chacun a une probabilit6 l / v ou sly d'gtre choisi, suivant que le service s'effeetue ordinairement ou par groupes de s visiteurs.

221

9/12 P. LE

Nous n'envisageons que le cas du processus limite stationnaire.

L a densitd des arrivdes est ~q ou c = s~q, suivant le type de.service consid6r6.

A. Service ordinaire aveo prooessus d'arrivfies rfig~nfiratiI que leonque .

D6signons par (I)z(z) la fonction earact6ristique de l 'at tente, dans le cas du choix des visiteurs dans l 'ordre des arriv6es, fonction donn6e par (IV.2.8), ou (IV.8.t) pour s = 1.

Nous posons, d'apr~s (IV.10.5), pour R(z) ~< 0.

(IV.12.t) J0, ) =

I ! / '+Ic~176 q)"l ?2(q) de �9 7~ ~ 2~i ~, - l ~ - 0 - - ?2(q) q - -

avec :

B(z, q) = ~ 2(-- q) . T,(-- q). [?2(q) -- ~2(z)].

Nous posons, en outre, d'apr~s (IV.10.t9) et toujours pour R(z) ~< 0 :

(TV. t%2) r z) =

t f - l ~ - O A ( z , q ) u?=(q) dqz ' 2=--] . / - , ~ - o 1 --u-~o2(q)" q +

avee :

A(z, q) = (I)2(-- q). [(~1(Z) - - ~1(-- q)].

La /onction caractdristique de l'attente est alors, d'apr6s (IV.t0.21), pour R(z) < 0 :

(IV.12.3) (I)(z) = Q + (I)(l, z) - (I)a(Z),

avec :

(I)~(z) = (z) ~------~---.exp . K(v, z) .du,

H(u, z) = t f + ~ + 0 ( ~ , ~ + r ) . a - - ~ , ( - ~ ) d~

Q + 2r:~]" J - ,oo+o u[l -- u~2(-- r)]" 7"

Q --~ t - - p est la probabilit6 de non at tente donn6e par (IV.2.9) ou (IV.8.2) pour s -~ t.

N o u s pouvons encore 6crire :

(IV.t2.4) �9 (I)(z)=

d v du. K(u, z)

K(x, z) a pour expression (IV.10.15) :

K(x, z) = x - ~ ~(z) +

(IV.12.5) t . f + l o o + o J(l, -- r)

J-Ico+o q)l (z-l- r). ~(t: O)) •

"I - - X d r

t - x ~ ( - ~)" 7 '

xo(z ) est la racine unique, pour R(z) < 0, de l'6qua- t ion en x : K(x, z) = 0, dans le domaine lxl ~< t .

Pour obtenir la fonetion de r6partition de F(t), nous consid6rons le point singulier de r le plus proehe de l'origine. Ce point z = z x est r6el et tel

G A L L [ANNALES DES TI~LI~COMMUNICATiON$

que z 1 > 0. I1 correspond ~ une racine double de l '6quation en x pr6c6dente, et c'est un point cri- t ique pour x0(z ).

Coupons le plan complexe z par une demi-droite, issue du point z = - Zl, et longeant l 'axe r6el ind6finiment vers les abscisses n6gatives.

D6signons par [31(z) la d6termination de xo(-- z), au voisinage du point critique z = - Zl, dans le demi-plan sup6rieur, et par ~l(z) sa d6termination dans le demi-plan inf6rieur.

Dans le plan complexe u, coup6 par une droite issue du point [3a(z) et passant par =l(z), consid6rons un chemin d'int6gration C~ par tant de ~1 en longeant la coupure, contournant le point [31 dans le sens direct, et re tournant vers ~1 en longeant l 'autre bord de la coupure.

Nous posons, d'apr~s (IV.9.28) :

(w.12.c)

t [ - z) .,xp l f ~ d" I M(z) = 2-~i" fie= ~-u K(,,--z)

Cette fonction est d6finle au voisinage du point (-- =1).

En d6signant par Hl(t ) l'originale de [Q + r z)],

nous trouvons d'apr~s (IV.10.29), pour la [onction de r~partition de l'attente, dans le cas off cette a t tente n'est pas trop faible :

(IV.12.7) F(t) ~ Hx(t) -- f / ~ ' e a. M(z) dz e 2r:lY(z) - - J_ z j - - Zl

avec :

(IV.t2.8) T(z) = t / ~ K [ [ 3 1 ( z ) , Z]

3x

La formule (IV.12.7) est exacte, pour t queleonque, dans le eas de la dur6e de service exponentielle avee arriv~es poissonniennes.

Elle suppose, en outre, que r n'a pas d 'autres points singuliers sur la droite x = - - z 1 ; et que Xo(--z) est prolongeable h gauche de ce point (--- zl).

L' expression asymptotique de F(t), pour ~} pas trop voisin de 1, est donn6e par (IV.9.37) :

(IVA2.9) F(t) "~ 1 -- M(-- z,) .(e-*,t/Zlt) .J(t) ;

avec

J(t) = y[(Bv/t]2)2],

- - 1 6 3 lta y ( x ) = ( 2 . V / ~ : 1 3 . ) z I . e - �9 ,

- - 2 1 ' /= B 7~ ,,) ; ~K(bzxl, . ~x = ]

off xx = Xo(Zl).y(x) est donn6e par hs courbes des figures (IV.9A) h (IV.9.4).

Le cas des arriv6es poissonniennes est plus simple. Nous allons le volt, comme cas partieuller du service par groupes (s : - 1).

222

t . 1 6 , n ~ 9 - 1 0 , 1 9 6 1 ]

Autre /orme de la [onction caract&istlque de l'attente.

Posons pour Is[ ~ ] et R ( z ) < 0, d'aprgs (IV.I0.46) h (IVAO.49) :

SUR QUELQUES PROBLEMES D'ATTEiNTE RECENTS t0/t2 Comme pr6c6demment nous d6finissons, dans les

mgmes conditions, les quantit6s zl, x 1 = Xo(Z~) , xo(z), ~l(z), avec ]a mgme coupure effectu6e pour rendre uniforme la fonction x0(-- z).

Posons : (IV.12.10)

]~,,,s M(u,z) l / ' d~ I ~(s, z) ~ exp .d u . (~) N(,~, N(~,, z) ;

avce N(,, ~) =

1 t + i o o - 0 0 ( t , _ r)

1. - - s dr I - - s ? , ( - - ~) - .?~(z + "~" --r

t / . [ O ( i , - 1.) M(s, z) = 2 ~ . ~ , O ( 1 , 0) x

?~ (z + r) dr (i - .~.). [~ -- s ? ~ ( - r)] "r + z

que :

R(r) < 8 + n(--~);

pour R(z) < 8. unique, pour R(z) < O, de z) = O, dans le domaine

La droite C~ est telle

0 ~< R(-~) <

?2(z) 6tant holomorphe So(Z ) est ici la racine

l '6quation en s : N(s, t*I ~< i.

D6signons par G(y) la fonction (IV.2.47), ou encore (IV.8A8) pour s = t.

La fonetion earaet6ristique de l 'a t tente peut encore s'6erire, d'apr~s (IV.10.52) :

I "~%Gi~) . f2(x,z) .dx, (IV.12.1t) alp(z)= Q- -2~ i ,

off Q est la probabilit6 de non attente. C~ est une courbe entourant l'origine dans le sens direct, dans le domaine : ~ < Ix] < 1, y = i / ~ 6tant le point singulier de G(y) le plus proche de l'origine (s~ r6el).

S E R V I C E

P A R G R O U P E S D E 8 ~ r I S I T E U R S A U M A X I M U M ~

A V E C A R R I V I ~ E S P O I S S O N N I E N N E S .

B . G u i e h e t p e r m a n e n t .

Pour des at tentes pas trop faibles (quelconques pour s ~ 1), nous avons la /onction caractdristique, d'apr~s (IV.tl .15) :

~ 1 8bts--1 (IV.t2A2) Or(z) = . ~o(~) H(u, z). ~ ) x

/ .d,,,

a v e c : S- -1

( 1 - U). Z a~W ~ 0

I-[(/~, Z) = ( ~ 1 [ _ _ C ( 1 _ _ ~ ) ] _ /~" X

(~l[Z - - 0 (~ - - ~l,)] - - ( ~ 1 [ - - 0 ( 1 - - U)]

Lt s - 1 , Z

(IV.12.13)

K(x, z) est donn6e par (IVAI.6) :

(IV.t2.14) K(x, z) - : r ' -- ?,[z -- c(t -- z)].

(IV.12.15) q = - - z + c(l --x).

A Xo(Z ) correspond qo(z). A ~l(Z) correspond ~(z), la d6termination de

q0(- -z) , dans les m~mes conditions. (IV).9.29, donne, pour t pas trop faible, la [onction de rdpartition de l'attente Fv(t) : ee n'est autre que (IV.12.7), o~ ,((z) se r6duit h ~'(z).

la

Express ions asymptoHques de F,,(t ).

a) ~ nettement diff&ent de t . ql = qo(Zl), nombre r6el, se d6termine h l'aide de relation (IV.I 1.17) :

1 (1V.12.16) ?[(-- ql) = ~ .[71(-- ql] (s-1)l~.

Nous d6duisons la relation (IV.1t.22) :

(IV.12A7) X , - - :l~0(gl) = [ f ~ l ( - - ql)] 1Is"

Zl, r6el et positif, est d6fini par ([V.12.15) :

( I V , ~ 2 . ~ 8 ) Z 1 = O ( l - - X l ) - - q l ,

L'expression asymptotique de F,p(t) est donn6e par

s - - I - - �9 [ g x ( - - q~)]-q" ~qs

(IV.12.9), avec [el. ( IV. l l .2 i ) ] :

(IVA2.19) B = ~ x

~ ; ( - q,). % , ( - q d l < q s ) - I _

b) =q voisin de I. (~ > 0,7).

L'expression asymptotique de Fv(t) est donn6e par (IV.11.23) :

1 - - Fv(t ) ~ y(~0t), (IVA2.20) �9 avec :

y(x) = 2V/x. K,(2V/x ),

oh Kl(z ) est la fonetion cylindrique de Schlafli, d'ordre I :

(IV.12.21) K~(z) = f + o o e--zeat . c ht . d t. JO

La figure (IV.9.7) donne la courbe y(x). L'expression asymptot ique de ~3 o est donn6e

par (IV.11.24) :

2(i - ~) (iv.12.22) �9 ~0~-- ?~(0) - ( s - t) / ,"

Dans le cas off s esr grand, ~ est voisin de l ( > 0,7 par exemple). La simplicit6 et la g6n6ralit6 de l'expression asymptot ique (IVA2.20) lui donne toute son importance.

- - 2 2 3 -

t /i2 Cas dtt service ordinalre (s = l).

(IV.t2A6) devient, pour d~terminer q t :

(IVA2.23) ~ ( - - q~) = 1/~;

(IV.i2. i9) s'~crit :

(IV.t2.24) B = ~ V ~ . ~ ( - q~).

(IV.t2.22) donne :

(IV.t2.25) {3o 2 0 -

C. Guichet orflinaire fl6marrant fl~s l'arrlvfie fl'un vislteur.

La fonction de rgpartltlon de rattente est donn~e par (IV.8.22) :

(IV.i2.26) �9 F(t) = ( t - - P ) + P.Fv(t),

o/h Ft(t) correspond au cas du guichet permanent, dans le eas du ehoix au hasard.

Rappelons que la probabilit6 d 'a t tente P est donn~e par (IV.8.23).

ANNP.X~. I I I

CAS ~ES GUICHETS A ~)UBI~.E DE SERVICE CONSTANTE

AVEC ARRIV~ES POISSONNIENNES ISOL]~ES

A. Cas de s guichets ordlnaires avec service ordinaire.

La densit6 des arriv~es est c ~-s~q, ~1 ~tant le taux d 'occupation de chaque guichet. L'unit6 de temps est la dur~e d 'un service.

Le cas du choix darts l 'ordre des arriv6es est elassique et a 6t6 trait6 ~ l'origine par Pollaczek, puis Crommelin.

L '6tude de ee eas est simplifi6e par le fait qu'il y a au tomat iquement affectation pr6d6termin6e des gulehets : el. annexe I, paragraphe A.

Faisons quelques remarques d'ordre pratique. D6signons par r o le hombre r6el unique tel q u e :

! "~ro > t, ~]ro. e--mr. = ~. e---~.

D6signons par Px la probabilit6 pour qu'il y ait ;~ visiteurs en pr6sence h un instant que]conque, et posons :

=

Posons en outre t

$--1

(3a) �9 l l g s = ]E a~r~ls( t- ~).ror-~.

K,, plus grand que t , est donn6 par les courbes des figures (V.4.6) et (V.4.7) de la r6f6rence [ i i ] .

Dfisignons par P s ( > t) la probabilit6 pour que l 'a t tente soit sup6rieure h t donn6, dans le eas de s guichets.

P. LE G A L L [ANNALES DES TI~LII~COMMUNICATIONS

En consld6rant l 'expression asympto t ique de Ps (> t), nous eonstatons que, darts le eas du choix darts l' ordre des arrivges, nous pouvons 6crire :

s i t > 3 # environ. Ps(> t) _~ PI (> st)/Ks.

Cette relation, sufflsante pour la plupar t des cas pratiques, permet de se ramener au cas d 'un seul guichet (courbes de Crommelin), connaissant K r

Dans le cas du cholx au hasard, nous d6montrons [cf. [9], et section (IVA9) de f i l l ] de mgme, pour ]a m~me zone de valeurs de t :

(5a) �9 P , (> t)_____ PI (> st)/Ks,

l'6galit6 6taut prat iquement r6alis6e pour ~ > 0,7. Iei encore il sufl]t de eonnaltre P~(> t), dans le cas du ehoix au hasard.

Signalons que, dans le cas d 'un guichet, la fonction caract6ristique de l 'a t tente (IV.t2.12), annexe II (pour s ---- t), pr6sente une infinit6 de points slngu- liers sur la droite x ----- zl, z 1 6taut le point singulier de Or(z) le plus proche de rorigine. D'ailleurs, nous pouvons 6crlre :

r =

off ~(z) reste inchang6 par la subs t i tu t ion : z -+ z _-4- 2n=|, n 6taut cutler. I1 s 'ensult que ]a formule asymptot ique (IV.12.20), annexe II, devlent icl, compte tenu du fait que le guichet est ordinaire :

(6a) �9 P , (> t) ~ ~].y[2(t-- ~)(t + 1)].

Nous donnons darts le texte les limites de validit6 de eette formule.

B. Cas de 1 guichet avec service par groupes de s visiteurs au maximum.

La densit6 des arriv6es poissonniennes est tou- louts : c = s~. De mgme l'unit6 de temps est tou- louts la dur6e d 'un service.

t o Guichet permanent.

Si To est le d61ai moyen d 'a t ten te darts le eas pr6c6dent de s guiehets ordinaires avee service ordinaire, nous trouvons, darts le cas pr6sent, pour dglai moyen d'attente :

(7a) �9 T v = T o+112,

d'apr~s la relation (IV.8.8), annexe I. Posons :

(8a) �9 K's = (r~-- l)l[gs.s~(r o - 1)],

off r o et Ks sont dorm,s respect ivement par (ta) et (3a).

K: est donn6 par les courbes de la figure (V.5A) de la r6f~rence f i l l .

D6signons par P ~ ( > t) la probabilit6 pour que le d61ai d 'a t tente soit sup6rieur h t donn6.

L'application de l 'expression asymptot ique

- - 224 - -

t. 16, n ~ 9-10, 1961]

(IV.8.11), annexe I, permet d'6crire, dams le cas du choix darts l'ordre des atria, des :

s i t > 1 + 2Is environ, (9a) �9 I PC(> t) "~ /~ , .P~(> st).

Les courbes dormant P~(> t) relatives au eas d 'un guichet ordinaire aver service ordinaire (eourbes de Crommelin) suffisent encore.

Dams le cas du choix au hasard, nous trouvons :

(10a) �9 P~(t) ~_. K~".P~(> st + s -- 1).

Pour ~ voisin de 1, nous avons : K~' ~ 1.

SUR QUELQUES PROBLEMES D'&TTENTE R~..CENTS

2 ~ Guichet ordinaire dgmarrant dbs la prdsence d'un ~isiteur.

La probabilitd d'attente P~ se d6duit de (IV.8.23) :

a v e o :

oo 0--me co (nc)~ (12a) Log (I)0(-- c) = -- Z - - " Z v~"

n = l n '~=ns+l

Px est donn6 par les courbes de la figure (V.5.2), r6f6renee [ l i ] .

La relation (IV.8.24), annexe I, nous donne pour le ddlai moyen d'attente :

(i3a) �9 Ti = P~.Tv,

oh Tv, donn6 par (7a), correspond au cas du guichet permanent.

La relation (IV.8.22), aunexe I, nous donne fina- lement pour les deux cas de loi de choix :

(I4a) �9 P(> t )= P~.Pv(> t),

off Pv(> t) correspond au cas du guichet permanent.

3 ~ Guichet ordinaire, ne ddmarrant qu'en prJsence d'un groupe complet de s visiteurs.

D6signons respeetivement par P o e t T o la proba- bilit6 d 'a t tente et le d61ai moyen d 'a t tente dans le eas de s guichets ordinaires avec service ordinaire.

Les relations (IV.8A6) et (IV.8A7), annexe I, nous donnent dans le eas pr6sent :

li - p = ( i - Po)/S, (15a) �9 T = T o + (s-- l)/2s~.

La relation (IV.8A9), annexe I, se simplifie pour (r o ~ l) < 1, e'est-h-dire ~ > 0,7. Nous trouvons alors, pour expression asymptotique, dans le cas des deux lois de choix :

(i6a) �9 P(> t) ~'~ ~.Pv(> t).

Pour les trois types de service par groupes, la probabilitd Pz, pour qu'il y aft X visiteurs en pr6sence h un instant quelconque, est la m~me que dams le cus A.

Manuscrit re~u le 8 ]uin 1961.

12/12

BIBLIOGRAPHIE

[l] BAILEY (N, T. J.). On queueing process with bulk service. (Processus de queue aveo service par groupes.) J. B. Statist. Soc. B, 16, 1954, pp. 80-87.

[2] BUaKE (P. J.). Equilibrium delay distribution for one channel with constant holding time, Poisson input and random service. (R6partition de l'attente, dams le cas de l'6quilibre statistique devant un guichet h dur6e de service eonstante, pour des arriv6es poissonniennes et un choix au hasard.) B. S. T. J. U. S. A., 38, n ~ 4, (juil. i959), pp. 1021-1031.

[3] COHEN (J. W.). Application of derived Markov chains in queueing and inventory theory. (Appli- cation des chalnes de Markoff d6rivdes dans la th6orie des queues et du stockage.) Math. Institute of the Technological University, Delft, (oct. i960).

[4] CO•OLLY (B. W.). Queueing at a single serving point with group arrival. (Attente devant un seul guichet, dams le eas d'arriv6es en groupes.) J. r. Statist. Soe., B 22, (i960), pp. 285-298.

[5] DOWNTON (F.). Waiting time in bulk service queues. (Attente dans le eas du service par groupes.) J. r. Statist. Soc. B 17, (1955), pp. 256- 261.

[6] GAvEn (D. P.). Imbebded Markov chain analysis of a waiting line process in continuous time. (Analyse d'un processus d'attente continu dams le temps, par la mdthode de la chafne de Markoff incluse.) Ann. Math. Statist., 30, (i959), pp. 698- 720.

[7] LE GALL (P.). Contribution h l%tude statistique des alterations de la parole, coneernant un con- centrateur 61ectronique de circuits interurbains pour cables h longue distance. Etude du Centre National d'Etudes des Tdl6eommunications, Paris, (avril 1959) (hors commerce).

[8] LE GALL (P.). Le probl~me de l'attcnte devant un guichet, avec ehoix au hasard, et sa loi asymptotique. (Cas des arrivdes poissonniennes.)Lettres d Acad. Sciences, Paris, (30 nov. 1959 et i4 d6c. i959).

[8 bis] I,E GALL (P.). Sur le probl6me de l'attente daus le cas d'un guichet avee choix des visiteurs au hasard. (Cas des arriv6es r6g6n6ratives.) Lettre 5 Acad. Sciences, Paris, (8 f6vr. 1960).

[9] LE GALL (P.). Les guichets ~ dur6es de service exponentielles et constantes dana le eas du choix au hasard. Lettre d Acad. Sciences, Paris, (25 avril 1960).

[10] LE GALL (P.). Le probl6me du guichet permanent et celui du service par groupes. Lettre d Acad. Sciences, Paris, (29 aofit 1960).

[10 bis] LE GALL (P.). Le probl6me du gulehet dans le cas des arriv6es en groupe. Lettre h A cad. Sciences, Paris, (27 f6vr. 1961).

[il] L~ GAiT (P.). Les processus stoehastiques et les syst~mes avee ou sans attente. T. I. G6n6ralit6s ; applications h la recherche op~rationnelle. Dunod, Paris, (en preparation).

[12] POSLACZEK (F.). La loi d'attente des appels t61~- phoniques. C. R. Acad. Sc., Paris, 222, i946, pp. 353-355.

[13] PO~-LACZEK (F.). Probl~mes stoehastiques pos~s par le ph6nom~ne de formation d'une queue d'attente h u n guichet et par des ph6nom~nes a.pparent6s. Mdmorial des Sciences Mathdma- ttques, Gauthier-Villars, Paris, i957.

[14] u (E.). D~lais d'attente des appels td~phoniques trait6s au hasard. C. It. Acad. Sc., Pari% (1946), 222, pp. 268-269.

225

Documents

Sur quelques problèmes d'attente récents