Files Attente

8/2/2019 Files Attente

1/39

Recherche Operationnelle

Les files dattente et les reseaux de filesdattente

Jean-Francois Heche

Institut de Mathematiques

Ecole Polytechnique Federale de Lausanne


2/39

Les files dattente

Definition et classification : la notation de Kendall La formule de Little

Les files dattente markoviennes

La file M/M/1

La file M/M/m

La file M/M/m/K

Les files dattente non markoviennes

La file M/G/1 et la formule de Pollaczek-Khinchin Approximations pour les files G/G/m

J.-F. Heche, ROSO-EPFL Files dattente 1


3/39

Les files dattente simples

Une file dattente ou queue simple est caracterisee par un processus darrivee de clients decrivant les instants auxquels les

clients entrent dans le systeme ;

un processus de service decrivant le temps requis pour servir un client ;

un nombre de serveurs, tous identiques, specifiant le nombre maximalde clients pouvant etre servis simultanement.

File (places dattente)

Serveur(s)Processus darrivee

Processus de depart



4/39

A ces caracteristiques de base sajoutent parfois

la capacite de la file correspondant au nombre maximal de clients

pouvant etre presents a un instant donne (aussi bien en attente quenservice) ;

la taille de la population des clients susceptibles dutiliser le serveur ;

la discipline de service decrivant lordre dans lequel les clients sont

servis.



5/39

Notation de Kendall

Afin de simplifier la description des 3 ou 6 elements decrivant une file,

Kendall a introduit la notation suivante

Forme abregee : A/S/m

Forme complete : A/S/m/K/P/D

ou chaque symbole correspond, dans le meme ordre quavant, a unecaracteristique de la file dattente :

A : processus darrivee K : capacite de la file ()

S : processus de service P : taille de la population ()

m : nombre de serveurs D : discipline de service (F I F O)



6/39

Pour les processus darrivee et de service, les symboles les plus courants sont

M loi exponentielle ( memoryless)

D loi deterministe (temps dinter-arrivee ou de service constants)

G loi generale (les resultats sont vrais pour toute loi)

Pour la discipline de service, ils sont

F I F O premier arrive, premier servi ( first in, first out)

LIFO dernier arrive, premier servi ( last in, first out)

P S temps partage ( processor sharing)



7/39

Mesures de performance

Letude dune file dattente ou dun reseau de files a pour but de calculer

ou destimer les performances dun systeme dans des conditions de

fonctionnement donnees. Ce calcul se fait le plus souvent pour le regime

stationnaire uniquement et les mesures les plus frequemment utilisees sont

N le nombre moyen de clients presents (en attente et en service)

Q le nombre moyen de clients en attente

T le temps moyen de sejour ou de reponse (attente et service)

W le temps moyen dattente

U le taux dutilisation de chaque serveur



8/39

De maniere generale, une file est stable si et seulement si le nombre moyen

darrivees de clients par unite de temps, note , est inferieur au nombre

moyen de clients pouvant etre servis par unite de temps. Si chaque serveur

peut traiter clients par unite de temps et si le nombre de serveurs est m,

une file est stable si et seulement si

< m =

m< 1.

Pour un systeme stable, on a

T = W + S

ou S est le temps moyen de service et

N = Q + mU

ou m est le nombre de serveurs.



9/39

Formule de Little

Theoreme 1. Pour un systeme en regime stationnaire, le taux darrivee

des clients, le nombre moyen N de clients dans le systeme et le temps moyen

T de sejour (temps moyen de reponse) sont relies par la relation

N = T .

Preuve. Jouons a la concierge a la vue (tres) defaillante et notonssimplement les heures dentree et de sortie de clients.

Le systeme est vide au temps 0 et au temps t, (t) clients sont entres et

(t) sont deja repartis. Le taux moyen darrivee dans [0, t) est donc

(t) = (t)/t.

A linstant t, il y a N(t) = (t) (t) clients dans le systeme et, dans



10/39

[0, t), le cumul des temps de sejour dans le systeme est

(t) =t0

((s) (s)) ds =t0

N(s)ds.

Le nombre moyen de clients presents dans [0, t) et le temps moyen de

sejour dun client dans [0, t) sont

N(t) = (t)/t et T(t) = (t)/(t).

Ainsi

N(t) = (t)/t = ((t)/(t)) ((t)/t) = T(t) (t).

Finalement, si le systeme admet un regime stationnaire, on doit avoirlimt (t) = , limt T(t) = T et limt N(t) = N et le resultat

suit.



11/39

La file dattente M/M/1

Cette file modelise un guichet unique ou chaque client recoit un service

dont la duree est une variable exponentielle de parametre (independantede tout autre element affectant le systeme) et ou larrivee des clients

correspond a un processus de Poisson de taux (les temps entre deux

arrivees successives sont des variables aleatoires i.i.d. selon une loi

exponentielle de parametre ).Definissant letat de la file comme le nombre de clients presents, levolution

de la variable detat est une chane de Markov a temps continu de graphe

representatif

0 1 2 3



12/39

La file M/M/1 est donc un processus de naissance et de mort et elle est

stable si et seulement si ce processus est ergodique, c.-a-d. ssi

=

< 1.

Cette valeur est appelee lintensite du trafic.

Pour une file stable, la distribution stationnaire est

k = (1 )k k = 0, 1, . . .

et le taux dutilisation du serveur est

U = P[X > 0] = 1 P[X = 0] = 1 0

=



13/39

Mesures de performance : nombres moyens

Le nombre moyen de clients presents est

N = E[X] =k=0

kk =k=0

k(1 )k = (1 )k=1

kk1

= (1 )

d

d k=1

k

= (1 )

d

d

1

=

1

et le nombre moyen de clients en attente est

Q = N U =

1 =

2

1 .



14/39

Mesures de performance : temps moyens

Utilisant Little, on obtient, pour le temps moyen de reponse,

T =N

=

(1 )=

1

(1 )=

S

1

et, pour le temps moyen dattente,

W =Q

=

2

(1 )=

(1 )=

S

1 .

Remarque. On a bien T = W + S.



15/39

La file dattente M/M/m

Dans ce modele, m serveurs identiques et independants partagent les

memes places dattente. Les arrivees suivent un processus de Poisson de

parametre et la duree de chaque service est une variable exponentielle de

parametre .

Levolution du nombre de clients dans un tel systeme est egalement un

processus de naissance et de mort dont le graphe representatif est

0 1 2

2

3

m+1m-1 m

(m 1)

m

m m



16/39

Il nest pas surprenant dapprendre que cette file est stable ssi

=

m

< 1.

La resolution des equations de bilan permet de calculer sans trop de

difficulte la distribution stationnaire de la file. Une grandeur importante

pour les files M/M/m est la probabilite quun client entrant dans le

systeme doive attendre. Elle est egale a

= P[ m clients presents] =k=m

k =(m)m

m!(1 )0

avec

0

=

1 +

(m)m

m!(1 )+

m1k=1

(m)k

k!

1

.



17/39

Le taux dutilisation de chaque serveur est

U = /(m) = .

Les nombres moyens de clients presents et en attente sont

N = m +

1 et Q =

1 .

Les temps moyens de reponse et dattente sont

T =1

1 +

m(1 )

= S+

S

m(1 )

et

W =

m(1 )=

S

m(1 ).



18/39

La file dattente M/M/m/K

La file M/M/m/K est une file markovienne composee de m serveurs et

disposant de K places au total. Le nombre maximal de clients en attente

est donc Km. Si un client arrive alors que le systeme est plein, il ne peut

y entrer et doit repartir.

Levolution du nombre de clients dans un tel systeme est encore et toujours

un processus de naissance et de mort dont le graphe representatif est

0 1

2

m+1m-1 m

(m 1)

m

m m

K

m



19/39

La chane de Markov a temps continu decrivant levolution du nombre de

clients ne possede quun nombre fini detats. Ainsi, pour et positifs, elle

est irreductible et ergodique. Une file M/M/m/K est donc toujours stable

quel que soit lintensite du trafic

=

m.

Comme tout client arrivant alors que le systeme est plein doit repartir, letaux effectif darrivee dans le systeme nest pas mais

=K1

k=0

k = (1

K).

Ayant calcule N et Q, cest ce taux effectif quil faut utiliser pour

calculer T et W a laide de la formule de Little.



20/39

La file dattente M/G/1

Dans une file M/G/1 le temps de service ne suit plus une loi exponentielle

mais une loi non negative quelconque desperance S et de variance 2S finies.

Le processus stochastique decrivant levolution du nombre de clients dans le

systeme nest plus une chane de Markov car le temps de service nest plus

sans memoire !

Pour obtenir un processus markovien il faudrait etendre la definition de

letat du systeme afin dinclure egalement la duree de service deja recue par

le client occupant le serveur.

Une autre approche consiste a nobserver le systeme quaux instants ou un

client le quitte ! On obtient ainsi une chane de Markov sous-jacente a

temps discret.



21/39

La formule de Pollaczek-Khinchin

Rappelons que le coefficient de variation dune variable aleatoire X

desperance X= 0 et decart-type X est CX = X/X.

La formule de Pollaczek-Khinchin est un resultat tres elegant montrant que

les differences de performance entre une file M/G/1 et une file M/M/1 se

resument a un facteur multiplicatif !

Ainsi, le nombre moyen Q de clients en attente dans une file M/G/1 stable

( = S < 1) est

Q = 1 + C2S

2 2

1

ou C2S est le coefficient de variation au carre du temps de service

(C2S = 2

S/S2).



22/39

Indicant les performances par le type de file en question, lexpression

precedente devient

QM/G/1 =

1 + C2

S

2

QM/M/1.

Pour le temps moyen dattente, il suffit dappliquer Little pour obtenir

WM/G/1 =

1 + C2

S

2

S

1 =

1 + C2

S

2

WM/M/1.

Pour le calcul de N et T, on utilise les relations

N = Q + U et T = W + S,

le taux dutilisation du serveur etant toujours U = .



23/39

Remarques

0 1

Lois dErlang Ek Lois hyperexponentielles Hk

C2

Loicste

D

Loiexp.

M

Une variable dErlang dordre k, de symbole Ek, est la somme de k variables

aleatoires exponentielles i.i.d. Son coefficient de variation au carre est 1/k.

Une variable hyperexponentielle dordre k, de symbole Hk, est unecombinaison convexe de k variables exponentielles independantes (de

parametres differents). Son coefficient de variation au carre est 1.



24/39

Les autres files dattente simples

Les files dattente G/M/1, M/G/m, G/M/m, G/G/1, G/G/m, . . . sont

des processus stochastiques complexes, difficiles voir tres difficiles a traiter

de maniere exacte et en toute generalite.

Les developpements se simplifient parfois pour les files ou m = mais les

resultats exacts existent essentiellement pour des cas particuliers.

De nombreuses approximations sont cependant disponibles, de plus ou

moins bonne qualite. Lune des plus simples est directement issue de la

formule de Pollaczek-Khinchin.



25/39

Approximations pour les files G/G/m

Soit le temps moyen entre deux arrivees successives de clients ( = 1/

est le taux darrivee) et S le temps moyen de service dun client ( = 1/S

est le taux de service).

Une file G/G/m est stable = /(m) = S/(m) < 1.

Dans ce cas, lutilisation moyenne de chaque serveur est U = et lenombre moyen de clients en attente est approximativement

QG/G/m

C2A + C

2

S

2

QM/M/m

ou C2A et C2

S sont, respectivement, les coefficients de variation au carre des

temps entre deux arrivees successives et des temps de service.



26/39

Les reseaux de files dattente

Definition

Reseaux ouverts, fermes et mixtes

Reseaux a forme produit

Les reseaux de Jackson

Conditions de stabilite

Distribution stationnaire



27/39

Reseaux de files dattente

Un reseau de files dattente est simplement un systeme compose dune ou

plusieurs files dattente reliees entre elles.

Les clients (dans les cas les plus simples, tous identiques ), une fois leur

service termine dans une station (file), se deplacent vers une autre station

ou quittent le systeme selon des regles de routage (deterministes ou

stochastiques).

1

2

3Arrivees

externes

Routage

Sortie du systeme



28/39

Reseaux ouverts, fermes et mixtes

Un reseau est ouvert si tout client present ou entrant dans le systeme peut

le quitter.

Un reseau est ferme si les clients ne peuvent le quitter. Dans un reseau

ferme, le nombre de client est generalement fixe et ces derniers sont

presents dans le systeme des le debut de son evolution.

Finalement, un reseau est mixte sil est ouvert pour certains clients et fermepour dautres.

Reseau ouvert Reseau ferme Reseau mixte



29/39

Reseaux a forme produit

La definition la plus simple de letat dun reseau consiste a definir letat

x(t) du systeme au temps t comme le vecteur (x1(t) . . . xJ(t)) ou xj(t)

est le nombre de clients presents a linstant t dans la file j.

Sous certaines conditions, un reseau stable possede une distribution

stationnaire de la forme

(x) = (x1 . . . xJ) =Jj=1

j (xj).

Un tel reseau est dit a forme produit et se comporte comme J filesindependantes de distribution stationnaire j , j = 1, . . . , J .



30/39

Les reseaux de Jackson

Un reseau de Jackson est compose de J files dattente ne comportant

chacune quun seul serveur de capacite infinie et utilisant une discipline defile F I F O. Chaque file fournit un service de duree exponentielle, le taux de

service de la file j etant j.

Les clients (appartenant tous a la meme classe) arrivent dans le systeme

selon des processus de Poisson, le taux darrivee dans la file j etant j.

Apres avoir termine son service a la station j, un client se deplace a la

station k avec probabilite rjk et quitte le systeme avec probabilite rj0 ou

rj0 = 1

Jk=1 r

jk.

De telles regles definissent un routage markovien.



31/39

Exemple2

3

1 21

r11 = 1/4

r13 = 1/4

r31 = 4/5

r23 = 2/3

r12 = 1/2

r30 = 1/5

r20 = 1/3

R= 1/4 1/2 1/40 0 2/3

4/5 0 0

r0 = 01/31/5



32/39

Conditions de stabilite

Pour quun reseau soit stable, chacune de ses files doit letre. Notant j letaux effectif (ou taux moyen) darrivee dans la file j, on peut ecrire les

equations de conservation

j = j +J

i=1

irij j = 1, . . . , J .

Sous forme matricielle, ces equations deviennent

= + R (IR) = .



33/39

Pour un reseau ouvert, on a limnRn = 0 et lunique solution du

systeme precedent est

= (IR)1.

Connaissant les taux effectifs darrivee , la file j est stable si et seulement

si

j =jj

< 1

et le reseau est stable si et seulement si chacune des files le composant

lest.



34/39

Exemple (suite)2

3

1 21

r11 = 1/4

r13 = 1/4

r31 = 4/5

r23 = 2/3

r12 = 1/2

r30 = 1/5

r20 = 1/3

Les equations de conservation du reseau sont

1 = 1 + 1r11 + 3r312 = 2 + 1r123 = 1r13 + 2r23



35/39

1 = 1 + 1/4 + 43/5

2 = 2 + 1/2

3 = 1/4 + 22/3

1 =60

171 +

32

172

2 =30

17

1 +33

17

2

3 =35

171 +

30

172

Le reseau est donc stable si 1, 2, 1, 2 et 3 sont tels que

1 =11

< 1 2 =22

< 1 2 =33

< 1.



36/39

Distribution stationnaire

Les reseaux de Jackson sont des reseaux a forme produit et la distribution

stationnaire dun reseau ouvert et stable est

(x) = (x1 . . . xJ) =Jj=1

j (xj) =Jj=1

(1 j)xjj .

Un tel systeme se comporte donc comme J files M|M|1 independantes

dintensite respective 1 = 1/1, . . . , J = J/J.

Rappel. Letat x du reseau est le vecteur dont la je composante, notee xj,

represente le nombre de clients presents dans la station j.



37/39

Exemple

1 = 6 2 = 4

r21 = p

1 = 2

Les taux effectifs darrivee sont solutions de

1 = 1 + p22 = 1.

Ainsi

1 = 2 =1

1p.



38/39

Le reseau est stable si et seulement si

1 =1

1=

1

(1p)1=

2

6(1p)

< 1 p

Documents

Files Attente