[PDF] [PDF] 14 Introduction aux files dattente - GERAD

[PDF] 1 Introduction 2 File M/M/1 : Définition et premières propriétés

Ecrire une fonction mm1 qui permet de simuler une trajectoire de la file d'attente M/M/1 prenant comme paramètre λ, µ et t l'instant final, et qui donne la matrice 

[PDF] 14 Introduction aux files dattente - GERAD

mod`ele de base en files d'attente se nomme M/M/1 et se généralise en notation de Kendall A/B/C/K/N/D : ▻ A : processus d'arrivée (M = markovien ou 

[PDF] Les files dattente - Loria

Loi de Little Modélisation dans le cadre Markovien Processus de Poisson File M/M/1 Autres files Un exemple Conclusion Exemples de files d'attente (2)

[PDF] 1 Préliminaire 2 Files dattente M(λ)/M(μ)/1

M1-MAPI3 2019-2020 Simulations stochastiques FILES D'ATTENTES On consid`ere une suite de v a (Tn) décrivant les temps entre deux arrivées de clients et 

[PDF] Files dattente

Si de plus tous les taux de naissance sont égaux à λ, c'est un processus de Poisson d'intensité λ Exemple 2 : La file M/M/1 La notation M/M/1 sera justifiée plus 

[PDF] Aide mémoire sur la file M/M/1 - MESCAL

On considère une file d'attente simple avec 1 serveur On suppose que le processus d'arrivée est un processus de Poisson de paramètre λ Les temps de services 

[PDF] EXEMPLES DE FILES DATTENTE - Ceremade

1 Étude d'une file d'attente M/M/1 On consid`ere une file d'attente qui se forme ` a un guichet par le mod`ele Dans le cas o`u ρ := λ/σ < 1, la chaıne de Markov

[PDF] Modèles stochastiques Modèle de file dattente

MAIS les suivantes donne un système d'équations plus facile à résoudre pour identifier les : équations d'équilib 0, , re 1 j M j j i ij i i j M j j q q j M π π π π = ≠

[PDF] Résumé de files dattente

1 / k ⩽ 1 ( kµ z + kµ )k loi hyper-exponentielle n ∑ i=1 piµie −µit n ∑ i=1 pi µi kX ⩾ 1 piµi z + µi Table 1 – File M(λ)/M(µ)/1 ρ λ µ < 1 πn (1 - ρ)ρn loi G(1 

[PDF] Files dattente - Stephan ROBERT-NICOUD

3 jui 2016 · Représentation de la file d'attente M/M/1 (Processus de naissance et de mort) : avec les paramètres suivants : λk = λ k = 0,1,2,3, µk = µ k = 1 

[PDF] file d'attente m/m/1 exercice corrigé

[PDF] file d'attente m/m/1/k

[PDF] file d'attente m/m/s

[PDF] file d'attente m/m/s/

[PDF] filet presse

[PDF] filiale danone

[PDF] filiale la poste

[PDF] filiale orange sosh

[PDF] filiales nestlé monde

[PDF] filialisation d'une activité

[PDF] filialisation d'une branche d'activité

[PDF] filiere

[PDF] filière agricole definition

[PDF] filière agriculture

[PDF] filière agroalimentaire

1/32/3 3/3

14. Introduction aux les d'attente

MTH2302D

S. Le Digabel,

Ecole Polytechnique de Montreal

A2017 (v1)

MTH2302D: Files d'attente1/24

1/32/3 3/3

Plan

1. Introduction

2. ModeleM=M=1

3. ModeleM=M=1=KMTH2302D: Files d'attente2/24

1/32/3 3/3

1. Introduction

2. ModeleM=M=1

3. ModeleM=M=1=KMTH2302D: Files d'attente3/24

1/32/3 3/3

Introduction

La theorie des les d'attente consiste en l'etude de systemes ou des clientsse presentent a un dispositif de service, appeleserveur. Puisqu'un client occupe le serveur pendant un certain temps, les autres clients doivent attendre avant d'^etre servis, formant ainsi unele d'attente. Quelques exemples d'application : I Reseaux informatiques : serveur = routeur, client = paquet. I Ateliers (job shop) : serveur = machine, client = t^ache. En ingenierie, on s'interesse a des metriques de performance des les d'attente, par exemple : I

Taille moyenne de la le d'attente.

I

Taux d'utilisation du serveur.

I Temps moyen d'attente d'un client.MTH2302D: Files d'attente4/24

1/32/3 3/3

Modele elementaire de le d'attente

En general, pour etudier l'impact de dierents choix de conception sur la performance d'une le d'attente, il faut construire un modele de simulation. On peut aussi utiliser un modele simplie pour lequel les metriques s'expriment par des equations analytiques. Le modele de base en les d'attente se nommeM=M=1et se generalise ennotation de KendallA=B=C=K=N=D: I A: processus d'arrivee (M= markovien oumemoryless). I B: processus de service (M= markovien oumemoryless). I

C: nombre de serveurs.

I

K: capacite du systeme (le + serveurs).

I N: taille de la population des clients (habituellement innie). I D: discipline de service (par defaut, FIFO, ou PAPS : 1er arrive 1er servi, mais aussi RANDOM ou PRIORITY).

MTH2302D: Files d'attente5/24

1/32/3 3/3

1. Introduction

2. ModeleM=M=1

3. ModeleM=M=1=KMTH2302D: Files d'attente6/24

1/32/3 3/3

ModeleM=M=1

I Les clients se presentent au systeme aleatoirement selon un processus de Poisson de taux. I Le temps de service suit une loi exponentielle de taux, independamment d'un client a l'autre. I

La le d'attente peut s'etendre a l'inni.

Rappel sur le processus de Poisson :

I Le nombreA(t)d'arrivees dans l'intervalle de temps[0;t]suit une loi de Poisson de parametrec=t. I Les arrivees dans deux intervalles de temps disjoints sont independantes. I Le temps qui s'ecoule entre deux arrivees suit une loi exponentielle de taux.MTH2302D: Files d'attente7/24

1/32/3 3/3

Exemple 1

SoitTnle temps d'arrivee duniemeclient dans une leM=M=1. On dit queTnsuit une loi d'Erlang de parametresnet, i.e. T n(=n;).

1.Trouver la fonction de repartition deTn(utiliser le processus

de Poisson).

2.Calculer E(Tn)et V(Tn).MTH2302D: Files d'attente8/24

1/32/3 3/3

Arrivee avant un depart et depart avant une arrivee I

Temps pour qu'une nouvelle arrivee se produise :

AExp().

I

Temps pour qu'un nouveau depart se produise :

DExp().

(AetDsont independantes). I Probabilite qu'une arrivee se produise avant un depart :

P(A < D) =+.

I Probabilite qu'un depart se produise avant une arrivee :

P(D < A) =+.MTH2302D: Files d'attente9/24

1/32/3 3/3

Analyse en regime stationnaire

Il est dicile d'etudier la variable aleatoireN(t)representant le nombre de clients au tempstdans le systeme. On s'interesse plut^ot aN= limt!1N(t). On parle alors d'analyse en regime stationnaire (ou analyse a l'equilibre). Pour qu'une leM=M=1 puisse atteindre l'equilibre, il faut que < (sinon la taille de la le augmentera a l'inni).A l'equilibre, on peut montrer que

P(N=n) =+P(N=n1) ++P(N=n+ 1).

Il s'agit de la regle des probabilites totales. Le terme +represente la probabilite qu'un nouveau client arrive avant que le client en service quitte le systeme, et +est la probabilite que le client en service quitte avant qu'un nouveau client n'arrive.

MTH2302D: Files d'attente10/24

1/32/3 3/3

Equations d'equilibre

Soitn=P(N=n). En posant les equations

1=+0++2,2=+1++3,:::,

n=+n1++n+1,:::, etP1 n=0n= 1, on trouve que n= (1)n pourn= 0;1;2;3;:::, ou= <1est deni comme l'intensite du trac. On remarque queN+ 1Geom(1).MTH2302D: Files d'attente11/24

1/32/3 3/3

Notations

IN

Q: nombre moyen de clients faisant la queue.

IN S: nombre moyen de clients en train d'^etre servis.

IN=E(N) =N

Q+N

S: nombre total (attente + service)

moyen de clients dans le systeme en equilibre. I

NQ,NSetNsont les v.a. correspondantes.

I

On aP(N=k) =k.

IT

Q: temps moyen d'attente.

IT

S: temps moyen de service.

IT=T Q+T

S: temps moyen qu'un client passe dans le

systeme. I TQ,TSetTsont les v.a. correspondantes.MTH2302D: Files d'attente12/24

1/32/3 3/3

La loi de Little

La loi s'enonce ainsi :N=eT

oueest le taux d'entree dans le systeme (e=pour une le

M=M=1). PuisqueN=N

Q+N

SetT=T

Q+T

S, on trouve

egalement queN Q=eT QetN S=eT S. Remarque :La loi de Little s'applique a tous les modeles de le d'attente rencontres en pratique (pas seulement a la leM=M=1).MTH2302D: Files d'attente13/24

1/32/3 3/3

Exemple 2

On considere une le d'attenteM=M=1de taux= 1et= 2.

Calculer (a l'equilibre) :

1.Le nombre moyen de clients dans le systeme,N.

2.Le nombre moyen de clients en service,N

S.

3.Le nombre moyen de clients dans la le d'attente,N

Q.MTH2302D: Files d'attente14/24

1/32/3 3/3

ModeleM=M=1: formules

I IN=1. IN

S=10=.

IN Q=NN S=21.

IT=N==(1)=1.

IT

S= 1=.

IT Q=TT

S=().MTH2302D: Files d'attente15/24

1/32/3 3/3

ModeleM=M=1: formules (suite)

I

Un seul serveur :NQ=0siN= 0ouN= 1,

N1siN >1.

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'attente16/24

1/32/3 3/3

ModeleM=M=1: formules (suite)

I SiNest le nombre de clients dans le systeme a l'equilibre, alorsN+ 1 =N1Geom(p= 1). I Nombre de clients en train d'^etre servis :NSBern(). I Temps total (attente + service) passe dans la le :

TExp().

I

Temps d'attenteTQ(variable mixte) :

I

P(TQ= 0) =0= 1.

ITQfNQ>0g Exp()(commeT).MTH2302D: Files d'attente17/24

1/32/3 3/3

Exemple 3

On considere une le d'attenteM=M=1de taux= 1et= 2.

Calculer (a l'equilibre) :

1.Le temps moyen de sejour d'un client dans le systeme,T.

2.Le temps moyen d'attente d'un client dans la le,T

Q.

3.Le temps moyen de service d'un client,T

S.MTH2302D: Files d'attente18/24

1/32/3 3/3

quotesdbs_dbs20.pdfusesText_26