EXPOSE PROCESSUS STOCHASTIQUE MODELE DE FILES DATTENTE Corrigé ERIC [PDF]

Zitiervorschau

République du Bénin Fraternité-Justice-Travail

∞∞∞∞∞∞∞ UNIVERSITE D’ABOMEY-CALAVI ∞∞∞∞∞∞∞

Ecole Nationale d’Economie Appliquée et de Management (ENEAM) ∞∞∞∞∞∞∞

MASTER EN STATISTIQUES ET ECONOMIE APPLIQUEE Année : II

EXPOSE DE PROCESSUS STOCHASTIQUES

THEME

MODELES DE FILES D’ATTENTE

Présenté par Roméo ADJOVI Brigitte B. BATONON Eric K. TCHINTCHIN Dorinali YALLA-BONI

Professeur Mustapha SANNI

Janvier 2010

PLAN INTRODUCTION 1. GENERALITES 1.1. Processus de Markov 1.2. Processus de naissance et de mort 2. MODELES DE FILES D’ATTENTE 2.1. Description d’un modèle de file d’attente 2.2. Files d’attente formant un processus de naissance et de mort 3. ETUDE DE CAS 3.1. Application 1 : file d’attende de type M/M/s 3.2. Application 2 : file d’attente de type

(

)

CONCLUSION BIBLIOGRAPHIE

2

INTRODUCTION Les origines de la théorie des files d’attente remontent à 1909 à l’époque où A. K. Erlang en a posé les bases dans ses recherches sur le trafic téléphonique. Ses travaux ont par la suite été intégrés à la recherche opérationnelle. Malheureusement, les publications sur la théorie des files d’attente ont adopté un langage de plus en plus mathématique, ce qui a freiné l’utilisation de cette théorie. En effet, Palm, Pollaczek, Khintchinne, Kolmogorov etc. ont publié beaucoup de résultats de recherches qui les placent au rang des précurseurs de l’usage des mathématiques pour résoudre les problèmes de files d’attente. La situation a toutefois changé quand des gens ont commencé à appliquer la théorie des files d’attente à l’évaluation des performances. Pour ce type d’applications, il est apparu que même des modèles de files d’attente relativement simples fournissaient des résultats qui correspondaient de près aux observations réelles. On assista alors à une évolution rapide de la théorie des files d’attente qu’on appliqua alors à l’évaluation des performances des systèmes informatiques et aux communications. Aujourd’hui, la théorie des files d’attente fait partie intégrante de l’évaluation des performances des systèmes informatiques. Les chercheurs œuvrant dans cette branche d’activité ont élaboré plusieurs nouvelles méthodes qui ont ensuite été appliquées avec succès dans d’autres domaines, notamment dans le secteur de la fabrication. On a aussi constaté une résurgence des applications pratiques de la théorie des files d’attente dans des secteurs plus traditionnels de la recherche opérationnelle, un mouvement mené par Peter Kolesar et Richard Larson. Grâce à tous ces développements, la théorie des files d’attente est aujourd’hui largement utilisée et ses applications sont multiples. Voici une liste non exhaustive de problèmes concrets abordés par la théorie des files d’attente : - Combien de lignes téléphoniques doit-on gérer pour que l’attente de communication soit raisonnable ; - Comment gérer les feux de circulation dans une agglomération afin d’obtenir un trafic fluide ; - Combien de caisses (guichets) doit-on implanter dans une boutique (péage) pour diminuer le temps d’attente des clients ; - Gestion optimale des stocks d’une entreprise ; - En génétique dans la reconnaissance des génomes d’un individu ; - Dans la reconnaissance de la parole ; - Etc.

1. GENERALITES

1.1.

Processus de Markov

+ un processus aléatoire à valeurs entières. On dit que le processus * Soit * + est un processus de Markov si, pour tout (

)

(

).

En d’autres termes, un processus de Markov est un processus ayant la propriété suivante :

3

-

-

La loi conditionnelle de la variable future sachant l’état présent et toute l’histoire du processus jusqu’au temps ne dépend que du présent et est indépendante du passé ; ( ) Si, de plus ( ) ne dépend pas de , le processus * + est dit homogène.

1.2.

Processus de naissance et de mort

Pour mieux apprécier cette notion, on se met dans le cas hypothétique où l’on cherche à modéliser ou décrire un système de file d’attente, en tenant à la fois compte des naissances et décès des clients/ pièces qui la composent. Supposons le taux d’arrivée des clients/ pièces et le taux de service lorsque le système est à l’état i. Dans un petit intervalle de temps , la transition de correspond à une naissance avec la probabilité et la transition de correspond à un décès avec la probabilité , et rien ne se produit avec une probabilité , ( )- . On dit que le processus des arrivées est un processus de naissance et celui de service un processus de mort. On a le diagramme de transition suivant :

Les taux de naissance

et de mort

sont tels que

et

.

2. MODELES DE FILES D’ATTENTE

2.1.

Description d’un système de file d’attente

2.1.1. Définition Un système de file d’attente se décrit par un processus d’arrivée de clients, un mécanisme de service et une discipline d’attente. Il est caractérisé par : a) Un flux d’arrivée : qui représente les instants où arrivent les « clients » (terme générique représentant aussi bien des pièces de fabrication, des véhicules, des appels à la mémoire d’un ordinateur, sollicitations de l’organe central d’un réseau téléinformatique, …). En première approximation, on considère souvent que les délais entre les arrivées sont des variables aléatoires indépendantes équidistribuées. Les durées inter-arrivées (Xn)n  1 sont donc indépendantes. Le flux est alors ce qu’on appelle un processus de renouvellement stationnaire. Le cas le plus simple est celui où la loi commune est la loi exponentielle, le flux d’arrivée est alors un processus de Poisson. Nous supposons de plus que ces variables sont de même loi : le processus arrivée est un processus de renouvellement. Voici une liste arrivées possibles et les notations associées : 4

-

arrivées à intervalles réguliers (chaîne de montage) : D (déterministe) ;

-

arrivées poissonneuses : M (Markov) ;

-

arrivées à intervalles suivant une loi d’Erlang : Ek égale à la loi gamma G(k,  ,)

-

arrivées à intervalles suivant une loi générale : GI.

b) Un organe de service : qui est caractérisé par : - Le temps de service : un client qui commence à être servi sera immobilisé pendant un temps aléatoire dont on supposera la loi connue ; -

Le nombre de guichets (points de service).

c) Une règle de service ou discipline : qui indique comment fonctionne le système : - Système avec attente ou sans attente (dans un système sans attente il n’y a pas de queue, un client non servi à son arrivée est perdu), - Système de capacité d’attente limitée (au delà d’une certaine longueur de queue les nouveaux clients sont perdus) - Ordre dans lequel les clients sont servis : « premier arrivé, premier servi », « dernier arrivé, premier servi » (cas usuel entre deux postes d’usinage les pièces issues du premier poste sont empilées les unes sur les autres puis saisies en commençant par celle qui est sur le dessus). - Plusieurs classes de clients chacune prioritaire par rapport aux classes suivantes. - Le client à son arrivée, si la queue est trop longue, quitte le système avec une certaine probabilité dépendant de la longueur de la queue. - Les durées de services (Yn)n  1 sont des variables positives indépendantes et de même loi. Voici une liste de services possibles et les notations associées :  services de durée constante : D (déterministe) ; 

services de durée suivant une loi exponentielle : M (Markov) ;



services de durée suivant une loi d’Erlang : Ek ;



services de durée suivant une loi générale : G.

Exemple de Discipline d’attente. Nous listons ci-dessous les différentes disciplines d’attente. FIFO

Premier arrivé, premier servi

FCFS

First Come First Served

LIFO

Dernier arrivé, premier servi

LCFS

Last Come First Served

RSS

Sélection au hasard d’un client en attente

Cette liste n’est pas complète. On peut définir d’autres types de priorité. Il faut alors déclarer précisément la manière dont les clients entrent en service. Lorsqu’il y a plusieurs serveurs en particulier, on peut par exemple -

affecter les clients aux serveurs par rotation, 5

-

créer une file d’attente unique, créer une file d’attente par serveur.

Exemples pratiques d’utilisation : E-commerce : connexion à un serveur, Online banking : capacité d’un call center, Agence bancaire : nombre de guichets.

2.1.2. Classification des files d’attente. Kendall a mis au point une nomenclature pour classer les files d’attente. Cette nomenclature est définie de la manière suivante. Une file d’attente spécifique est désignée par le symbole Arrivée / Service / Nombre de serveurs / Capacité maximale de la file / Nombre maximal de clients potentiels / Discipline de service Exemple : La file décrite par le symbole M/M/1/5/1/LIFO est une file dont les arrivées se font selon un processus de Poisson. Les services suivent la loi exponentielle et la file est constituée d’un unique serveur. On ne peut accepter plus de 5 clients en attente alors que le nombre de clients potentiels est illimité. La discipline de service est celle du dernier arrivé premier servi. Convention : La plupart du temps, seuls les trois premiers items sont spécifiés pour décrire une file d’attente. Par défaut, on utilise la convention suivante : –

Capacité maximale de la file : 

–

Nombre maximal de clients potentiels : 

–

Discipline de service : FIFO.

Ainsi la file d’attente M / M / 1/  /  / FIFO se note simplement : M / M / 1 Convention On note  le taux d’arrivée des clients. Cela signifie que l’espérance de la durée séparant deux arrivées successives est : E X 1   On note

E Y1  

1



le taux de service. Cela signifie que l’espérance de la durée de service est

1



L’intensité de trafic s’exprime de la manière suivante :  

 E Y1    EX 1 

Ce rapport de deux durées est une variable sans dimension. On l’exprime pourtant souvent dans une unité appelée Erlang. Nous notons Xt le nombre de clients en attente ou en service à l’ instant t. La théorie des files d’attente s’intéresse en particulier à l’étude du processus {Xt ; t  0} et à son comportement

asymptotique.

Si

ce

processus

admet

un

régime

stationnaire

indépendamment de la condition initiale, nous notons : 6

On dit alors que le processus {Xt ; t  0} est régulier. Les notations suivantes seront utiles par la suite. Nous notons L le nombre de clients dans q l’état stationnaire et L le nombre de clients en attente dans le régime stationnaire. Ainsi,

nous avons, pour la file M/M/1,

et

Nous notons encore W la durée de séjour d’un client en régime stationnaire et nous admettrons finalement la célèbre formule suivante connue sous la dénomination de formule de Little. ( )

( )

Cette formule exprime tout simplement le fait qu’en régime stationnaire, le nombre moyen de clients dans la file est égal au taux d’arrivée des clients multiplié par le temps moyen d’attente des clients. Cette formule rappelle un comportement poissonnien de la longueur de la file d’attente en régime stationnaire.

2.2.

Files d’attente formant un processus de naissance et de mort

Un processus de naissance et de mort est un processus de Markov homogène à valeurs dans IN tel que

ii 1  i ii 1  1 si j  i, i  1, i  1 ij  0 Où i  0,  i  0 et i  IN

On interprète un tel processus en admettant que Xt est la taille d’une population `a l’instant t. Si la population se compose de i individus au temps t, le taux instantané de

7

naissance d’un nouvel individu est  i tandis que le taux instantané de disparition d’un individu est i. Le générateur d’un processus de naissance et de mort est

 0    1  0   0

0  (1  1) 2 0

.  1 . .  ( 2   2 )  2 .  . .  .

Il existe plusieurs types de files d’attente formant un processus de naissance et de mort parmi lesquels on peut citer : M/M/1 et M/M/s Une file d’attente simple : M/M/1. Dans une file d’attente M/M/1, les clients se présentent à un serveur selon un processus de Poisson de paramètre  et sont servis les uns après les autres. Les durées de service sont indépendantes et de loi exponentielle de paramètre . Nous nous intéressons à l’évolution du nombre Xt de clients présents dans la file d’attente ou en service au temps t > 0. Le processus {Xt ; t  0} est un processus de naissance et de mort de taux :

Résolution des modèles de file d’attente "Résoudre" un modèle de file d’attentes consiste, en fonction des paramètres (taux d’arrivée  , taux de service  ), à écrire la distribution du nombre des clients dans le système et du temps d’attente (ou à défaut prévoir les moyennes de ces quantités) indépendants des lois des processus mis en œuvre :

 est le taux d’activité. La probabilité stationnaire que le  serveur soit inactif est p o  1   ;

 Le paramètre  

 Les nombres moyens et les temps d’attente sont reliés par la célèbre formule de Little :

E ( N X )  E (W X ) L’indice X signifie qu’on peut donner à ces grandeurs toute interprétation possible : le temps moyen d’attente et le nombre de clients en attente ; ou bien le temps de séjour et le nombre des clients séjournant ; Cette dernière formule est très importante. Une preuve intuitive peut en être donnée, basée sur un raisonnement graphique très simple. File d’attente de type M/M/s : Dans cette file d’attente, les arrivées se font selon un processus de Poisson de paramètre les temps de services sont des variables aléatoire de loi exponentielle de paramètre . A la 8

différence de la file M/M/1, le système n’est pas constitué d’un unique serveur mais d’un nombre arbitraire ( ) de serveurs. Dans ce cas, on a encore un processus de {

naissance et de mort avec, pour tout

On considère pour ce système une intensité de trafic normalisé par le nombre de serveurs . Le régime stationnaire du processus de naissance et de mort associé existe si et seulement si

Nous avons, pour tout

(

)

(

)

et

[∑

(

)

( ) ] ( )

{ La file d’attente M/M/I/k Dans cette file d’attente markovienne, il n’y a qu’un seul serveur, mais la capacité du système est limitée à k clients au total. Cela signifie que les clients qui arrivent lorsque le système est saturé sont définitivement rejetés. Avec les conventions de notation utilisées précédemment, nous avons affaire à un processus de naissance et de mort de taux définis pour tout

{

par

Puisque la capacité est limitée, nous obtenons d’office un régime stationnaire indépendant des conditions initiales quelle que soit la valeur de l’intensité de trafic Nous avons

et pour

.

3. ETUDE DE CAS

3.1.

Application 1 : File d’attente de type M/M/s

Un magasin opère actuellement avec une caisse où travaille un seul caissier. Une mesure statistique au bout d’un certain temps a révélé : -

qu’il arrive en moyenne 24 clients par heure ; et que 30 clients sont servis en moyenne en une heure.

Evaluons les performances de cette file d’attente. Cette file d’attente est de type M/M/1 où s=1, il existe un seul serveur (une seule caisse). Les paramètres du modèle sont : -

l’espérance de la durée séparant deux requêtes successives (le taux d’arrivée des clients) est : ,

-

. Donc le temps moyen séparant deux requêtes

successives est de 0,042 heures. -

L’espérance de la durée des services est de , -

Donc le temps

moyen des services est de 0,033 heures.

9

-

L’intensité du trafic

est :

Le caissier passe 80% de son temps

occupé. Les indicateurs de mesures de performances : -

Le nombre moyen de clients dans le système est donné par la formule :

-

Le nombre de clients dans la file est

-

Le temps d’attente moyen d’un client dans le système ( )

-

Le temps d’attente moyen d’un client dans la file (

(

⁄

=3,2 , -

(

)

)

) est donné par la formule de

⁄

Little,

Supposons à présent que le magasin gagne 75 FCFA par semaine en réduisant d’une minute le temps d’attente des clients et que les services d’un employé supplémentaire pendant une semaine coûte 150 FCFA. Voici les différents scénarios proposés au responsable du magasin : Scénario 1 : ajouter un emballeur au caissier, ce qui fera augmenter le taux de service à 40 clients par heure Scénario 2 : ajouter une deuxième caisse avec file séparée Scénario 3 : ajouter une deuxième caisse mais garder une seule file d’attente pour les deux caisses. Examinons l’incidence de ces différents scénarios sur le coût de l’attente. Scénario 1 : Nous sommes toujours dans le cas d’une file d ‘attente de type M/M/1, sauf que le taux de service est passé de 30 clients à 40 clients par heure. En implémentant les formules ci-dessus évoquées, on trouve : -

L’intensité du trafic

-

occupé. Le nombre moyen de clients dans le système est donné par la formule :

-

Le nombre de clients dans la file est

-

Le temps d’attente moyen d’un client dans le système ( )

-

Le temps d’attente moyen d’un client dans la file (

(

Little,

est :

Le caissier passe 60% de son temps

⁄

⁄ , -

(

)

)

) est donné par la formule de

⁄

10

Scénario 2 : Les files d’attentes étant séparées, nous nous trouvons toujours dans le cas d’une file d’attente de type M/M/1 où le taux de service est égal 12 clients par heure. Les performances du système sont : -

L’intensité du trafic

-

temps occupé. Le nombre moyen de clients dans le système est donné par la formule :

-

Le nombre de clients dans la file est

-

Le temps d’attente moyen d’un client dans le système ( ) (

-

est :

Chaque caissier passe 40% de son

⁄

⁄ , -

(

)

)

Le temps d’attente moyen d’un client dans la file (

) est donné par la formule de

⁄

Little,

Scénario 3 : Dans ce cas, on a à faire avec une file d’attente de type M/M/2. Les performances du système sont : -

L’intensité du trafic

est :

Chaque caissier passe 40% de son

temps occupé. [∑

)

( ) ] ( )

Le nombre de clients dans la file est

-

Après calcul, on trouve Donc il y a en moyenne 0,15 clients dans la file d’attente. Le temps d’attente moyen d’un client dans la file ( ) est donné par la formule de

(

)

où

(

-

⁄

Little,

, -

-

Le temps d’attente moyen d’un client dans le système( )

-

Le nombre moyen de clients dans le système est donné par la formule :

Les résultats sont récapitulés dans le tableau suivant : Tableau récapitulatif des indicateurs de mesure de performance

(clients) (

)

Actuellement

Scénario 1

Scénario 2

Scénario 3

4,0

1,5

0,67

0,95

3,2

0,9

0,27

0,15

(

)

10

3,75

3,33

2,38

(

)

8

2,25

1,33

0,38 11

(%)

80

60

40

40

-

468,75

500,25

571,5

Vente supplémentaire

(FCFA)

Source : Calcul des auteurs On réalise que les ventes supplémentaires augmentent avec la réduction du temps d’attente des clients, consécutive à une amélioration de la qualité du service fourni aux clients. On obtient les fonctions de coûts théoriques suivants : Figure : Fonctions de coût Coût total du système

Coût total Coût du service Coût minimum

Coût de l’attente Niveau de service désiré

3.2.

Application 2 : File d’attente de type

Niveaux de service

(

)

Pendant une période de deux semaines, une collecte a été effectuée sur l’un des postes de péage de notre pays doté de trois (03) guichets de service. Les tests d’ajustement statistiques ont montré que par seconde, les arrivées de voitures étaient poissonnières de paramètre et les durées de service Gamma de paramètres ( ) Le modèle dont il s’agit ici est de type . Ses indicateurs de mesure de performance sont : - L’espérance de la durée séparant deux arrivées successives de passagers : , soit environ 1 minute et 7 secondes ; L’espérance

-

L’intensité du trafic :

-

période des deux semaines l’intensité du trafic a été de 93,4%. Ceci veut dire que les guichets passent plus de 93% de leur temps occupés, ce qui assure le gestionnaire du péage d’une pleine utilisation des installations. Un régime stationnaire pourra cependant exister car l’intensité de trafic est inférieure à 100%. L’espérance du temps d’attente dans le système ⁄ (

de

, la durée de service : soit environ 3 minutes et 7 secondes.

-

)

, , -

⁄

(

Donc pendant toute la

) 12

-

Le temps moyen de séjour d’un client dans le système :

-

Le nombre moyen de clients en service : d’après la formule de Little,

-

Donc on a en permanence pratiquement 3 clients en service pendant toute la période de deux semaines. Le nombre moyen de clients dans la file d’attente ) ( )] ( ) [( ∑

-

(

)

⁄

Donc une file d’attente comporte en moyenne 13 passagers. Le nombre moyen de passagers dans le système

Donc il y a en moyenne 16 passagers dans le système dont environ 13 en attente et 3 au niveau des guichets. De tout ce qui précède, il apparait clairement que lorsqu’un nouveau client arrive dans le poste péage, il doit attendre pendant environ 16 minutes qu’un client en service complète son service pendant 3 minutes et que tous les service des clients présents dans la file se servent avant d’être servi à son tour. Pendant ce temps, il y a en moyenne 16 passagers dans le hall d’attente du poste dont un peu plus de 13 dans les files d’attente et entre 2 et 3 au niveau des guichets. Mais puisque les guichets passent plus de 93% de leur temps occupés, le gestionnaire pourrait diminuer le temps d’attente des passagers en augmentant le nombre de guichets de service.

CONCLUSION La théorie des files d’attente est une technique de la Recherche Opérationnelle permettant de modéliser un système admettant un phénomène d’attente, de calculer ses performances et de déterminer ses caractéristiques. Nous venons de votre à travers les divers exemples que nous avons développés qu’il faudra trouver un compromis entre le coût d’attente et le coût du service accordé aux clients pour optimiser la gestion des opérations. La théorie des files d’attente constitue de ce fait un puissant outil d’aide à la décision applicable dans nombre de domaines de la vie économique, même ceux les plus banals qu’on ne puisse pas penser.

BIBLIOGRAPHIE [1] H. Mehri et Djemel Taoufick « Etude et simulation du phénomène d’attente dans l’autoroute (Zone de péage) » Unité de Recherche en Gestion Industrielle et Aide à la Décision, 13

[2] 2008Donatien CHEDOM FOTSO et Laure Pauline FOTSO « Etude et simulation du phénomène d’attente dans un système bancaire » Université de Yaoundé 2006 [3] Olivier FRANCOIS « Cours de processus aléatoire », 2005

14