Processus de Poisson File M/M/1 Autres files Un exemple Conclusion Cours de Tronc Commun Scientifique Recherche Opérationnelle Les files d'attente (1)
| Previous PDF | Next PDF |
[PDF] 14 Introduction aux files dattente - GERAD
▻ Taille moyenne de la file d'attente ▻ Taux d'utilisation du serveur ▻ Temps moyen d'attente d'un client MTH2302D: Files
[PDF] Files dattente - LACIM
23 mai 2014 · ▷ Lignes aériennes; ▷ Transplantation d'organes; ▷ Cour de Justice; ▷ Traitement de processus informatiques; ▷ Prendre de l'essence
[PDF] Les files dattente - Loria
Processus de Poisson File M/M/1 Autres files Un exemple Conclusion Cours de Tronc Commun Scientifique Recherche Opérationnelle Les files d'attente (1)
[PDF] Résumé de files dattente
intensité du trafic ; – Q : longueur de la file, πn = P(Q = n), GQ(z) = E(zQ); – ˜Q : nombre de personnes en attente, ˜Q = Q - n01l{Q李n0} s'il y a n0 serveurs ;
Files dattente - Érudit
La théorie des files d'attente existait avant que ne fût imaginé, sous le titre « recherche la probabilité d'au moins une arrivée au cours de la durée t, le W(t)
[PDF] Files dattente
Un processus est une collection de variables aléatoires {Zt , t ≥ 0}, indicée par le temps Ici, il nous servira à décrire l'évolution aléatoire au cours du temps d'un
[PDF] Modèles stochastiques Modèle de file dattente
File d'attente: La file d'attente est caractérisée par le nombre maximum permis de clients en attente (fini ou infini) Clients: Les clients (issus de la population) se
[PDF] 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),s) Le nombre de
[PDF] MODÈLES DE DURÉE Processus poissoniens et files dattente
3 août 2020 · Support de cours 2020-2021 Classification des files d'attente au nombre d' évènements qui se sont produits au cours de l'intervalle ] ]t,0
[PDF] FILE DATTENTE - cloudfrontnet
le système à cet instant (un client est « présent dans le système » si il est en file d 'attente ou en cours de service) Les quantités fondamentales auxquelles
[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] montrer que le répertoire d'action politique s'est aujourd’hui élargi corrigé
[PDF] filière es premiere
[PDF] le répertoire de l'action politique se limite-t-il au vote ?
[PDF] montrez que les répertoires d’action politique dépassent aujourd’hui la pratique du vote.
Files d"attente (1)
F. Sur - ENSMN
Introduction
Vocabulaire
Caract´eristiques
Notations de Kendall
Loi de Little
Mod´elisation dans
le cadre MarkovienProcessus 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 MarkovienProcessus 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 MarkovienProcessus 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 MarkovienProcessus de Poisson
File M/M/1
Autres files
Un exemple
ConclusionExemples de files d"attente (2)
4/28Files d"attente (1)
F. Sur - ENSMN
Introduction
Vocabulaire
Caract´eristiques
Notations de Kendall
Loi de Little
Mod´elisation dans
le cadre MarkovienProcessus 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 MarkovienProcessus 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 / pleine6/28Files d"attente (1)
F. Sur - ENSMN
Introduction
Vocabulaire
Caract´eristiques
Notations de Kendall
Loi de Little
Mod´elisation dans
le cadre MarkovienProcessus 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 MarkovienProcessus 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 1234S 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 MarkovienProcessus 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 oud´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 MarkovienProcessus de Poisson
File M/M/1
Autres files
Un exemple
ConclusionLa loi de Little (1)Arriv´ees
D´eparts
temps t1234567 23145Nombre 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 0N(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 MarkovienProcessus de Poisson
File M/M/1
Autres files
Un exemple
ConclusionLa loi de Little (1)
Arriv´ees
D´eparts
temps t1234567 23145Nombre 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 0N(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 MarkovienProcessus de Poisson
File M/M/1
Autres files
Un exemple
ConclusionLa loi de Little (2)
t 0N(u)du=A(t)?
i=1T i-R(t)Donc :
1t t 0N(u)du=A(t)t
1A(t)A(t)?
i=1T i-R(t)tHypoth`eses: lorsquet→+∞11
t t0N(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/28Files d"attente (1)
F. Sur - ENSMN
Introduction
Vocabulaire
Caract´eristiques
Notations de Kendall
Loi de Little
Mod´elisation dans
le cadre MarkovienProcessus 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 MarkovienProcessus de Poisson
File M/M/1
Autres files
Un exemple
ConclusionExemple
Un serveur informatique `a 5 processeurs re¸coit en moyenne1000 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 MarkovienProcessus 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 MarkovienProcessus 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 que1?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-λtOn 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 MarkovienProcessus de Poisson
File M/M/1
Autres files
Un exemple
ConclusionProcessus de Poisson01020304050607080900 2 4 6 8 10 12 14 16 18 20 tA(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 MarkovienProcessus 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 MarkovienProcessus 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)Simet : Pr(Nt+h=n|Nt=n+ 1) =μh+o(h)Vocabulaire:Nt=processus de Markov `a temps continu.18/28Files d"attente (1)