Belkora samir

par BELKORA Samir

1re

anne

Filires AF & ROAD

2014-2015

Institut National de Statistique

et dEconomie Applique

Files dattente

Support de cours

Belkora samir

AVANT-PROPOS

DEFINITION DE LA RECHERCHE OPRATIONNELLE

"La Recherche Oprationnelle consiste en lapplication des mthodes scientifiques pour

rsoudre les problmes complexes rencontrs dans la direction et la gestion de grands

systmes dhommes, de machines, de matriaux et dargent dans lindustrie, le commerce,

ladministration et la dfense. La caractristique de lapproche est le dveloppement dun

modle scientifique du systme (incluant la mesure de facteurs tels que le hasard et le risque)

avec lequel on tente de prvoir et comparer les rsultats de diverses dcisions et stratgies. Le

but est daider la direction dterminer sa politique de manire scientifique"

Cette dfinition a t propose par la Socit de Recherche Oprationnelle de Grande-

Bretagne ; elle conduit aux notions de prise de dcision optimale et de modle.

La dmarche scientifique de la Recherche Oprationnelle peut tre dcrite

schmatiquement de la manire suivante :

Formulation du modle et construction du modle

Rsolution du modle

Test du modle et de la solution

LENSEIGNEMENT DE LA RECHERCHE OPRATIONNELLE

La Recherche Oprationnelle intresse tant les futurs conomistes, que les tudiants des

facults des sciences et les lves ingnieurs. De ce fait, on peut lenseigner de manire trs

diffrente, suivant que lon propose de mettre en relief laspect conomique ou bien les

mthodes mathmatiques ou encore les particularits de programmation des algorithmes

correspondants.

Par ailleurs, sil est incontestable que la Recherche Oprationnelle sappuie sur des

connaissances mathmatiques importantes et varies telles que algbre linaire, thorie des

graphes, probabilits, processus stochastiques, statistiques et quelle ne pourra progresser

que si des spcialistes de haut niveau lui consacrent des efforts de recherche, il est tout aussi

incontestable que ce qui prcde ne couvre absolument pas les besoins des utilisateurs,

socits de service, entreprises et organismes dtat, lorsquils cherchent embaucher un

cadre apte la Recherche Oprationnelle pratique. Pour accder la pratique, il nest pas

suffisant de bien connatre les mathmatiques classiques ; un minimum de notions sur le

fonctionnement et la gestion des entreprises, et une certaine exprience de linformatique sont

requises, sinon il serait vain dattendre un aboutissement rel de toute tude.

Les modules enseigns en Recherche Oprationnelle prsentent des modles et des

techniques mathmatiques. Les techniques mathmatiques sont celles qui ont inventes ou

Belkora samir

largement perfectionnes pour la rsolution des modles, ce qui revient, lorsquon a pu btir

un modle de la ralit, optimiser une certaine fonction en prsence de contraintes multiples

(les chercheurs oprationnels dsirent le plus souvent maximiser ou minimiser une fonction

conomique). Les techniques doptimisation constituent donc lessentiel des mthodes.

Mais laide la dcision quapporte la Recherche Oprationnelle peut concerner des

situations trs diverses. A cela correspond une trs grande diversit de modles et de

techniques de rsolution qui constitueront autant de modules.

APPLICATIONS DE LA RECHERCHE OPRATIONNELLE

Nous allons illustrer des secteurs et des exemples dapplication de la Recherche

Oprationnelle travers les Projets de Fin dEtudes que nous avons encadrs.

2014

Elaboration dun outil dcisionnel doptimisation de la construction des portefeuilles obligataires pour CDG CAPITAL GESTION

Optimisation de la chaine logistique bancaire : cas de la gestion des caisses des agences bancaires du CAM

Etude dopportunit du Transport Ferroviaire Rgional au Maroc - Cas de la zone de Casablanca -

Planification des besoins en composants du produit Mur Rideaux en VEC du projet ARRIBATE Center JET ALU Maroc

Optimisation de la capacit dentreposage de la plateforme des produits finis Cosumar

Optimisation du cot de transport au sein de la plateforme logistique LabelVie Skhirat

Lutilisation des outils de Data Mining pour lexploration dun observatoire du tissu conomique du Maroc

Elaboration dun modle de scoring revolving pour les particuliers de la BCP 2013

Mise en uvre du Revenue Management lONCF

Optimisation de la slection des wagons et de la formation des trains pour le transport fret lONCF

Systme de suivi et modle daffectation multicritre pour les ressources humaines de la Banque Populaire

Modlisation et rsolution du problme d'affectation des ressources humaines de l'ADII sous critres de comptences et de

prfrences

Belkora samir

Optimisation du systme dalimentation en composants au sein de la socit Delphi Packard Tanger

Rationalisation et optimisation de flux de transport national au sein de SJL Maghreb

Optimisation des missions de convoyage de fonds au sein de la direction de DAR AS-SIKKAH

2012

Modlisation et rsolution du problme de la dtection des opportunits darbitrage sur le march financier au sein de la CDG Capital

Optimisation des missions de convoyage de fonds au sein de la direction de Dar As-Sikkah

Optimisation de la gestion du parc automobile du Ple Infrastructure et Circulation lONCF

Modlisation et optimisation de la maintenance du matriel roulant lONCF : cas des rames automotrices Z2M

Elaboration dun schma directeur de la modernisation des gares ferroviaires lONCF

2011

Optimisation du processus de production et dmission de la monnaie Dar As-Sikkah

Lextension du rseau ferr national : quels projets et pour quelles rentabilit ?

Optimisation des encaisses du CIH

Projet de construction dune nouvelle ligne entre Casablanca-Kenitra : Etude de rentabilit financire et socio-conomique

2010

Modlisation et optimisation du processus de production et de vente des utilits IMACID

Approches multicritres pour lallocation des fonds propres de la banque CDG Capital

Prslection du fournisseur et estimation dun prix cible de ngociation pour un choix multicritre dun fournisseur la Direction achats dAttijariwafa Bank

Stratgie dexternalisation Maroc Phosphore Safi : optimisation du processus de dcision et de gestion

2009

De la production la commercialisation du phosphate l'OCP : modlisation, optimisation et automatisation du processus

Equipement des gares ferroviaires en distributeurs automatiques de vente : quelle optimisation pour quelle profitabilit ?

Construction et optimisation d'un portefeuille "Actions" l'aide des algorithmes multicritres au sein de la CMR

Modlisation et conception d'un planning d'affectation du personnel naviguant de la compagnie arienne Atlas-Blue

Contrle de qualit l'export & Gestion du stock l'import Jorf Lasfar

2008

Elaboration d'un modle de rentabilit d'un projet d'externalisation l'usine Maroc Phosphate (OCP Groupe)

Calculs des surfaces de stockages & Optimisation des flux logistiques la SOMACA

Mise en place d'un benchmarking interne pour la mesure des performances des zones et des branches d'Al Amana et

optimisation des ressources

Pilotage et valuation de la performance au sein de la Trsorerie gnrale du Royaume : cas des Directions Gnrales

2007

Choix et gestion d'un projet d'infrastructure pour l'augmentation de la capacit d'une ligne ferroviaire

Etude multicritre des scnarii d'augmentation de la capacit de la ligne Casablanca-Rabat

Essai de modlisation et de rsolution du problme de redploiement du personnel des agences CNSS de la Direction

Rgionale de Rabat-Knitra

Elaboration d'une grille de salaires, d'un systme d'valuation du personnel et d'un systme de primes

Les produits drivs de crdit : mcanismes, pricing et stratgies de couverture

2006

Elaboration d'un outil dcisionnel pour une gestion optimale des placements de la trsorerie de la Caisse Marocaine des

Retraites

La mise en place d'un service d'approvisionnement direct par la mthode MRP-II au sein d'OB Electronique

Elaboration et automatisation d'un planning d'approvisionnement optimal au sein d'HOLCIM MAROC

Optimisation de la gestion des encaisses (AttijariWafabank)

2005

Ralisation et optimisation d'un planning de tches pour l'laboration du projet de Gestion Intgre de la Dpense (GID)

Optimisation du roulement du personnel roulant de l'ONCF

Analyse du systme actuel d'information l'ONCF et optimisation des circuits d'acheminement d'information technique

manant des oprateurs

2001

Optimisation des encaisses dormantes et des circuits de ramassage des fonds au niveau du rseau de la BMCE Bank

Mesure du changement de lefficacit des stations services SHELL entre 1999 et 2000

2000

Elaboration d'un outil d'aide la dcision spcifique la banque : application au cas MRE de la BMCE Bank

1999

Optimisation du Parc Autocars de la CTM

Gestion des Stocks : vers une rationalisation de la politique d'approvisionnement au sein des ateliers centraux Jorf Lasfar

Optimisation du couple rentabilit-risque pour un portefeuille d'OPCVM - Frontire d'efficience de Markowitz (CDVM)

Elaboration dun systme tutoriel intelligent (STI) pour lenseignement de la programmation linaire

Conception et implmentation d'un catalogue en ligne de donnes exprimentales

Belkora samir

SOMMAIRE

I. Introduction aux files dattente

II. Description dun systme de files dattente

a/ Le processus darrive

b/ Le mcanisme de service

III. Classification des systmes de files dattente

IV. Notations, dfinitions et rsultats gnraux

V. Etudes des systmes de files dattente

A. Du systme M/M/1 au systme taux variables

Systme M/M/1

Modle taux variables et processus de naissance et de mort

B. Autres systmes particuliers du modle taux variables

Systme M/M/1/N//GD

Systme M/M/c///GD

Systme M/M/c/N//GD

C. Tous les systmes ne relvent pas du modle taux variables

D. Quelques problmes

Annexe

Files dattente 1

Belkora samir

I. Introduction

Les phnomnes dattente constituent un mal invitable de notre poque. Ces phnomnes de congestion ont toujours

leur source dans des fluctuations du systme : cest parce que dans certaines priodes la demande de service excde loffre

que des files dattente se crent.

La thorie des files a fait lobjet de plusieurs dizaines de livres et de plusieurs milliers darticles (plus de 2000

recenss en 1914). Les premiers travaux dans ce domaine remontent K. Erlang qui tudia (de 1909 1920) les problmes

du rseau tlphonique de Copenhague. La thorie mathmatique des files dattente sest ensuite dveloppe grce aux

apports de Palm, Kolmogoroff, Khintchine, Pollackzeck et Kendall.

Le but de ce cours est de donner ltudiant une ide des diffrentes mthodes de solutions, des diffrentes modles

mathmatiques adapts aux situations varies dans lesquelles des files dattente peuvent tre observes.

Exemple de problmes de files dattente :

1/ Combien faut-il construire de lignes tlphoniques de manire ce que lattente pour obtenir une communication ne

soit pas trop grande sans effectuer cependant des investissements inutiles (lignes totalement ou presque totalement

inutilises) ?

2/ Combien faut-il prvoir de comptoirs dans un supermarch ? Comment peut-on adapter le nombre de vendeuses au

nombre de clients ? Convient-il de faire des comptoirs spciaux pour les clients ne prenant quun nombre limit

darticles ? On a un problme de mme type dans un bureau de poste, une banque, une gare

3/ Combien faut-il construire de pistes dans un arodrome de manire ce que le temps dattente latterrissage et au

dcollage ne soit pas excessif ? Conviendrait-il de donner la priorit certains types dappareils ? Quelles seront les

consquences de cette priorit sur le temps dattente des appareils non prioritaires ?

4/ Quel est, du strict point de vue du temps dattente total des automobilistes, le meilleur quipement dun carrefour : feux

de signalisation ou signal stop sur certains voies ? Si on adopte la solution de feux de signalisation, quel est le meilleur

rglage de ces feux ?

5/ Combien construire de postes de page un page autoroute ? Quelle surface prvoir pour lattente des

automobilistes ?

6/ Dans une usine, un certain nombre de machines sont susceptibles de tomber en panne. Combien de rparateur doit-il y

avoir pour que le fonctionnement de lusine ne soit pas trop perturb, compte tenu du fait que chaque rparateur reoit un

salaire mme quand les machines fonctionnent ? Si certaines machines sont plus importantes que dautres pour le

fonctionnement de lusine, convient-il de leur donner une priorit dans leur traitement ? Faut-il interrompre la rparation

Files dattente 2

Belkora samir

dune machine moins importante pour soccuper dune machine plus importante qui vient de tomber en panne ?

7/ Combien organiser un systme multi-processeur, un systme de temps partag, un rseau dordinateurs ? Doit-il y avoir

des travaux prioritaires ?

II. Description dun systme de files dattente

Une file dattente peut se dcrire comme un systme o des clients arrivent un "guichet" pour recevoir un service.

A la lumire des exemples prcdents, on voit que les clients peuvent tre de toutes sortes (appels tlphoniques, clients de

magasin, avions, automobiles, machines, travaux), de mme que le guichet o le service peut tre rendu (central

tlphonique, comptoir de supermarch, piste darodrome, carrefour, poste de page, rparateur, processeur).

Si la demande du service est importante, le client peut avoir attendre que dautres clients soient servis. Dans ce cas,

les clients perdront du temps et le serveur au guichet sera trs occup. Si, par contre, la demande du service est rare, le

client a de fortes chances dtre aussitt servi mais le serveur au guichet sera mal occup. Lobjectif de la thorie des files

dattente est dobtenir un certain dquilibre dans ce genre de situation en tenant compte :

- des fluctuations alatoires enregistres habituellement dans les arrives des clients et dans la dure du service

- des divers cots relatifs la perte du temps par les clients et lamlioration dun service (le bnfice dun service rapide

tant hors de proportion avec le cot que ncessiterait cette action, il faut se rsigner partager cette opration avec

dautres demandeurs).

Un systme de files dattente est caractris par :

- le processus darrive des clients

- le mcanisme (les caractristiques) du service (dure du service, disponibilit et nombre des serveurs)

- la discipline dattente.

a/ Le processus darrive :

On admet le plus souvent que les clients arrivent indpendamment les uns des autres cest--dire que les intervalles

de temps sparant les arrives de deux clients successifs sont des variables alatoires indpendantes ayant mme loi.

Les lois suivantes sont les plus connues :

Arrives rgulires :

Les clients arrivent intervalles rguliers (ce cas se rencontre dans la pratique dans une chane de montage, par exemple,

o les pices se prsentent devant les ouvriers toutes les secondes).

Ce processus darrive est reprsent symboliquement par la lettre D (dterministe).

Arrives "compltement alatoires" (ou poissoniennes) :

Cest le cas o les instants darrive forment un processus de Poisson.

Ce processus est dit compltement alatoire parce que la probabilit pour quune arrive se produise dans un intervalle

[t , t + t] est indpendante de t, cest--dire du temps qui sest coul depuis larrive prcdente.

Un grand nombre de phnomnes rels sont aussi parfaitement dpourvus de mmoire et suivent donc un processus de

Poisson (ex : instants dappels de communications tlphoniques).

Ce processus est reprsent par la lettre M (markovien).

Arrives suivant une loi dErlang dordre k :

Il sagit dun processus darrive qui peut se driver du processus de Poisson de la manire suivante :

des clients (fictifs) arrivent suivant un processus de Poisson et on ne retient comme clients rels que ceux dont le rang

darrive est k, 2k, 3k

Files dattente 3

Belkora samir

Ce processus est reprsent par le symbole Ek (Erlang dordre k).

Arrives suivant une loi gnrale :

Si la distribution (observe) de lintervalle de temps sparant deux arrives successives ne peut tre ajuste aucune des

lois prcdentes, on dit quon a une loi gnrale.

Ce processus est reprsent par les lettres GI (General Independant).

Autres arrives :

- arrives par paquets ou par groupes (les instants darrive suivront un des processus dcrits ci-dessus tandis que le

nombre de clients arrivant chacun de ces instants sera lui-mme une variable alatoire ; ex : arrives une station

dautobus)

- arrives rgulires avec absence de ponctualit (dviation alatoire autour de lhoraire : arrive sur RDV chez un

mdecin, un dentiste)

- clients impatients ne figurant pas dans le modle darrive.

b/ Le mcanisme de service :

On fait le plus souvent lhypothse que les dures de service dun mme serveur sont des variables alatoires

quidistribues. On peut avoir :

Services rguliers :

Tous les services ont la mme dure (si le "serveur" est une machine, par exemple une presse dans un atelier ou une

machine distribuer un caf).

Cette loi est reprsente par la lettre D.

Services exponentiels :

Les dures de service suivent un loi exponentielle. Cette loi sapplique assez bien de nombreux cas concrets (en

particulier la dure des appels tlphoniques locaux ; pour les appels interurbains ou internationaux, la tarification a pour

effet de donner un grand nombre dappels dans lintervalle [0 , 3 minutes]).

Cette loi est reprsente par la lettre M.

Services suivant une loi dErlang dordre k :

Si le service consiste en la succession doprations lmentaires dont les dures sont indpendantes et suivent une loi

exponentielle, la dure totale du service suit une loi dErlang dordre k. Les lois dErlang sont en fait utilises dans un

grand nombre de situations relles o les conditions ci-dessus ne sont pas remplies car elles peuvent tre ajustes de

manire satisfaisante une large classe de distributions observes.

Cette loi est reprsente par le symbole Ek.

Services suivant une loi gnrale :

Cette loi est reprsente par la lettre G.

Pour dcrire compltement le mcanisme de service, il faut encore indiquer la disponibilit du service (les guichets

peuvent ne pas tre disponibles constamment par suite du repos des serveurs ou dincidents) et le nombre de serveurs.

c/ Le mcanisme de service :

- La discipline dattente la plus courante est "premier arriv, premier servi" (FIFO : First In, First Out / FCFS : First

Come, First Served).

- La rotation des articles dans un conglateur, le traitement des pices quon empile avant dusiner suivent la discipline

"dernier arriv, premier servi" (LIFO : Last In, First Out / LCFS : Last Come, First Served).

Files dattente 4

Belkora samir

- Dautres disciplines peuvent se rencontrer galement, par exemple la slection au hasard dune unit en attente, cas

frquent dans les systmes de tlphonie (RSS : Random Selection for Service / SIRO : Service In Random Order).

- GD (General Discipline) : pour indiquer indiffremment les trois disciplines cites plus haut.

- Dautre part, des rgles de priorit peuvent exister (PR).

Les clients peuvent appartenir des classes diffrentes, une unit de classe i ayant priorit sur une unit de classe j si i < j

(avions demandant la piste pour latterrissage, travaux dans un systme informatique).

On distingue la priorit relative ("non preemptive priority") pour laquelle larrive dune unit prioritaire ninterrompt pas

le service en cours de la priorit absolue ("preemptive priority") pour laquelle le service en cours est interrompu.

Remarques :

- Dans un systme de files dattente pour lequel les dures de service des clients sont indpendantes, on peut dmontrer le

rsultat suivant (qui est dailleurs intuitif) : quelle que soit la discipline dattente ( lexclusion de la priorit absolue), le

temps total pass dans le systme par lensemble des clients est le mme.

La rgle "premier arriv, premier servi" correspond un critre dquit en ce sens que cette rgle minimise la variance

des dures de sjour.

- Lorsquil y a plusieurs serveurs et que chacun dentre eux peut servir indiffremment chaque client, on peut :

. crer une file dattente unique ; le premier client de la file devant tre servi est affect au premier serveur libre

. avoir une file dattente par serveur (avec possibilit pour un client daller dune file une autre)

. affecter les clients aux serveurs par rotation : le client de rang n va la ime

station sil ya S stations et si

III. Classification des systmes de files dattente

La plupart des files dattente quon rencontre peuvent tre caractrises par une squence de 6 symboles (Confrence

Internationale sur la standardisation des notations dans la thorie des files dattente - 1971), qui dsigne la nomenclature

des modles :

Files dattente 5

Belkora samir

a / b / c / d / e / f

o :

a = processus darrive (D , M , Ek , GI)

b = processus de service (D , M , Ek , G)

c = le nombre de serveurs (ou guichets)

d = la borne suprieure du nombre de clients dans le systme (capacit)

e = le nombre de clients

f = la discipline dattente (FIFO/ FCFS, LIFO/LCFS, RSS/SIRO, PR, GD)

Ainsi (M/M/S///FCFS) dsigne une file dattente o

-

-

-

-

-

-

Dans les cas (les plus courants) o les trois derniers symboles sont //FCFS, on se contente des trois premiers

(notation de Kendall). Ainsi, la file dattente ci-dessus sera dsigne par (M/M/1).

IV. Notations, dfinitions et rsultats gnraux

"Rsoudre" un problme de file dattente consiste donner :

- la distribution du nombre de clients prsents dans le systme (files + service) chaque instant. Xt dsigne le nombre de

clients prsents dans le systme linstant t.

Remarque : {t [0 , T] / Xt = 0} est le temps doisivet du serveur.

- la loi de la "dure de sjour" (temps total pass dans le systme) du nime

client. Wn dsignera la dure de sjour du nime

client.

- ventuellement, la loi des priodes doccupation (busy periods) cest--dire des priodes pendant lesquelles le serveur est

occup.

Malheureusement, la solution mathmatique complte dun systme de file dattente est inextricable. Cependant,

dans de nombreux cas, le systme atteint assez vite un rgime "stationnaire" (on dit aussi "permanent") cest--dire que la

distribution de Xt (et des autres grandeurs quon dsire connatre) tend vers une distribution limite, indpendante de ltat

initial lorsque t augmente indfiniment. Ce rgime stationnaire, sil existe, est en gnral plus facile tudier. On ne va

donc pas sintresser aux files dattente dans leur phase transitoire, mais lorsquelles sont en rgime stationnaire.

Dans la pratique, on est intress par le fonctionnement du systme sur une priode finie. Ltude du rgime

stationnaire nest cependant pas dpourvue dintrt car la priode dtude est en gnral assez longue par rapport la

dure du rgime transitoire et les distributions limites donnent alors une bonne approximation de la ralit.

Dautre part, et ceci est trs gnral, les distributions limites donnent des indications sur la structure du

fonctionnement du systme (indications pures des conditions initiales).

Cependant, dans certains cas, lhypothse de stationnarit pourra tre compltement inadquate (si on cherche, par

exemple, tudier comment la demande de pointe se rsorbe aprs lheure de pointe). Dans ce cas, les techniques de

simulation seront souvent les seules utilisables.

Files dattente 6

Belkora samir

Dfinition :

On dsignera par le "taux darrive des clients" cest--dire que 1/ sera gal lesprance de lintervalle de temps

sparant deux arrives conscutives.

On dsignera par le "taux de service" cest--dire que 1/ sera gal lesprance de la dure de service.

Le rapport sans dimension

(resp. = quand 1 serveur (resp. c serveurs)

1

)1 c

est appel "intensit du trafic" et sexprime en Erlangs (ce nom est souvent utilis en tlphonie).

Exemple :

Considrons des pices qui dfilent sur un tapis roulant au taux de pices par heure (cest--dire que lintervalle de temps

sparant le passage de deux pices conscutives est 1/ heures).

Chaque fois quune pice passe devant une certaine machine, la pice doit tre emboutie. La machine emboutir peut

traiter au maximum pices par heure (cest--dire que la dure de lopration est 1/ heures).

On a ici un systme D/D/1 qui nest pas proprement parler une file dattente puisquil ny a pas fluctuation.

Cependant, on peut faire au sujet de ce systme la remarque lmentaire suivante :

- si le temps sparant larrive de deux clients conscutifs est suprieur ou gal la dure du service (cest--dire si 1),

chaque client trouvera son arrive le guichet (serveur) libre et sa dure dattente sera nulle ; le systme sera stable.

- si le temps sparant larrive de deux clients conscutifs est infrieur la dure du service (cest--dire si > 1), le

serveur ne suffit pas la tche et la file dattente va crotre, en principe indfiniment ; le systme sera instable.

On verra que cette proprit de stabilit stend assez facilement une file dattente quelconque :

- Quand < 1, le systme est stable. La distribution du nombre de clients dans le systme (ainsi que celle du temps de

sjour) tend vers une distribution limite indpendante des conditions initiales (tat stationnaire).

- Quand 1, le systme est instable (except si la capacit du systme est limite). Le nombre de clients dans le systme

(ainsi que la dure de sjour) augmente indfiniment avec t. Il ny a pas de distribution limite.

Ainsi, en ce qui concerne la "rgularit" dun systme de file dattente, ce quon peut dire du cas trivial D/D/1 se

gnralise sauf dans le cas o lintensit du trafic est gale 1.

Il faut galement noter que ltat stationnaire est atteint au bout dun temps dautant plus long que est proche de 1.

Dfinition :

On pose :

. t1, t2, t3, instants darrive des clients

. 1, 2, 3, instants de dpart des clients

. n = lim (P(Xt = n)) quand t + : probabilit pour quil y ait n clients dans le systme dans ltat stationnaire

. L : nombre de clients dans le systme dans ltat stationnaire.

On a : n = P(L = n) ( ltat stationnaire, la loi de L est celle de Xt)

. Lq : nombre de clients en attente dans ltat stationnaire

si L c

Lq = c : nombre de serveurs

si L < c

Files dattente 7

Belkora samir

. W : dure de sjour dans ltat stationnaire Wn

. Wq : dure dattente dans ltat stationnaire Wn

q

. S : dure de service Sn

Wn =

. Tn : temps qui spare les arrives du nime

et du n + 1ime

client

si Tn Wnq + Sn

Wn + 1q =

sinon

Rsultats gnraux :

- On peut reprsenter lvolution dune file dattente par le diagramme suivant (avec la discipline "premier arriv, premier

servi") :

- Considrons le systme pendant une priode T assez longue. On peut valuer de deux manires laire de la surface ci-

dessus :

.

o L(T) reprsente le nombre moyen de personnes dans le systme pendant la dure T

.

o A(T) reprsente le nombre moyen de clients arrives pendant la dure T

W(T) reprsente la dure moyenne de sjour des clients arrivs pendant la dure T

le terme correctif tient compte des clients qui taient arrivs avant le dbut de la priode et dont le service nest pas

achev au dbut de la priode et de ceux dont le service nest pas achev la fin de la priode

do :

Le terme correctif reste born quand T augmente ; donc si on divise les deux nombres de cette quation par T et quon fait

augmenter T, on a1 :

A(T) 1

L(T) W(T) T T

1 Loi des grands nombres (Thorme de Bernouilli 1800) :

X1, , Xn n variables alatoires indpendantes, de mme loi pX, de mme esprance m, de mme cart-type et soit1 nX ... XY

n

.

On a : P(Y m) > ) 0 quand n ce qui signifie Y m quand n .

Xt

T

t1 t2 t3 1 2 t4 3 4 t5 t6 t7 t8 5 t9 t10 6 7 8 9 10 t

T +

Files dattente 8

Belkora samir

do :

Formule de Little

reprsente le taux darrive moyen des clients. Si le taux darrive des clients est constant le long du processus darrive

et gal , on a bien sr .

Entre les quatre quantits E(L), E(Lq) E(W) et E(W

q), on a aussi les trois relations suivantes :

. Le mme raisonnement que prcdemment avec le nombre moyen de personnes en attente et la dure moyenne dattente

conduit la formule suivante :

. Comme Wn = Wnq + Sn, si le taux de service est constant le long du processus, on obtient en prenant les esprances :

. En combinant les trois quations prcdentes, on trouve :

V. Etude des systmes de files dattente

A. Du systme M/M/1 au modle taux variables

Systme M/M/1 :

Arrives poissoniennes avec taux darrive des clients

Dures de service exponentielles avec taux de service

1 serveur

Rgime stationnaire : = / < 1

La solution est donne par :

0 = 1 -

n = 0n = (1 - )n 0 < n

Dmonstration :

Les arrives sont poissoniennes de paramtre arrives par unit de temps :

Files dattente 9

Belkora samir

Les dures de service suivent une loi exponentielle de paramtre services par unit de temps i.e desprance de dure

de service 1/ :

Soit maintenant P(Xt+h = n) = Pn(t + h) la probabilit quil y ait n clients (n > 0) dans le systme t + h :

Files dattente 10

Belkora samir

On a aussi les rsultats suivants :

E(L) =

Files dattente 11

Belkora samir

E(Lq) =

En utilisant les formules de Little :

E(L

q) =

E(W) =

E(Wq) =

Remarques :

- On montre que dans le systme M/M/1, la variable W (dure de sjour des clients dans le systme dans ltat

stationnaire) suit une loi exponentielle de paramtre (1 ) = - .

- Tout ceci est valable dans le systme M/M/1///GD.

- Considrons le systme pendant un temps T assez long.

La dure T ' pendant laquelle le serveur sera occup est gale au nombre de clients arrivs pendant T, A(T), multipli par le

temps moyen M(T) de service de ces clients plus un terme correctif dans lequel on tient compte des clients qui taient

arrivs avant le dbut de la priode et dont le service nest pas achev au dbut de la priode et de ceux dont le service

nest pas achev la fin de la priode :

Le terme correctif reste born quand T augmente ; donc si on divise les deux nombres de cette quation par T et quon fait

augmenter T, on a2 :

A(T)T' 1

M(T) T T T

On retrouve ainsi le rsultat dmontr prcdemment :

0 =

Exemple :

Considrons une station service avec une pompe essence. Les clients arrivent suivant un processus de Poisson au rythme

de 10 lheure (lesprance de lintervalle de temps sparant deux arrives conscutives est donc 6 mn) tandis que la dure

de service suit une loi exponentielle de paramtre m = 12 (lesprance de la dure de service est donc 5 mn).

On a :

En particulier, la probabilit pour quil y ait 3 personnes ou plus sera :

2 Cf. la Loi des grands nombres en note 1 page 7

T +

Files dattente 12

Belkora samir

Modles taux variables et processus de naissance et de mort :

On rappelle que dans le systme de files dattente M/M/1o est le taux darrive et est le taux de service, on

aboutit aux quations dtat :

'n n 1 n 1 nP (t) P (t) P (t) ( )P (t) n > 0

'0 0 1P (t) P (t) P (t)

o Pn(t) est la probabilit quil y ait n clients dans le systme au temps t.

On se propose dtudier maintenant le modle taux variables o :

- les arrives suivent une loi de Poisson de moyenne j, j tant le nombre de clients dans le systme

- les dures de service suivent une loi exponentielle de moyenne 1/j

- les autres caractristiques sont celles du systme M/M/1.

Pour ce modle taux variables, les formules de n (probabilit quil y ait n clients dans le systme ltat

stationnaire) et de 0 scrivent :

0 1 n 1

n 01 2 n

...

...

11 n 10 0 1 0 1 2 i

01 1 2 1 2 3 i 1n 1 i 0

1 ... 1

n nn 0

Dmonstration :

Files dattente 13

Belkora samir

Application :

Donner lexpression de 0 et n au cas o jj 1

et j = pour j = 0, 1, 2, (file avec dcouragement des clients).

Les rsultats du modle taux variables sont fondamentaux puisquil correspond, comme on va le voir, au processus de

naissance et de mort et quun grand nombre de problmes de files dattente sont rsolus laide de ce modle.

Processus de naissance et de mort :

On a un systme discontinu tel que 0, 1, , N (N fini ou infini) reprsentent ses tats possibles.

Le processus de naissance et de mort, cas particulier des processus de Markov, est un processus homogne dans le temps,

ayant les caractristiques suivantes :

1/ Les seuls sauts possibles sont ceux vers les tats immdiatement voisins : de j j + 1 ou j - 1 si 0 < j < N, de 0 1 et

enfin de N N - 1.

2/ Si linstant quelconque t le systme est ltat j, la probabilit conditionnelle de passer ltat j + 1 dans lintervalle

dt qui suit est constante et gale jdt (j 0) o j est le coefficient de naissance correspondant une arrive.

3/ Si linstant quelconque t le systme est ltat j, la probabilit conditionnelle de passer ltat j - 1 dans lintervalle

dt qui suit est constante et gale jdt (j 0) o j est le coefficient de mort correspondant un dpart.

4/ La probabilit de plus dune transition dans cet intervalle dt, infiniment petit, est un infiniment petit dun ordre

suprieur 1 donc celui des probabilits prcdentes.

Le schma caractrisant le processus de naissance et de mort (ou graphe de transition des tats du systme) est le suivant :

Avec le principe de conservation des flux, on obtient directement les quations :

Ces quations dfinissent le processus de naissance et de mort et on les reconnait comme tant les quations dtat en

rgime stationnaire du modle taux variable !

Files dattente 14

Belkora samir

Remarques :

Au lieu de traiter le modle taux variables et ensuite le systme M /M/1 et les systmes qui vont suivre comme cas

particuliers, nous avons prfr prsenter le modle M/M/1, ensuite gnraliser avec le modle taux variables et enfin

traiter les systmes qui vont suivre comme cas particulier de ce dernier. La raison de cette dmarche rside dans le fait que

la dmonstration du modle M/M/1 est plus simple apprhender demble

Pour traiter le systme M/M/1 comme un cas particulier (limite) du modle taux variables, il suffit de prendre :

Le modle taux variables tant lui-mme un cas particulier des processus de Markov, il peut tre bien sr trait comme

tel.

B. Autres systmes particuliers du modle taux variables

Systme M/M/1/N//GD :

Arrives poissoniennes avec taux darrive des clients

Dures de service exponentielles avec taux de service

1 serveur

Le nombre maximum de clients dans le systme est limit N

Rgime stationnaire : = /

La solution est donne par :

1 : = 1 :

0 N 1

1

1

0

1

N 1

n n

n 0 N 1

1 0 < n N

1

nn 0

1 0 < n N

N 1

n = N < n n = N < n

Dmonstration :

1re

dmarche :

Files dattente 15

Belkora samir

2de

dmarche :Utilisation du modle taux variables

Files dattente 16

Belkora samir

On a aussi les rsultats suivants :

E(L) =

Pour 1 :

Pour = 1 :

E(Lq) =

Formules de Little avec

E(Lq) =

E(W) = E(Wq) =

Systme M/M/c///GD :

Arrives poissoniennes avec taux darrive des clients

Dures de service exponentielles avec taux de service

c serveurs

Rgime stationnaire : = /c < 1

La solution est donne par :

11 c 12 c 1 c n c

0

n 0

(c ) (c ) (c ) (c ) (c )1 c ...

2! (c 1)! c! (1 ) n! c! (1 )

n

0(c )

0 n cn!

n =

c n

0c

c nc!

Dmonstration :

Files dattente 17

Belkora samir

On a aussi les rsultats suivants :

E(Lq) =

E(L) =

Formules de Little avec

E(L) =

E(W) = E(Wq) =

Exemple :

Reprenons lexemple de la station service (page 11). Si on ajoute une seconde pompe de caractristiques identiques

celles de la premire, on aura :

Files dattente 18

Belkora samir

Systme M/M/c/N//GD :

Arrives poissoniennes avec taux darrive des clients

Dures de service exponentielles avec taux de service

c serveurs

Le nombre maximum de clients dans le systme est limit N

Rgime stationnaire : = /c

La solution est donne par :

1c 1 n c N c 1

0

n 0

(c ) (c ) 1 pour 1

n! c! 1

1c 1 n c

n 0

c c(N c 1) pour 1

n! c!

n

0(c )

0 n cn!

c n

0c

c n Nc!

0 N < n

Dmonstration :

n =

Files dattente 19

Belkora samir

On a aussi les rsultats suivants :

E(L) =

Pour 1 :

Pour = 1 :

Formules de Little avec

E(Lq) =

E(W) =

E(Wq) =

Files dattente 20

Belkora samir

C. Tous les systmes ne relvent pas du modle taux variables

On considre un systme simplifi de files dattente avec deux guichets disposs en srie comme le montre la figure

suivante :

Un client, pour tre servi, doit passer par le guichet 1 puis par le guichet 2.

Les dures de service chaque guichet suivent une loi exponentielle avec le mme taux de service .

Les arrives suivent une loi de Poisson avec un taux darrive (on pose : = /).

Chaque guichet peut tre libre ou occup. Aucune queue nest autorise devant le guichet 1 ou le guichet 2. Si le client

accomplit son service au guichet 1 avant que le guichet 2 ne soit libre, il ne peut attendre entre les deux guichets puisque

ce nest pas autoris ; dans ce cas, le guichet 1 est dit "bloqu".

1. Etablissons pour ce systme les quations dtat :

En reprsentons un tat du systme par un couple (i , j) o i est ltat du guichet 1 et j est ltat du guichet 2, les tats

possibles du systme sont :

Etablissement des quations dtat par le tableau cartsien des probabilits de transition :

En ngligeant les termes en h2, on a alors :

Les quations dtat en rgime stationnaire sont alors, en posant = / :

Guichet 1 Guichet 2

Systme

entre sortie

Files dattente 21

Belkora samir

Etablissement des quations dtat par le graphe de transition des tats :

2. Dduisons les probabilits des diffrents tats possibles du systme ainsi que E(L), E(Lq), E(W), E(W

q).

Files dattente 22

Belkora samir

Problme 1 :

On se propose dtudier le systme de files dattente M/M/ o le nombre de serveurs est illimit.

1. Etablir p ce modle les formules de n (probabilit quil y ait n clients dans le systme ltat stationnaire) et 0.

2. En dduire E(L), E(Lq), E(W) et E(W

q).

3. Ce modle est appel "modle self-service".

- Pourquoi ?

- Le cas du guichet de banque automatique rentre-t-il dans cette catgorie de modle ? Expliquez votre rponse.

Files dattente 23

Belkora samir

Problme 2 :

On se propose dtudier le systme M/M/c//K/GD (finite calling source).

Files dattente 24

Belkora samir

Problme 3 :

Un rparateur soccupe de m machines-outils qui de temps en temps tombent en panne. Le taux de panne dune machine-

outil est gal et le flux de panne est poissonien.

Si linstant o se produit la panne le rparateur est libre, il sattaque immdiatement au rglage, sinon la machine-outil

est mise dans la file pour le rglage. Le temps de rglage obit la loi exponentielle de paramtre .

1. Donner la liste des tats possibles.

2. Etablir les quations dtat du systme en rgime stationnaire.

3. Dterminer la distribution stationnaire (il nest pas ncessaire dutiliser la question 2).

4. On tudie les caractristiques du systme :

4.1 Donner la probabilit pour que le rparateur soit occup.

4.2 Donner le nombre de machines-outils (effectivement) rgles par le rparateur par unit de temps.

4.3 Que reprsente E(L) ? m E(L) ? (m E(L) ?

4.4 Utiliser 4.2 et 4.3 pour en dduire E(L).

4.5 Dterminer E(Lq).

Files dattente 25

Belkora samir

Problme 4 :

Des personnes vont un distributeur de billets selon un processus de Poisson de taux = 1 personne/minute. Ce

distributeur met un temps distribu exponentiellement de moyenne 1/ = 1 minute. Les clients entrant le guichet sont

impatients et partent tout de suite sans prendre de billet avec une probabilit pdpart(n) = n/3 o est n est le nombre de

personnes devant le distributeur.

2.1 Combien de personnes peuvent se trouver devant le distributeur au maximum ?

2.2 Etablir les quations dtat en rgime transitoire (i.e. les quations diffrentielles qui rgissent les Pn(t), probabilits

davoir n clients devant le distributeur).

2.3 En dduire les quations dtats en rgime stationnaire.

2.4 Donner la distribution stationnaire.

2.5 Calculer le nombre moyen de clients devant le distributeur, le dbit moyen des clients qui repartent avec des billets

(et celui de ceux qui repartent sans) et le temps de sjour moyen devant le distributeur.

Files dattente 26

Belkora samir

Annexe :

Dans le systme M/M/1, les dure de service suivent une loi exponentielle de paramtre services par unit de temps i.e desprance de

dure de service . Pour sa dmonstration, on a utilis lapproximation q1(h) h o qn(t) reprsente la probabilit davoir n fins de

service (ou dparts) durant t.

On va montrer que q0(t) = e-t et, mieux encore, que les fins de service suivent la loi de Poisson de paramtre . Nous allons effectuer

tout dabord une tude de la loi exponentielle.

Les dures de service suivent la loi exponentielle de paramtre . Soit S la variable alatoire qui reprsente les dures de service. On a :

e-t t 0 fS(t) =

0 t < 0

P(S t) = 1 e-t P(S > t) = e-t E(S) = Var(S) =

Prop 1 : P(0 S t) > P(t S t + t)

Prop 2 : Absence de mmoire : P(S > t + t / S > t)) = P(S > t) t, t 0

Prop 3 : S1, S2, , Sn variables alatoires indpendantes exponentielles de paramtres 1, 2, , n.

S = min {S1, S2, , Sn}

S suit une loi exponentielle de paramtre

La dure de service est lintervalle de temps qui spare deux fins de service (dparts) conscutives. Considrons qn(t) la

probabilit davoir n fins de services (ou dparts) durant t. On a :

1

n

1j

j

12

1

fS(t)

0 t

Files dattente 27

Belkora samir

Nous allons pousser plus loin et montrer que les fins de service suivent la loi de Poisson de paramtre .

Considrons N clients dans le systme. On a :

n = 0 :

n = 1 :

Ainsi, on a montr la proprit suivante :

Si les intervalles entre les vnements suivent la loi exponentielle de taux , alors le phnomne stochastique est distribu

selon la loi de Poisson de taux .