14 Files Attente [PDF]

Zitiervorschau

1/3

2/3

3/3

14. Introduction aux files d’attente MTH2302D ´ S. Le Digabel, Ecole Polytechnique de Montr´ eal

H2015 (v1)

MTH2302D: Files d’attente

1/23

1/3

2/3

3/3

Plan

1. Introduction

2. Mod` ele M/M/1

3. Mod` ele M/M/1/K

MTH2302D: Files d’attente

2/23

1/3

2/3

3/3

1. Introduction 2. Mod` ele M/M/1 3. Mod` ele M/M/1/K

MTH2302D: Files d’attente

3/23

1/3

2/3

3/3

Introduction La th´eorie des files d’attente consiste en l’´etude de syst`emes o` u des clients se pr´esentent `a un dispositif de service, appel´e serveur. Puisqu’un client occupe le serveur pendant un certain temps, les autres clients doivent attendre avant d’ˆetre servis, formant ainsi une file d’attente. Quelques exemples d’application : I

R´eseaux informatiques : serveur = routeur, client = paquet.

I

Ateliers (job shop) : serveur = machine, client = tˆache.

En ing´enierie, on s’int´eresse `a des m´etriques de performance des files d’attente, par exemple : I

Taille moyenne de la file d’attente.

I

Taux d’utilisation du serveur.

I

Temps moyen d’attente d’un client.

MTH2302D: Files d’attente

4/23

1/3

2/3

3/3

Mod` ele ´ el´ ementaire de file d’attente En g´en´eral, pour ´etudier l’impact de diff´erents choix de conception sur la performance d’une file d’attente, il faut construire un mod`ele de simulation. On peut aussi utiliser un mod`ele simplifi´e pour lequel les m´etriques s’expriment par des ´equations analytiques. Le mod`ele de base en files d’attente se nomme M/M/1 et se g´en´eralise en notation de Kendall A/B/C/K/N/D : I I I I I I

A : processus d’arriv´ee (M = markovien ou memoryless). B : processus de service (M = markovien ou memoryless). C : nombre de serveurs. K : capacit´e du syst`eme (file + serveurs). N : taille de la population des clients (habituellement infinie). D : discipline de service (par d´efaut, FIFO, ou PAPS : 1er arriv´e 1er servi, mais aussi RANDOM ou PRIORITY).

MTH2302D: Files d’attente

5/23

1/3

2/3

3/3

1. Introduction 2. Mod` ele M/M/1 3. Mod` ele M/M/1/K

MTH2302D: Files d’attente

6/23

1/3

2/3

3/3

Mod` ele M/M/1 I

Les clients se pr´esentent au syst`eme al´eatoirement selon un processus de Poisson de taux λ.

I

Le temps de service suit une loi exponentielle de taux µ, ind´ependamment d’un client `a l’autre.

I

La file d’attente peut s’´etendre `a l’infini.

Rappel sur le processus de Poisson : I

Le nombre A(t) d’arriv´ees dans l’intervalle de temps [0; t] suit une loi de Poisson de param`etre c = λt.

I

Les arriv´ees dans deux intervalles de temps disjoints sont ind´ependantes.

I

Le temps qui s’´ecoule entre deux arriv´ees suit une loi exponentielle de taux λ.

MTH2302D: Files d’attente

7/23

1/3

2/3

3/3

Exemple 1

Soit Tn le temps d’arriv´ee du ni`eme client dans une file M/M/1. On dit que Tn suit une loi d’Erlang de param`etres n et λ. 1. Trouver la fonction de r´epartition de Tn (utiliser le processus de Poisson). 2. Calculer E(Tn ) et V(Tn ).

MTH2302D: Files d’attente

8/23

1/3

2/3

3/3

Arriv´ ee avant un d´ epart et d´ epart avant une arriv´ ee I

Temps pour qu’une nouvelle arriv´ee se produise : A ∼ Exp(λ).

I

Temps pour qu’un nouveau d´epart se produise : D ∼ Exp(µ). (A et D sont ind´ependantes).

I

Probabilit´e qu’une arriv´ee se produise avant un d´epart : P (A < D) =

I

λ . λ+µ

Probabilit´e qu’un d´epart se produise avant une arriv´ee : µ P (D < A) = . λ+µ

MTH2302D: Files d’attente

9/23

1/3

2/3

3/3

Analyse en r´ egime stationnaire Il est difficile d’´etudier la variable al´eatoire N (t) repr´esentant le nombre de clients au temps t dans le syst`eme. On s’int´eresse plutˆot `a N = limt→∞ N (t). On parle alors d’analyse en r´egime stationnaire (ou analyse `a l’´equilibre). Pour qu’une file M/M/1 puisse atteindre l’´equilibre, il faut que λ < µ (sinon la taille de la ` l’´equilibre, on peut montrer que file augmentera `a l’infini). A P (N = n) =

µ λ P (N = n − 1) + P (N = n + 1) . λ+µ λ+µ

λ Il s’agit de la r`egle des probabilit´es totales. Le terme λ+µ repr´esente la probabilit´e qu’un nouveau client arrive avant que le µ client en service quitte le syst`eme, et λ+µ est la probabilit´e que le client en service quitte avant qu’un nouveau client n’arrive.

MTH2302D: Files d’attente

10/23

1/3

2/3

3/3

´ Equations d’´ equilibre Soit πn = P (N = n). En posant les ´equations µ µ λ λ π1 = λ+µ π0 + λ+µ π2 , π2 = λ+µ π1 + λ+µ π3 , . . . , P ∞ µ λ πn = λ+µ πn−1 + λ+µ πn+1 , . . . , et n=0 πn = 1, on trouve que πn = (1 − ρ)ρn pour n = 0, 1, 2, 3, . . ., o` uρ= trafic.

λ µ

est d´efini comme l’intensit´e du

On remarque que N + 1 ∼ Geom(1 − ρ).

MTH2302D: Files d’attente

11/23

1/3

2/3

3/3

Notations I I I

I I

N Q : nombre moyen de clients faisant la queue. N S : nombre moyen de clients en train d’ˆetre servis. N = E(N ) = N Q + N S : nombre total (attente + service) moyen de clients dans le syst`eme en ´equilibre. NQ , NS et N sont les v.a. correspondantes. On a P (N = k) = πk .

I

T Q : temps moyen d’attente. T S : temps moyen de service. T = T Q + T S : temps moyen qu’un client passe dans le syst`eme. TQ , TS et T sont les v.a. correspondantes.

I

Tk : temps que passe le k`eme client dans le syst`eme.

I I I

MTH2302D: Files d’attente

12/23

1/3

2/3

3/3

La loi de Little La loi s’´enonce ainsi : N = λe T o` u λe est le taux d’entr´ee dans le syst`eme (λe = λ pour une file M/M/1). Puisque N = N Q + N S et T = T Q + T S , on trouve ´egalement que N Q = λe T Q et N S = λe T S . Remarque : La loi de Little s’applique `a tous les mod`eles de file d’attente rencontr´es en pratique (pas seulement `a la file M/M/1).

MTH2302D: Files d’attente

13/23

1/3

2/3

3/3

Exemple 2

On consid`ere une file d’attente M/M/1 de taux λ = 1 et µ = 2. Calculer (`a l’´equilibre) : 1. Le nombre moyen de clients dans le syst`eme, N . 2. Le nombre moyen de clients en service, N S . 3. Le nombre moyen de clients dans la file d’attente, N Q .

MTH2302D: Files d’attente

14/23

1/3

2/3

3/3

Mod` ele M/M/1 : formules ρ . 1−ρ

I

N=

I

N S =1 − π0 = ρ.

I

N Q =N − N S =

I

T =N /λ =

I

T S = 1/µ.

I

T Q =T − T S =

MTH2302D: Files d’attente

ρ2 . 1−ρ

ρ 1 = . λ(1 − ρ) µ−λ

λ . µ(µ − λ)

15/23

1/3

2/3

3/3

Mod` ele M/M/1 : formules (suite)



0 N −1

si N = 0 ou N = 1, si N > 1 .

I

Un seul serveur : NQ =

I

P (NQ = 0) =P (N = 0) + P (N = 1) = π0 + π1 = 1 − ρ + ρ(1 − ρ) = (1 − ρ)(1 + ρ).

I

P (NQ = k) =P (N = k + 1) = πk+1 = ρk+1 (1 − ρ), pour k > 0.

MTH2302D: Files d’attente

16/23

1/3

2/3

3/3

Mod` ele M/M/1 : formules (suite) I

Si N est le nombre de clients dans le syst`eme `a l’´equilibre, alors N + 1 = N1 ∼ Geom(p = 1 − ρ).

I

Nombre de clients en train d’ˆetre servis : NS ∼ Bern(ρ).

I

Temps total (attente + service) pass´e dans la file : T ∼ Exp(µ − λ).

I

Temps d’attente TQ (variable mixte) : I I

P (T Q = 0) = π0 = 1 − ρ. TQ {NQ > 0} ∼ Exp(µ − λ) (comme T ).

MTH2302D: Files d’attente

17/23

1/3

2/3

3/3

Exemple 3

On consid`ere une file d’attente M/M/1 de taux λ = 1 et µ = 2. Calculer (`a l’´equilibre) : 1. Le temps moyen de s´ejour d’un client dans le syst`eme, T . 2. Le temps moyen d’attente d’un client dans la file, T Q . 3. Le temps moyen de service d’un client, T S .

MTH2302D: Files d’attente

18/23

1/3

2/3

3/3

1. Introduction 2. Mod` ele M/M/1 3. Mod` ele M/M/1/K

MTH2302D: Files d’attente

19/23

1/3

2/3

3/3

Mod` ele M/M/1/K Pour un syst`eme de capacit´e K (taille maximale de la file de K − 1) avec ρ 6= 1, on peut montrer que πn = P (Y = n + 1|Y ≤ K + 1) =

ρn (1 − ρ) P (Y = n + 1) = P (Y ≤ K + 1) 1 − ρK+1

pour n = 0, 1, . . . , K, o` u Y ∼ Geom(1 − ρ). I

L’´equilibre est atteint pour tout ρ : 1−ρ . 1 − ρK+1

I

Si ρ 6= 1, πn = ρn

I

Si ρ = 1, on consid`ere des ´etats ´equiprobables : πn = pour n = 0, 1, . . . , K .

I

Le syst`eme est `a pleine capacit´e avec probabilit´e πK .

I

Taux d’entr´ee : λe = λ(1 − πK ).

MTH2302D: Files d’attente

1 K +1

20/23

1/3

2/3

3/3

Exemple 4

Pour le syst`eme M/M/1/2 avec λ = µ, trouver l’esp´erance et la variance du nombre de clients dans le syst`eme en ´equilibre.

MTH2302D: Files d’attente

21/23

1/3

2/3

3/3

Exemple 5 On consid`ere une file d’attente M/M/1/5 de taux λ = 1 et µ = 2. Calculer (`a l’´equilibre) : 1. Le nombre moyen de clients dans le syst`eme. 2. Le nombre moyen de clients dans la file d’attente. 3. La proportion de clients ne pouvant entrer dans le syst`eme. 4. Le temps moyen de s´ejour d’un client dans le syst`eme. 5. Le temps moyen d’attente d’un client dans la file.

MTH2302D: Files d’attente

22/23

1/3

2/3

3/3

Exemple 6 On consid`ere une file d’attente M/M/1 avec priorit´e : Les clients de classe 1 ont une priorit´e absolue sur les clients de classe 2, c’est-`a-dire qu’ils d´epassent automatiquement tous les clients de classe 2 dans la file. De plus, un client de classe 2 en service retourne imm´ediatement dans la file d’attente si un client de classe 1 se pr´esente. On a λ1 = 1 pour les clients de classe 1, λ2 = 2 pour les clients de classe 2, et µ = 4. Calculer (`a l’´equilibre) : 1. Le nombre moyen de clients de chaque classe dans le syst`eme. 2. Le temps moyen de s´ejour dans le syst`eme pour chaque classe. Indication : On peut montrer que les ´equations d’´equilibre de la file M/M/1 ne d´ependent pas de la politique de service de la file. MTH2302D: Files d’attente

23/23