Modles de files dattente Modle gnral de files dattente, tude des lois darrives et de service dusystme, distribution exponentielle, proprits dun systme de file dattente.Processus de naissance et de mort. tude de cas particuliers: une ou plusieursfiles, une ou plusieurs stations, un nombre limit ou non de clients, distributionsnon exponentielles, etc. Politiques de service. Aspect conomique desphnomnes dattente. Applications.

Gnralits Nous sommes souvent en prsence dun phnomne de files dattente.CONGESTION :Lorsque la demande de service dpasse la capacit de service,il y a formation de files dattente.Caractristiques dun tel phnomne :Arrives dunits des intervalles de temps irrguliers ou non, un centre de service.Exemple :arrive de camions un poste de chargement,entre de clients dans un magasin,arrive de bateaux dans un port,etc.Un ou plusieurs canaux de service ou stations.Exemple :guichet, vendeur, etc.Les units doivent ventuellement attendre quune station soit disponiblepour tre servies.Les intervalles de temps de service des units sont irrguliers ou non.

Gnralits Cas non intressant :Des intervalles constants des entres et des temps de service,avec une dure de service plus leve que lintervalle entre 2 entres,La file dattente augmente rgulirement et indfiniment.Schma de file dattente :Source 1Source 2Source UFile dattente 1File dattente 2File dattente FProcessusdarrivedunitsProcessusde servicedes units(dure et ordre de service, )Station 1Station 2Station SSystme dattente

Modle gnral de file dattente Posons M nombre dunits dans lensemble du phnomne (peut tre infini)(dans les sources, les files et les stations),N nombre dunits dans le systme (dans les files et les stations),Q nombre dunits dans les files dattente,R nombre dunits en cours de service,S nombre de stations,SI nombre de stations inoccupes,SO nombre de stations occupes,F nombre de files dattente,Qmax nombre maximum dunits dans les files dattente,

Quelques rsultats prliminaires . Trivialement, N =Rsi N SS + Qsinon.En gnral, N N(t), Q Q(t) et R R(t) varient en fonction du temps et sontalatoires suivant une loi de probabilit que nous chercherons connatre.Posons maintenant pn = Prob(N = n) la probabilit quil y ait n units dans le systme.En gnral, pn pn(t) varient aussi en fonction du temps. On obtient alors :ME[N] = k pkk = 0Dans le cas dune seule file dattente (F = 1),ME[Q] = (k S) pkk = S+1le nombre moyen dunits dans le systme.dsigne le nombre moyen dunits dans la file.

Quelques rsultats prliminaires . SE[SI] = (S k) pkk = 0dsigne le nombre moyen de stations inoccupes.On peut vrifier assez facilement que :E[N] = E[Q] + S E[SI](en exercice)Afin de poursuivre plus avant notre tude dun phnomne dattente, il nous fautconnatre les probabilits pn quil y ait n units dans le systme.Pour y arriver, il nous faut tudier les lois darrives et de service du systme.

Arrive dune unit dans le systme Considrons un intervalle de temps de dure t et n le nombre dunits qui arriventdans le systme dans cet intervalle,n est une variable alatoire.Hypothses :La probabilit quil y ait n arrives dans lintervalle de dure t ne dpend quede t et non de linstant initial partir duquel on a comptabilis les arrivesdans le systme.Homognit ou stationnarit dans le temps.La probabilit quune arrive se produise plus dune fois dans un intervallede temps infinitsimal dt est infiniment petite par rapport dt.Il ny a pas darrives en groupe (plusieurs arrives simultanes).La probabilit quune arrive se produise une fois exactement dans unintervalle de temps infinitsimal dt est proportionnelle dt, disons dt.Il ny a pas dheures de pointe (rpartition uniforme).

Arrive dune unit dans le systme Nous pouvons poser pn(t) la probabilit quil y ait n arrives dans lintervalle de dure t. Sous les hypothses prcdentes, on peut montrer que le nombre darrives dansun intervalle de temps t, soit N(t), suit une distribution de Poisson de paramtre tgal au nombre moyen darrives pendant un temps t i.e.pn(t) ( t)n e-tn! n = 0, 1, 2, On a aussi que :E[N] = tetVar[N] = t.La loi des arrives est entirement dtermine par le nombre moyen des arrives par unit de temps.

Temps de service dune unit dans le systme Aprs une priode dattente, les entits dans le systme reoivent le service.Le service est alatoire; il est donc dcrit par une distribution de probabilit.Si le nombre darrives dans un intervalle de temps obit une loi dePoisson, alors la dure sparant deux arrives est exponentielle.Nous considrerons donc que la dure de service suit une loi exponentiellede paramtre dont la fonction de densit est :f(t) = e-tt [0, ), > 0.La loi des services est entirement dtermine par le taux moyen des services gal linverse de la dure moyenne dun service.Note :Nous supposons que < sans quoi la file va augmenter indfiniment. moins davis contraire, lespremiers arrivs sont les premiers servis.

Processus de naissance et de mort Une arrive : une naissance,un dpart : une mort.Hypothses :Soit N = n,le temps coul jusqu la prochaine naissance suitune loi exponentielle de paramtre n,

le temps coul jusqu la prochaine mortalit suitune loi exponentielle de paramtre n,

seul une naissance ou une mort arrive la fois,

n : taux darrive lorsquil y a n clients dans le systme,n : taux de service lorsquil y a n clients dans le systme.Problme :Trouver une formule pourunits dans le systme au temps t. pn(t) = Prob(N(t) = n) la probabilit quil y ait n

Processus de naissance et de mort : rsolution Rgime transitoire :pn(t) dpend de t(rsolution difficile).Rgime stationnaire :pn(t) est indpendant de t.En supposant le rgime transitoire trs court, notre intrt va porter sur le rgimestationnaire.PRINCIPE PERMETTANT DCRIRE UNE QUATION DQUILIBRE POURTOUT TAT n :pour tout tat n = 0, 1, 2, , le taux dentre moyen de clients doit tregal au taux de dpart moyen.diagrammedtats

Calcul de Pn pn(t)

Calcul de Pn pn(t)

1er cas : modle S/F/M/Qmax modle 1/1// Une file dattente de capacit illimite, une station, une source illimite.diapositivesuivanteIntensitde trafic

Modle 1/1// : calcul de P0 Vous jouez pile-ou-face. Vous dcidez de jouer jusqu' ce qu'apparaisse "Pile"pour la premire fois. Le nombre L de lancers ncessaires est donc une variablealatoire dont la distribution est gomtrique.

Modle 1/1// : intensit de trafic Max Pncorrespond = n . n + 1Exemple :La probabilit la plus leve de rencontrer 3 units dans le systmea lieu lorsque = 3 / 4 et a pour valeur : 27 / 256 0.1054.Pour calculer Prob(N n), on a : Pi=(1 - ) i = 0 i = 0nnn=1 - n+1Par consquent, Prob(N > n) = n+1 et la probabilit quil y ait au moins uneunit dans le systme est Prob(N > 0) = = intensit de trafic = 1 probabilitde ne pas attendre.

Modle 1/1// : nombre moyen dunits dans le systme NN = / (1 - )Note :Si , alors 1 et N .La quantit est lessence mme du problme; cela reflte un compromisentre le gain issu de la rduction de N et le cot associ des installationset du personnel constituant le service.

Modle 1/1// : nombre moyen dunits dans la file dattente Q

Modle 1/1// : temps moyen pass dans le systme Formule de Little : Temps moyen pass dans le systme (temps de service inclus) :N / = [ / (1 - )] / = 1 / ( - ) = [1 / (1 - )] / Temps dattente moyen dans la file :Q / = [2 / (1 - )] / = / [( - )]= [ / (1 - )] / = N / Note :N / - Q / = 1 / ce qui reprsente bien le temps moyen de service.

Modle 1/1// : exemple I Dans une usine de fabrication de meubles, on peint 20 units lheure.Celles-ci arrivent la salle de peinture un rythme moyen de 12 lheure. = 12 = 20N = / (1 - ) = (12 / 20) / (1 12 / 20) = 1.5 meuble.Nombre moyen de meubles dans la salle de peintureTemps moyen pass dans la salle de peintureN / = 1.5 / 12 = 1/8 heure = 7.5 minutes.Temps moyen dattente avant dtre peintN / = 1.5 / 20 = 3/40 heure = 4.5 minutes.

Modle 1/1// : exemple II Dans un grand magasin, on a observ les arrives suivantes de clients :Arrives pendantune priodede 5 min.(n)Frquencesobserves(fn)01234562934248410Total sur 100Nombre moyen darrives par priode de 5 minutes : 6 1 n fn =1.27100n=0

Le paramtre 1.27 est-il admissible comme celui de la loi de Poisson associe aux arrives ? Effectuons donc un test du 2.Rgle suivre :On doit retrouver 4 5 lments par classe auminimum pour un chantillon de taille 100.Regroupons les 3 dernires classes en une.Arrives pendantune priodede 5 min.(n)Frquencesobserves(fn)0123 429342485Frquencesthoriques(100 pn(t) )o t = 1.2728362394100 ce qui prcdeDiffrence :|fn 100 pn(t) |2(fd)14111fd 100 pn.0357.1111.0435.1111.2500

Le paramtre 1.27 est-il admissible comme celui de la loi de Poisson associe aux arrives ? Nous avons alors exp2 = 0.0357 + 0.1111 + 0.0435 + 0.1111 + 0.2500 = 0.5514.tant donn que nous avons estim un paramtre et que nous possdons5 classes, nous sommes en prsence dune 2 3 degrs de libert. un niveau = 5 %, on obtient t2 = 7.8147 et vu que t2 > exp2 on acceptelhypothse que : = 1.27 / 5 minutes = 0.254 / minute.

Dure des services La dure des services sest rpartie comme suit :DureFrquence[0, 1) 23[1, 2) 20[2, 3) 14[3, 4) 12[4, 5) 9[5, 6) 5[6, 7) 4[7, 8) 5[8, 9) 3[9, 10) 2[10, 11) 2[11, 12) 1[12, ) 0Dure moyenne de service (1 / ) :(0.5 x 23 + 1.5 x 20 + + 11.5 x 1) / 100= 3.27valeur mdianede lintervalle = 1 / 3.27 0.3 / minuteVrifions par un test de 2 si cette hypothseest fonde.

Dure des services Regroupons quelques classes :DureFrquencesFrquencesobservesthoriques (fn) (100 pn) o 0.3

[0, 1) 23 26 9 .3962[1, 2) 20 19 1 .0526[2, 3) 14 14 0 0[3, 4) 12 11 1 .0909[4, 6) 14 14 0 0[6, 8) 9 7.5 2.25 .3000[8, ) 8 9 1 .1111Diffrence :|fn 100 pn |2(fd)fd 100 pnexp2 = 0.9008qui correspond un 2 5 degrs de libert. 5 %, on a t2 = 11.1; on acceptedonc lhypothse.

Caractristiques de la file dattente N = / (1 - ) = 5.52 = / = 0.8467S = 1Temps moyen dattenteN / = 5.52 / 0.3 = 18.4 min.Nombre moyen dunits dans le systmeNombre moyen de clientsunejournede 8 h.0.254 x 8 x 60 = 121.92Temps perdu en attente121.92 x 18.4 min.Temps pendant lequel le caissier est occup121.92 x 3.27 min.Duremoyennede service

Modle S/1// Arrive dune unitLes S stationssont occupes.nonLunitest servieimmdiatementouiLunit attend.

Modle S/1// : nombre moyen dunits dans la file QQ =Temps dattente moyen :Q /

Modle S/1// : nombre moyen de stations inoccupes SISI

Modle S/1// : nombre moyen dunits dans le systme N = Q + S SIN = Q + / Modle S/1// : temps moyen pass dans le systmeQ / + 1 / Note : S P0 e - / La probabilit quil y ait 0 unit dans la file lorsque S est gale 1.

Modle S/1// : probabilit quune unit attende dans la file Prob(N S) = pnn = S =p0 SS n S!n = S =p0 ( / )S S! (1 - )

Exemple : salle durgence dun hpital Arrives de patients suivent un processus de Poisson.Dure de traitement par patient obit une loi exponentielle. = 2 patients / heure = 3 patients / heureQuestion :Doit-on affecter un ou deux mdecins ? / = 2/3 < 1 / 2 = 2/6 = 1/3 < 1S = 1S = 2P01/31/2P12/91/3Pn(2/3)n/3(1/3)nn 2Q4/31 / 12Nombre moyen dunits dans la fileN23/4Nombre moyen dunits dans le systme2/31/24Temps moyen dattente dans la fileNette amlioration

3ime cas : modle S/F/M/Qmax modle 1/1//q Une file dattente de capacit limite q, une station, une source illimite.Lorsquil y a q + 1 units dans le systme, les nouveaux arrivants partent sansrecevoir de service.Ex. : Salle dattente de capacit limite.Taux darrive :n = si n = 0, 1, 2, , q0 si n > qTaux de service :n = pour tout n.Cn =(/)n = nsi n = 0, 1, 2, , q, q + 10 si n > q + 1P0 =[ 1 - ] / [1 - q+2]etPn =[ (1 - ) n] / [1 - q+2] n q + 1

3ime cas : modle S/F/M/Qmax modle 1/1//q N = n Pnn = 0q+1= [ (1 - )] / [1 - q+2] n nn = 0= [ / (1 - )] - [ (q + 2) q+2 / (1 - q+2)] Q = N (1 P0). = taux darrive moyen = q n Pnn = 0= (1 Pq+1)Temps pass dans le systme : N / .Temps dattente dans la file : Q / .

4ime cas : modle S/F/M/Qmax modle s/1//q Une file dattente de capacit limite q, s stations, une source illimite.Lorsquil y a q + s units dans le systme, les nouveaux arrivants partent sansrecevoir de service.Ex. : Salle dattente de capacit limite.Taux darrive :n = si n = 0, 1, 2, , q + s - 10 si n q + sTaux de service :n = nsi n sssi n > sCn =(/)n / n!si n = 0, 1, 2, , s[(/)s (/s)n-s] / s! si n = s + 1, s + 2, , q + s0 si n > q + sOn peut alors calculer P0 et, ensuite, Pn pour tout n = 1, 2, , q + s.etc.

5ime cas : modle S/F/M/Qmax modle 1/1/m/ Une file dattente de capacit illimite, une station, une source limite m.Exemple :Considrons un atelier dans lequel sont utilises m machines identiques quifonctionnent indpendamment les unes des autres. Des pannes se produisentsur ces machines, dune faon alatoire selon une loi de Poisson avec un taux pour chacune.

Pour les rparer, on dispose dun mcanicien qui constitue ainsi la station paro doivent passer les machines. La dure des rparations est distribue selonla loi exponentielle avec un taux .Taux darrive :n =(m - n) si n = 0, 1, 2, , m0 si n mTaux de service :n = si n = 1, 2, , m./ dsigne le facteur de service ou facteur dentretien.o n dsigne le nombre de machines dans le systme (n m).

5ime cas : modle S/F/M/Qmax modle 1/1/m/ Cn =m!(/)n / [(m n)!]si n = 1, 2, , m.Pn = Cn P0 si n = 1, 2, , m.Pour calculer P0, on se sert du fait que : P0 = 1 - P1 - - Pm.mLe nombre moyen dunits dans la file est : (n 1) Pn = m - (1 P0) (1 + / )n = 2mLe nombre moyen dunits dans le systme est : n Pn = m - (1 P0) / n = 0La probabilit dune attente de dure quelconque est : m Pn = 1 P0n = 1

5ime cas : modle S/F/M/Qmax modle 1/1/m/ Le temps moyen dattente dans la file est : nombre moyen dunits dans la filetaux moyen des arrivescest--dire, # moyen dunits dans la file (m - # moyen dunits dans le systme)Le temps moyen dattente dans le systme est :# moyen dunits dans le systme (m - # moyen dunits dans le systme)= [m / (1 P0) - / ] / = [m / (1 P0) (1 + / )] /

6ime cas : modle S/F/M/Qmax modle s/1/m/ Taux darrive :n =(m - n) si n = 0, 1, 2, , m0 si n mTaux de service :n = n si n = 1, 2, , s.s si n = s+1, s + 2, , m.o n dsigne le nombre de machines dans le systme (n m).Gnralisation du cas prcdent : s mcaniciens au lieu dun seul.Pn = m n P0si n = 1, 2, , s n Pn = n! m n P0si n = s + 1, s + 2, , m s! sn-s n etc.

Conclusion Il existe plusieurs autres types de phnomnes dattente avec des lois darriveset/ou de service diffrentes. Mais les principes gnraux demeurent les mmes.Exemples :Un taux de service qui dpend de ltat du systme (n).Des dures de services non exponentielles.etc.