[PDF] Étude et simulation du phénomène dattente dans un système

View - Download Étude et simulation du phénomène dattente dans un système

Previous PDF

Next PDF

Étude et simulation du phénomène d"attente dans un système bancaire Approximations des mésures de performances des files d"attente M/G/c

Donatien CHEDOM FOTSO

*-Laure Pauline FOTSO**

Département d"informatique

Université de Yaoundé I

BP 812Yaoundé

Cameroun

chedonat@yahoo.com

Département d"informatique

Université de Yaoundé I

BP 812Yaoundé

Cameroun

l_fotso@yahoo.com

RÉSUMÉ.Des tests d"ajustements sur les intervalles de temps entre les arrivées et les durées de

service d"une étude de cas ont abouti au modèle M/¡(®;¯)/c. Il n"existe pas de formules analy-

tiques pour calculer les mesures de performance d"un tel modèle. Nous généralisons la formule de

Pollazeck-Khitchinne pour établir des formules approximatives de ces mesures et nous présentons

un simulateur pour calculer les mesures de performance des modèles de file A/B/c où A, B appar-

tiennent à l"ensemble des distributions {Déterministe, Exponentielle, Erlang, Gamma}. Nous vérifions

la théorie selon laquelle le type d"organisation de la file (une file unique pour tous les serveurs ou

multiple files avec une file devant chaque serveur) n"influence pas les mesures de performance du système d"attente bancaire. ABSTRACT.Adjustment tests show that arrival times and service times in a banking queueing system

of a case study led to the model M/¡(®;¯)/c. There are no analytical formulae to calculate perfor-

mance measures of such a model. In this article, we generalize Pollazeck-Khitchinne"s formula to establish approximate formulae of these measures and we present a simulator that calculates per- formance measures of A/B/c queueing system where A, B can be one of the following distributions: determinist, exponential, Erlang or Gamma. We verify the theory according to which the type of orga- nization of the queue (an unique queue for all the servers or multiple queues where each server has his/her own queue) does not influence the performance measures of the queueing system.

MOTS-CLÉS :Files d"attente, analyse statistique, simulation multi agent, distribution exponentielle,

distribution Gama KEYWORDS :Queues, statistical analysis, multi agent simulation, exponential distribution, Gamma distribution

1. Introduction

La Théorie des files d"attente est une technique de la Recherche opérationnelle qui permet de modéliser un système admettant un phénomène d"attente, de calculer ses per- formances et de déterminer ses caractéristiques pour aider les gestionnaires dans leurs

prises de décisions. Des résultats et formulations théoriques sont bien établis pour les mo-

dèles de files d"attente avec arrivées poissonnières et durées de services exponentielles

(M/M/c)[14][10]. Mais pas pour tous les systèmes tels que ceux avec arrivées poisson- nières et durées de services non exponentielles M/G/c dont l"étude analytique est très complexe. pour établir les mesures de performances du modèle M/G/c. Notre application numérique est basée sur une étude de cas d"un système bancaire d"une banque camerounaise Afri-

land First Bank dont les test statistiques sur les arrivées et les durées de service ont montré

que leurs distributions étaient respectivement poissonnières et Gamma; donc un modèle

M/¡(®;¯)/c.

Nous présentons un simulateur multi agent permettant d"implémenter tout système d"attente A/B/c où A, B appartiennent à l"ensemble des distributions {Déterministe, Ex- ponentielle, Erlang, Gamma}. Ce simulateur est utilisé pour vérifier l"hypothèse selon laquelle dans un système bancaire, le type d"organisation de la file d"attente (file unique pour tout les serveurs ou files multiples, une par serveur) n"influence pas les mesures de performances. Le reste de l"article est organisé comme suit. La section 2 présente brièvement les files

d"attente bancaires; une étude de cas est faite à la section 3 suivie par la généralisation de

la formule de Pollaczeck-khitchinne aux mesures de performances des modèles M/G/c à

la section 4; Le simulateur est présenté à la section 5. La section 6 calcul et interprète les

résultats et la section 7 conclut l"article.

2. Les files d"attente

Une file d"attente est constituée des clients qui demandent un service à un ou plusieurs serveurs et d"une salle d"attente. Le taux des clients qui arrivent et le taux de service par

unité de temps sont respectivement notés¸et¹. Un modèle de file d"attente est complè-

tement décrit selon la notation de Kendall-lee[10][14] parA/B/C/Disc/N/Poù :AetB représentent les lois des processus des arrivées et des durées de services. Par convention,

M signifie exponentielle, D déterministe,¡(®;¯)Gamma de paramètres®et¯, et G une

loi générale (quelconque).Cest le nombre de serveurs,Discla discipline de service,Nla capacité du système etPla taille de la population source. Lorsque les trois derniers para- mètres facultatifs sont omis ils sont considérésFCFS=1=1où FCFS veut dire premier arrivé premier servi (First Come, First served). Les mesures de performances d"un modèle de file d"attente sont : Le temps moyen de séjour d"un client dans le système (W), le temps d"attente moyen d"un client (Wq), le temps de service moyen (Ws), le nombre moyen de clients dans le système (L), le nombre moyen de clients dans la file d"attente (Lq), le nombre moyen de clients en service(Ls), le taux d"utilisation des serveurs ou intensité du trafic½=¸ c: ⁱ (où c est le nombre de serveurs), Les probabilités d"équilibre notéPn(probabilité d"avoir n client dans le système) et la probabilité d"attente¦w(probabilité qu"un client qui arrive attende avant d"être servi). Dans les banques, deux grandes écoles se partagent le type d"organisation des files d"attente[7],[11] : (ii) type 1, une unique file d"attente pour servir tous les guichets; ce qui permet d"empêcher les clients de former eux même les files d"attente. (ii) type 2 chaque guichet a sa propre file d"attente laissant le client joindre la plus courte file.

3. Etude de cas

Pendant une période de deux semaines, nous avons effectué une collecte des données à Afriland First Bank (une banque privée du Cameroun) sur les arrivées des clients et les durées des services. Le hall d"entrée de l"immeuble (abritant le siège social) où se trouvaient trois guichets (serveurs) étaient notre cadre d"étude. Les tests d"ajustement

statistiques ont montré que par seconde, les arrivées étaient poissonnières de paramètre

¸= 0;015et les durées de service Gamma de paramètres®= 2;42et¯= 77;17. Contrairement aux modèles multiserveurs avec des arrivées poissonnières et des du- rées de services exponentielles M/M/c, ceux avec des distributions quelconques sont plus complexes à analyser[8]. Aucun résultat théorique exact sur le calcul des mesures de per-

formance des modèles M/G/c n"a été formellement établi et prouvé[1][3]. Ivo Adan[1] n"a

proposé une approximation que de la durée moyenne d"attente pour ces modèles M/G/c. Les seules bonnes formulations théoriques rencontrées traitent des modèles n"admettant pas d"attente, à savoir le modèleM=G=c=GD=c=1avec perte de clients et le modèle

M=G=1avec un nombre infini de serveurs[5][8].

4. Approximation des mesures de performance des modèles

M/G/c D"après la formule de la valeur moyenne de Pollaczek-khintchinne[2], un nouveau client qui arrive doit attendre qu"un client en service complète son service et que tous les clients présents dans la file se servent avant d"être servi à son tour. Le temps d"attente moyen est alors définie par : W q=½E(R) +LqE(B)[1] où R est le temps de service résiduel d"un client en service, B le temps de service et la probabilité de trouver un client en service. En accord avec Ivo Adan [1], nous supposons que le temps nécessaire pour vider la file d"attente avec c serveurs est c fois plus petit qu"avec un serveur, on obtient alors : W q=1 c :(¦wE(R) +LqE(B))[2]

Où cette fois la probabilité qu"un client attende avant d"être servi est notée¦w(La valeur

de¦wdu modèle M/M/c peut être utilisée comme une approximation de¦wdu modèle M/G/c). R est le temps de service résiduel et B le temps moyen de service. D"après le théorème de LittleLq=¸ Wq. CommeE(B) =1 nous avons : W q¼¦wE(R) c(1¡½)avec½=¸ c ⁱ [3] La moyenne distribution du temps résiduel[10],[14]est :E(R) =1 2 (c2B+ 1)E(B) oùc2Best le coefficient de variation des durées de service (quotient de l"écart-type sur la moyenne).

Nous avons alors :

W q=1 c ¹ :¦w

2(1¡½)(c2B+ 1)[4]

D"où :

W s=E(B) =1 [5]

W=Ws+Wq=1

+1 c ¹ :¦w

2(1¡½)(c2B+ 1)[6]

L q=¸ Wq=¸:1 c ¹ :¦w

2(1¡½)(c2B+ 1)[7]

L s=¸ Ws=½=¸ [8]

L=Ls+Lq=¸

+¸:1 c ¹ :¦w

2(1¡½)(c2B+ 1)[9]

Ne pouvant établir des formules pour trouver des valeurs approximatives des proba- bilités d"équilibre du nombre de clients présents dans le système (Pn). Nous les avons simulées.

5. Simulation

La simulation multi agent, propose de créer un monde artificiel dans lequel inter- agissent des agents évoluant dans un environnement[4].

5.1. Fonctionnalités

Le simulateur programmé en Java, est multi agent. Il implémente les deux types d"or- ganisation des files d"attente bancaires pour les modèles A/B/c où A, B appartiennent à l"ensemble des distributions {Déterministe,Exponentielle,Erlang,Gamma}.

à simuler, la durée de la simulation, les distributions des durées de services et des arrivées

et le nombre de guichets. Le simulateur fournit en sortie les mesures de performance du modèle. La figure 1 donne une vue de ce simulateur.

Figure 1.Une vue du simulateur5.2. Description

Un agent est représenté par un thread indépendant, son savoir-faire par une méthode, son état par l"ensemble des valeurs de ses propriétés et son comportement par la méthode Run du thread. Les agents sont dotés de deux facultés : Percevoir et Agir. Un agent doit percevoir d"abord son environnement avant d"y agir. Le système a trois types d"agents : les clients, les serveurs et le super agent qui contrôle et cordonne le déroulement de la simulation. Le choix des unités de temps et la détermination des valeurs qui en dépendent sont im-

portants. L"unité de temps est régie par les taux de service et taux des arrivées des clients.

Ces taux sont exprimés par rapport à la même unité de temps. Si par exemple le taux des arrivées s"exprime en nombre de clients qui arrivent par heure, alors le taux de service devra être exprimé en nombre de clients servis par heure. La durée de la simulation, doit également être exprimée dans la même unité de temps. Dans le type 2, quand un client choisi une file, il y reste jusqu"à obtenir son service. Le simulateur utilise la méthode de la transformation inverse[9] pour générer les variables aléatoires. Pour valider le simulateur nous avons comparé ses sorties aux résultats théoriques connus.

5.3. Calcul des mésures de performances

Calcul de L, L

q, et Ls Nous utilisons deux tableaux d"entiers Lq[ ] et Ls[ ]. Un pas de simulation correspond à 100 ms (1/10 secondes). Auiemepas on affecte à Lq[i] ( repectivement Ls[i]) le nombre de clients dans la file d"attente Qsize(respectivement nombre de clients en service Ssize).

A la fin de la simulation nous avons :

L q=T pP i=1Lq[i] T p;Ls=T pP i=1Ls[i] T p;L=Lq+Ls[10] oùTpest le nombre total de pas de simulation. Si T est la durée de la simulation, T

Calcul de W, W

qet Ws Nous utilisons également deux tableaux d"entiers Wq[ ] et Ws[ ] correspondant res- pectivement aux temps d"attente et de service des clients dans le système. Chaque agents Client possède deux variables Date (sa date de création Dc et sa date de début de service Dd) et une variable durée de service Ds. A la création du client, sa

date de création est mise à jour à la date courante et l"ordinateur génère le temps avant

la création du prochain client suivant la distribution des intervalles de temps entre les

arrivées. Le client créé va être servi si un serveur est libre, sinon il se voit attribuer une

positionPos=Qsize+ 1dans la file d"attente (la plus courte dans le cas à plusieurs

files) qui est décrémentée au fur et à mesure qu"un serveur se libère (celui de sa file, dans

le cas à plusieurs files).

Quand le i

emeclient occupe la position 1 et qu"un serveur se libère (son serveur dans

le cas à plusieurs file), il rejoint le service, sa date de début de service Dd est mise à jour

à la date courante et l"ordinateur génère la durée de son service Ds suivant la distribution

des durées de service. Puis on met à jour :

Wq[i] =Dd¡Dc;etWs[i] =Ds[11]

A la fin de la simulation nous avons :

W q=N qP i=1Wq[i] N q;Ws=N sP i=1Ws[i] N s;W=Wq+Ws;[12] oùNsest le nombre total de clients servis pendant la simulation etNqle nombre total de clients ayant attendus (la somme du nombre de clients déjà servis et du nombre de clients en service).

Calcul des probabilités d"équilibres

Nous utilisons un tableau d"entiers P[ ] dont les 200 premières composantes sont ini- tialisées à 0 (P[i] = 0;pour1< i <= 200). A chaque pas de simulation, on incrémente P[j] de 1 sij=Qsize+Ssize. A la fin de la simulation nous avons : P n=P[n] T p[13] T preprésentant le nombre de pas de simulation.

6. Résultats et interprétation

Pour le type 1, nous avons utilisé les approximations établies à la section 3 et simulé

les probabilités d"équilibre. Pour le type 2, il n"existe pas de modèles théoriques prenant

en charge tous les aspects de cette approche, les résultats ont été simulés sous les mêmes

conditions initiales.

Données initiales

L"analyse statistique de l"ensemble des données collectées de notre étude de cas a

abouti à un modèle M/¡(®;¯)/3 et nous a permis de conclure que les arrivées des clients

sont poissonnières de taux¸= 0;015par seconde et que les durées de service sont Gamma de moyenne1=¹= 187;38secondes et de variance¾2= 14461;96. D"où

®= 2;42et¯= 77;17.

Résultats

Le tableau 1 donne les valeurs des indicateurs de performance obtenues dans les deux cas.

Mesures de performance

file unique files multiples 93,7%
93,5%
0 0,015 0,015 w 0,87 0,81 W

796,107

778
W q

608,727

591,42

W s

187,38

186,61

Lquotesdbs_dbs29.pdfusesText_35

[PDF] chaine de markov pour les nuls

[PDF] chaine de markov résumé

[PDF] chaine de markov matrice de transition

[PDF] chaine d'acquisition de données

[PDF] chaine de mesure audioprothèse

[PDF] acquisition de données du capteur ? l ordinateur

[PDF] chaine de mesure pdf

[PDF] chaine d'acquisition capteur

[PDF] les capteurs exercices corrigés

[PDF] chaine de markov apériodique

[PDF] chaine de markov apériodique exemple

[PDF] chaine de markov reversible

[PDF] chaine de markov récurrente

[PDF] chaine de markov exemple

[PDF] chaine de markov irreductible exemple