[PDF] Cours de Tronc Commun Scientifique Recherche Opérationnelle

View - Download Cours de Tronc Commun Scientifique Recherche Opérationnelle

Previous PDF

Next PDF

Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionCours de Tronc Commun Scientifique

Recherche Op´erationnelle

Les files d"attente (1)

Fr´ed´eric Sur

´Ecole des Mines de Nancy

www.loria.fr/≂sur/enseignement/RO/

1/28Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionLes files d"attente (1)1Introduction

2Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

3Mod´elisation dans le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

4Un exemple

5Conclusion

2/28Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionExemples de files d"attente (1)

Noah"s ark, Edward Hicks, 1846.

3/28Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionExemples de files d"attente (2)

4/28

Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionExemples de files d"attente (3)

St Pancras Station, Londres, AFP, dec. 2010.

"File" d"attente?

5/28Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionExemples de files d"attente (4)

et :Trafic a´erien T´el´ecommunications (t´el´ephonie, call-centers)

Serveurs informatiques

Objectif: dimensionnement, organisation

par l"estimation demesures de performancecomme :temps moyen d"attente nombre moyen de clients dans la file nombre de serveurs occup´es probabilit´e que la file soit vide / pleine

6/28Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionLes files d"attente (1)1Introduction

2Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

3Mod´elisation dans le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

4Un exemple

5Conclusion

7/28Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionCaract´eristiques d"un syst`eme d"attente"Clients"File d'attente "Serveurs"S 1 1234
S 2 S n"loi" d"arriv´ee des clients? "loi" de la dur´ee des services? combien de serveurs? quelle est la taille de la file? comment s"organise la file? 8/28

Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionLes notations de Kendall (1953)

File (syst`eme) d"attente d´ecrite par :

A/B/m/N/S

o`u :Aest la distribution des arriv´ees : stochastique ou

d´eterministe;Best la distribution des temps de service : idem;mest le nombre de serveurs;Nest le nombre maximum de clients dans le syst`eme;Sest ladiscipline de service(FIFO, LIFO, RAND...)Question: sous quelles conditions peut-on faire des calculs?9/28Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionLa loi de Little (1)Arriv´ees

D´eparts

temps t1234567 2

3145Nombre d"arriv´ees / d´epartsA(t) nombre d"arriv´ees pendant [0,t]D(t) nombre de d´eparts pendant [0,t]N(t) =A(t)-D(t) nombre de clients au tempstT

i: temps de s´ejour (attente + service) dui-`eme client

Remarque:?

t 0

N(u)du=A(t)?

i=1T i-R(t)

10/28Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionLa loi de Little (1)

Arriv´ees

D´eparts

temps t1234567 2

3145Nombre d"arriv´ees / d´epartsA(t) nombre d"arriv´ees pendant [0,t]D(t) nombre de d´eparts pendant [0,t]N(t) =A(t)-D(t) nombre de clients au tempstT

i: temps de s´ejour (attente + service) dui-`eme clientRemarque:? t 0

N(u)du=A(t)?

i=1T i-R(t)10/28Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionLa loi de Little (2)

t 0

N(u)du=A(t)?

i=1T i-R(t)

Donc :

1t t 0

N(u)du=A(t)t

1A(t)A(t)?

i=1T i-R(t)t

Hypoth`eses: lorsquet→+∞11

t t

0N(u)→N(nombre moyen de clients pr´esents)2A(t)t

→λ(nombre moyen d"arriv´ees par unit´e de temps)3? ?A(t) i=1Ti? /A(t)→T(temps de s´ejour moyen)4R(t)t →0 (hypot. 1,2,3 : "r´egime permanent"; hypot. 4 : pas de cumul) 11/28

Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionLa loi de Little (3)Proposition - loi de Little (1961)

N=λ·T

Autre version :

N f=λ·T f avec : -N f: nombre moyen de clientsdans la file d"attente -T f: temps d"attente moyen (dans la file). (i.e. sans compter les clients en cours de service.)Remarque: r´esultat g´en´eral! -→pas d"hypoth`ese sur la distribution des arriv´ees ou des temps de services, ni sur la discipline de service.

12/28Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionExemple

Un serveur informatique `a 5 processeurs re¸coit en moyenne

1000 requˆetes par seconde.

L"administrateur du serveur se rend compte que le serveur est occup´e `a 100%, et qu"en moyenne 8 requˆetes sont en attente. Question 1: quel est le temps moyen d"attente d"une requˆete? (attention autime-out)loi de Little :T f=N f/λ= 8/1000 sec.Question 2: quel est le temps moyen de traitement d"une requˆete?T-T f= (N-N f)/λ= (13-8)/1000 = 5/1000 sec.13/28Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionLes files d"attente (1)1Introduction

2Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

3Mod´elisation dans le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

4Un exemple

5Conclusion

14/28Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionLes clients n"ont pas de m´emoire

Hypoth`esessur le nombre d"arriv´eesA(t) pendant [0,t] :les nombres d"arriv´ees pendant des intervalles de temps

disjoints sont ind´ependants(ph´enom`ene "sans m´emoire")Pr(A(t+h)-A(t) = 1) =h→0λh+o(h)Pr(A(t+h)-A(t)>1) =h→0o(h)

λ: taux d"arriv´ee (nombre par unit´e de temps).Alors on peut montrer que

1?t,A(t) suit une loi de Poisson de param`etreλt:

?k?0,Pr(A(t) =k) =e-λt(λt)kk!2le tempsTarrentre deux arriv´ees cons´ecutives suit une loi exponentielle : ?t?0,Pr(Tarr=t) =λe-λt

On dit queA(t) est unprocessus de Poisson.15/28

Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionProcessus de Poisson01020304050607080900 2 4 6 8 10 12 14 16 18 20 t

A(t)(exemple avecλ= 0.2)Propri´et´es:E(A(t)) =λt,E(Tarr) = 1/λ16/28Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionLes serveurs n"ont pas davantage de m´emoire... Hypoth`ese: la dur´ee d"un service suit une loi exponentielle. ?t?0,Pr(Tserv=t) =μe-μt De mani`ere ´equivalente, siS(t) est le nombre de services possibles pendant [0,t], ?t,S(t) suit une loi de Poisson : ?k?0,Pr(S(t) =k) =e-μt(μt)kk! Iciμest letaux de service(ounombre moyen de services par unit´e de temps) d"un serveur donn´e. (1/μest ladur´ee moyenne d"un service.)

17/28Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionFile M/M/1

Exemple canonique : un serveur, file non-born´ee.Arriv´ees = processus de Poisson, taux d"arriv´eeλDur´ee des services exponentielle, taux de serviceμ

-→hypoth`ese Markovienne (M) dans les deux cas + proba d"arriv´eeetservice pendant [0,h] esto(h)SimPr(Nt+h=n|Nt=m) = Pr(A(t+h)-A(t) =n-m|Nt=m) +o(h)donc (cf d´ef processus de Poisson) simn+ 1 : Pr(Nt+h=n|Nt=m) =o(h)

et : Pr(Nt+h=n|Nt=n+ 1) =μh+o(h)Vocabulaire:Nt=processus de Markov `a temps continu.18/28Files d"attente (1)

F. Sur - ENSMN

Introduction

Vocabulaire

Caract´eristiques

Notations de Kendall

Loi de Little

Mod´elisation dans

le cadre Markovien

Processus de Poisson

File M/M/1

Autres files

Un exemple

ConclusionFile M/M/1 : vue comme une chaˆıne de Markov Pr(Nt+h=n) =λhPr(Nt=n-1) + (1-λh-μh)Pr(Nt=n) +μhPr(Nt=n+ 1) +o(h) (si n?1...)

D"o`u la repr´esentation :

0 ??1 ??2quotesdbs_dbs35.pdfusesText_40

[PDF] statistique drogue 2015

[PDF] chiffre d'affaire de la drogue dans le monde

[PDF] onudc recrutement

[PDF] consommation de drogue par pays

[PDF] nombre de drogue dans le monde

[PDF] filière es matières

[PDF] filière es wikipédia

[PDF] montrer que l'action politique ne se limite pas au vote

[PDF] filière es premiere

[PDF] le répertoire de l'action politique se limite-t-il au vote ?

[PDF] montrer que la participation politique repose sur des répertoires d'action politique variés

[PDF] montrez que les répertoires de l'action politique sont variés.

[PDF] définition de l'éducation pdf

[PDF] connectés pour apprendre les élèves et les nouvelles technologies

[PDF] education english pdf