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





Previous PDF Next PDF



14. Introduction aux files dattente

? Taille moyenne de la file d'attente. ? Taux d'utilisation du serveur. ? Temps moyen d'attente d'un client. MTH2302D: Files 



Résumé de files dattente

Q : longueur de la file ?n = P(Q = n)



MÉMOIRE MASTER

quent le problème des files d'attente ne survient que pendant de courtes pé- riodes. Donc le nombre de serveurs en cours est : min(X(t)



Files dattente

2018. gada 30. okt. Exemples On se contente de deux exemples qui seront revus plus tard dans le cours. — File M/M/1/?/PS. M Processus d'arrivée : Poisson de ...



Cours de Modélisation et dEvaluation de Performance

Cours de Modélisation et files d'attente chaque file modélisant une ressource par exemple. ... déduire la fonction de répartition (PDF) et la fonction.



Cours de Tronc Commun Scientifique Recherche Opérationnelle

temps moyen d'attente nombre moyen de clients dans la file nombre de serveurs occupés probabilité que la file soit vide / pleine 6/28. Files d'attente (1).



Modèles stochastiques Modèle de file dattente

Service: Le service peut être assuré par un ou plusieurs serveurs. Le temps qui s'écoule entre le début et la fin de service d'un client est dénoté.



Modélisation dune le dattente

Les files d'attente sont aujourd'hui des phénomènes que l'on rencontre nées il faut reprendre celle qui était en cours depuis le début puisque les ...



Files dattente

b) au cours de la durée t une arrivée au moins se produit. Cette dernière probabilité étant complémentaire de g(t)



Files dattente

Un processus est une collection de variables aléatoires {Zt t ? 0}



Files d’attente

Files d’attente B Ycart La théorie des ?les d’attente a de nombreuses applications en particulier dans les réseaux de communication et les réseaux informatiques Nous insis-terons surtout sur les modèles markoviens en supposant acquises les notions de base sur les chaînes de Markov et les processus markoviens de saut qui



Files d'attente Théorie des - databnffr

Files d'attente Théorie des Topic : Files d'attente Théorie des Source ?le : RAMEAU see also : Microsoft Message queue server (logiciel) Field : Mathématiques Variant subject headings : Queues Théorie des Teoria delle code (italien) Théorie des ?les d'attente Théorie des queues Data 1/12 data bnf

Qu'est-ce que la théorie des files d'attente ?

De nos jours, la théorie des files d’attente connaît une croissance rapide dans divers champs, notamment une analyse théorique des modèles de files d’attente et des réseaux d’une structure plutôt complexe en utilisant des modèles mathématiques assez sophistiqués et divers types de processus stochastiques.

Quelle est la différence entre les files d’attente et les services de transport?

Dans Exchange 2016 et Exchange 2019, les files d’attente peuvent contenir des messages avant, pendant et après la remise. Il existe des files d’attente dans le service de transport sur les serveurs de boîtes aux lettres et les serveurs de transport Edge.

Quels sont les différents types de files d’attente ?

Puis comprendre le fonctionnement des systèmes de files d’attente et de constater leur utilité en réseau. Il existe d’autres types de files d’attente à titre d’exemple CBQ (Class Based Queuing) permet d’allouer une certaine proportion de bande passante pour une classe de trafic donnée et DRR Deficit Round Robin.

Comment fonctionne la file d’attente?

Six demandes sont téléchargées simultanément. Après cela, une série de demandes sont en file d’attente ou bloquées. Une fois l’une des six premières demandes terminé, l’une des demandes de la file d’attente démarre.

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 ??2 ??3 μ??Remarque: chaˆıne ergodique?Formule des coupes (r´egime permanent) + n=0pn= 1 :quotesdbs_dbs19.pdfusesText_25
[PDF] file dattente m/m/1/k

[PDF] drogues les plus consommées dans le monde

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

[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.