Gestion des operations file d attente

Gestion des operations file d attente

OBJECTIFS D’APPRENTISSAGE Apres avoir termine l’etude de ce chapitre, vous pourrez : 1. Expliquer pourquoi des files d’attente se forment dans des systemes non congestionnes. 2. Identifier l’objectif de l’analyse des files d’attente. 3. Enoncer les mesures de performance utilisees dans le cadre des files d’attente. 4. Formuler les hypotheses des principaux modeles de base. 5. Resoudre des problemes classiques. Chapitre 19 LES FILES D’ATTENTE Plan du chapitre Lecture : Attendre… un passe-temps populaire : Mme Bonnes Manieres 692 19. 1 Introduction 693 19. Pourquoi y a-t-il de l’attente ? 693 19. 3 L’objectif de l’analyse des files d’attente 694 19. 4 Les caracteristiques du systeme de files d’attente 695 19. 4. 1 La population 695 19. 4. 2 Le nombre de serveurs 696 19. 4. 3 Les tendances quant a l’arrivee et au service 696 19. 4. 4 La discipline de la file d’attente 699 19. 5 Les mesures de performance 699 19. 6 Les principaux modeles de files d’attente 699 19. 6. 1 Modeles avec population infinie 699 19. 6. 1. 1 Les relations de base 700 19. 6. 1. 2 Modele 1 : serveur unique, temps de service exponentiel 702 91 19. 6. 1. 3 Modele 2 :

Désolé, mais les essais complets ne sont disponibles que pour les utilisateurs enregistrés

Choisissez un plan d'adhésion
serveur unique, temps de service constant 703 19. 6. 1. 4 Modele 3 : serveurs multiples, temps de service exponentiel 703 19. 6. 1. 5 Optimisation des files d’attente 707 19. 6. 1. 6 Capacite maximale de la file d’attente 709 19. 6. 1. 7 Modele 4 : serveurs multiples et regles de priorite 710 19. 6. 2 Modele avec population finie 714 19. 7 Autres approches d’analyse 720 19. 8 Conclusion 721 Terminologie 721 Problemes resolus 721 Questions de revision et de discussion 723 Problemes 723 Bibliographie 727 692

PARTIE V LA GESTION ET L’EXPLOITATION DU SYSTEME LECTURE ATTENDRE… UN PASSE-TEMPS POPULAIRE : Mme BONNES MANIERES (Judith Martin, adaptation de Hocine Bourenane) I l y a plusieurs choses dans la vie pour lesquelles cela vaut la peine d’attendre, mais pas tres longtemps. Mme Bonnes Manieres limiterait, par exemple, le temps passe par les vendeurs a discuter avant de prendre une commande ou le temps pris par un mari qui a quitte sa femme pour se rendre compte de sa terrible erreur. Quoi qu’il en soit, l’attente et le travail sont devenus des passe-temps populaires.

Un specialiste de l’analyse de l’attente a determine qu’une personne adulte passait au minimum le dixieme de son temps a attendre. On attend les autobus, les ascenseurs, dans les banques, les magasins, les cinemas, les stations d’essence, les tribunaux, pour l’obtention du permis de conduire, chez le dentiste, etc. On pourrait passer toute sa vie a subir ce genre d’attente classique. Cependant, il y a d’autres types d’attente : l’attente intermediaire, comme attendre que la pluie cesse ou, encore, l’attente plus febrile, comme attendre que votre bateau rentre a bon port.

Il fut un temps ou toute l’Amerique attendait d’etre decouverte dans un supermarche par un cineaste et, aujourd’hui, chacun attend qu’une camera de television arrive pour lui demander de donner son avis au monde entier. C’est l’attente classique, l’attente a court terme, qui interesse Mme Bonnes Manieres. Si vous voulez en savoir plus sur les autres types d’attente, vous n’avez qu’a… attendre ! Il est tout a fait correct, malgre le fait que tres peu de gens le comprennent, de refuser d’attendre au telephone. Quand on demande a Mme Bonnes Manieres de patienter quelques minutes au telephone, elle replique souvent par la negative.

Malheureusement, la personne au bout du fil l’a deja mise automatiquement en attente, car elle n’a pas attendu la reponse de Mme Bonnes Manieres. On devrait toujours refuser d’attendre pour un service inefficace et qui prend un temps infini. Au restaurant, on devrait etre capable de vous donner le temps d’attente et de ne pas vous laisser attendre, excepte pour servir les clients arrives avant vous. En effet, c’est inconvenant de refuser d’attendre en annoncant que nos besoins ont une primaute sur ceux des autres.

Mme Bonnes Manieres ne peut concevoir aucune situation d’attente ordinaire ou une personne pourrait legitimement passer avant les autres. « Laissez-moi passer, s’il vous plait, je suis enceinte, j’ai des douleurs, je pense que je vais accoucher ! » Peutetre, mais que faites-vous donc dans un magasin au moment des soldes ? La seule maniere polie d’attendre est d’emporter avec soi du travail ou de quoi se divertir. Toute personne inoccupee dans une file d’attente est, par definition, un maniaque qui peut se dechainer a tout moment.

Un bon roman de Jane Austen a pu preserver l’esprit naturellement tranquille de Mme Bonnes Manieres. Selon elle, meme le fait d’engager la discussion pour passer le temps peut etre dangereux. C’est tout simplement une honte de voir deux personnes qui attendent en train de discuter tranquillement. Par definition, ce sont des comploteurs potentiels. Pour conclure et en attendant, relaxez-vous en ecoutant de la musique ! Pourquoi pas Georges Moustaki ? « Passe, passe le temps, il n’y en a plus pour tres longtemps. Pendant que j’attendais… » ©1980 Judith Martin. Reproduit avec autorisation. 5 3 1 0 Attendre a des feux Ouvrir du courrier inutile Chercher des objets perdus Attendre qu’une ligne se libere Faire le menage a la maison Attendre en file 2 Annees 4 6 CHAPITRE 19 LES FILES D’ATTENTE 693 19. 1 INTRODUCTION L’article portant sur Mme Bonnes Manieres parodie une des realites de la vie : l’attente en file. Pour ceux qui attendent en file, la solution est tres simple : ajouter des ressources ou bien agir, faire n’importe quoi pour accelerer le service. C’est l’evidence meme. Cependant, ce n’est pas aussi simple, car il faut tenir compte de certaines subtilites.

Premierement, sur une longue periode, la majorite des processus de service ont une capacite de traitement superieure a celle qui est necessaire. Par consequent, le probleme des files d’attente ne survient que pendant de courtes periodes. Deuxiemement, il ne faut pas perdre de vue le fait qu’a certains moments, le systeme est vide : les employes sont inoccupes et attendent que les clients se presentent. En augmentant la capacite, on ne fait qu’augmenter le temps d’inoccupation des employes. Donc, si on veut concevoir un systeme de service, il faut omparer le cout associe au niveau de service (capacite) mis en place et le cout associe a l’attente des clients. La planification et l’analyse de la capacite de service sont des themes traites par la theorie des files d’attente. Cette theorie est une approche mathematique permettant d’analyser les files d’attente. Elle est basee sur l’etude des equipements telephoniques automatiques realisee au debut du XXe siecle par l’ingenieur danois en telecommunication, A. K. Erlang. L’application de cette theorie n’a ete generalisee a divers types de problemes qu’apres la Seconde Guerre mondiale.

La theorie mathematique des files d’attente etant assez complexe, on ne s’attardera dans ce chapitre qu’aux concepts et aux hypotheses relatifs a la resolution des problemes d’attente. On utilisera les formules et les tables disponibles. Les files d’attentes se forment lorsque les clients arrivent de facon aleatoire pour se faire servir. Les exemples les plus courants de la vie de tous les jours sont les caisses des supermarches, les etablissements de restauration rapide, les billetteries des aeroports, les cinemas, les bureaux de poste, les banques. Toutefois, lorsqu’on parle d’attente, on pense souvent a des personnes.

Or, les « clients » en attente sont aussi des commandes en attente de traitement, des camions en attente de chargement ou de dechargement, des machines en attente de reparation, des programmes d’ordinateur qui attendent d’etre executes, des avions qui attendent l’autorisation de decoller, des bateaux qui attendent les remorqueurs pour accoster, les voitures aux panneaux d’arret, les patients dans les salles d’urgence, etc. Generalement, les clients voient dans l’attente une activite sans valeur ajoutee et, s’ils attendent trop longtemps, ils associent cette perte de temps a une mauvaise qualite de service.

De la meme facon, au sein de l’entreprise, des employes inoccupes ou des equipements inutilises representent des activites sans valeur ajoutee. Pour eviter ces situations, la majorite des entreprises ont mis en place des processus d’amelioration continue dont le but ultime est l’elimination de toute forme de gaspillage, notamment l’attente. Tous ces exemples revelent l’importance de l’analyse des files d’attente. Commencons par une question fondamentale : pourquoi y a-t-il de l’attente ? theorie des files d’attente Approche mathematique servant a l’analyse des files d’attente. 9. 2 POURQUOI Y A-T-IL DE L’ATTENTE ? Il est surprenant d’apprendre que des files d’attente se forment meme dans les systemes non congestionnes. Par exemple, un etablissement de restauration rapide qui peut traiter en moyenne 200 commandes a l’heure voit malgre tout se former des files d’attente avec un nombre moyen de 150 commandes a l’heure. L’expression cle est « en moyenne ». Le probleme vient du fait que les arrivees des clients ont lieu a intervalles aleatoires plutot qu’a intervalles fixes. De plus, certaines commandes requierent un temps de traitement plus long.

En d’autres termes, les processus d’arrivee et de service ont un degre de variabilite eleve. Par consequent, le systeme est soit temporairement congestionne, ce qui cree des files d’attente, soit vide, parce qu’aucun client ne se presente. Donc, si le systeme n’est pas congestionne d’un point de vue macro, il l’est d’un point de vue micro. Par ailleurs, en cas de variabilite minimale ou inexistante (arrivee selon les rendez-vous et temps de service constant), aucune file d’attente ne se forme. 694 PARTIE V LA GESTION ET L’EXPLOITATION DU SYSTEME 19. L’OBJECTIF DE L’ANALYSE DES FILES D’ATTENTE L’objectif de l’analyse des files d’attente est de minimiser le cout total, qui equivaut a la somme de deux couts : le cout associe a la capacite de service mise en place (cout de service) et le cout associe a l’attente des clients (cout d’attente). Le cout de service est le cout resultant du maintien d’un certain niveau de service, par exemple le cout associe au nombre de caisses dans un supermarche, au nombre de reparateurs dans un centre de maintenance, au nombre de guichets dans une banque, au nombre de voies d’une autoroute, etc.

En cas de ressources inoccupees, la capacite est une valeur perdue, car elle est non stockable. Les couts d’attente sont constitues des salaires payes aux employes qui attendent pour effectuer leur travail (mecanicien qui attend un outil, chauffeur qui attend le dechargement du camion, etc. ), du cout de l’espace disponible pour l’attente (grandeur de la salle d’attente dans une clinique, longueur d’un portique de lave-auto, kerosene consomme par les avions qui attendent pour atterrir) et, bien sur, du cout associe a la perte de clients impatients qui vont chez les concurrents.

En pratique, lorsque le client est externe a l’entreprise, le cout d’attente est difficile a evaluer, car il s’agit d’un impact plutot que d’un cout pouvant etre comptabilise. Cependant, on peut considerer les temps d’attente comme un critere de mesure du niveau de service. Le gestionnaire decide du temps d’attente acceptable, « tolerable », et il met en place la capacite susceptible de fournir ce niveau de service. Lorsque le client est interne a l’entreprise — les clients sont les machines et les commis, l’equipe d’entretien —, on peut etablir directement certains couts se rapportant au temps d’attente des clients (machines).

Par ailleurs, il ne faut pas conclure trop rapidement que pour l’entreprise, le cout du temps d’attente d’un employe qui attend est egal a son salaire durant le temps d’attente ; cela impliquerait que la baisse nette des gains de l’entreprise, du fait de l’inactivite d’un employe, est egale au salaire de ce dernier, ce qui, a priori, n’est pas evident. L’employe, qu’il travaille ou qu’il attende, recoit le meme salaire. Par contre, sa contribution aux gains de l’entreprise est reellement perdue, car la productivite baisse.

Quand un operateur de machine est inactif parce qu’il attend, sa force productive (qui peut comprendre, outre son salaire, une proportion des couts fixes de l’entreprise) est perdue. En d’autres termes, il faut tenir compte non pas de la ressource physique en attente, mais plutot de la valeur (cout) de toutes les ressources economiques inactives, et evaluer ensuite la perte de profit a partir de la perte de productivite. L’objectif de l’analyse des files d’attente est de trouver un compromis entre le cout associe a la capacite de service et le cout d’attente des clients. La figure 19. illustre bien ce concept. Notez que lorsque la capacite de service augmente, le cout de service augmente. Par souci de simplicite, nous avons illustre un cout de service lineaire. Cela n’affecte en rien la demonstration. Lorsque la capacite de service augmente, le nombre de clients en attente et le temps d’attente tendent a diminuer, donc les couts d’attente diminuent. Le cout total (la somme des couts de service et d’attente) est represente sur le graphique par une courbe en forme de U. Graphiquement, il suffit de determiner le niveau de service se traduisant par le cout total minimum. Contrairement au modele de la quantite economique utilise dans la gestion des stocks, le minimum n’est pas necessairement atteint au point d’intersection de la droite et de la courbe. ) Dans le cas d’une clientele externe a l’entreprise, les files d’attente donnent une image negative de la qualite du service offert. Dans cette situation, les entreprises auront tendance a augmenter la rapidite du service plutot que d’augmenter le nombre d’employes. Le fait d’abaisser le cout d’attente aura pour effet de deplacer vers le bas la courbe en U, qui represente le cout total.

CHAPITRE 19 LES FILES D’ATTENTE 695 Figure 19. 1 L’objectif de l’analyse des files d’attente est de minimiser la somme de deux couts : le cout d’attente des clients et le cout de service. Cout Cout total Cout de service Cout d’attente des clients 0 Niveau de service optimal 19. 4 LES CARACTERISTIQUES DU SYSTEME DE FILES D’ATTENTE Dans le cadre de la theorie des files d’attente, on a concu plusieurs modeles d’analyse. Le succes de l’analyse des files d’attente repose surtout sur le choix du modele approprie. Plusieurs caracteristiques sont a prendre en consideration : 1. La population. . Le nombre de serveurs. 3. Les tendances quant a l’arrivee et au service. 4. L’ordre de traitement des clients. La figure 19. 2 illustre un systeme de file d’attente. Systeme Ordre de traitement Figure 19. 2 Systeme de file d’attente simple Population Arrivees File d’attente Service Depart 19. 4. 1 La population Dans la theorie des files d’attente, on appelle « population » la source de clients potentiels. Il y a deux situations possibles. Dans le premier cas, la population est infinie, c’est-a-dire que le nombre potentiel de clients est infiniment grand en tout temps.

C’est le cas des clients des supermarches, des banques, des restaurants, des cinemas, des centres d’appels, etc. De plus, les clients proviennent de toutes les regions possibles. Dans la deuxieme situation, la population est finie, ce qui signifie que le nombre de clients potentiels est limite. Un bon exemple est le nombre de machines, d’avions, etc. , en reparation dans le centre de maintenance d’une entreprise. L’entreprise en question possede un nombre fini de machines, d’avions, etc. Voici d’autres situations semblables : une infirmiere opulation infinie Le nombre de clients qui arrivent est illimite. population finie Le nombre de clients qui arrivent est limite. 696 PARTIE V LA GESTION ET L’EXPLOITATION DU SYSTEME ayant la charge de 10 patients, un employe de banque charge de remplir et de vider 4 guichets automatiques, une secretaire qui s’occupe de 5 representants, un controleur de la navigation aerienne qui dirige l’atterrissage ou le decollage de 5 avions, etc. 19. 4. 2 Le nombre de serveurs serveur Entite qui fournit le service. La capacite de service depend de la capacite de chaque serveur et du nombre de erveurs disponibles. Le terme « serveur » represente ici la ressource et, en general, on suppose qu’un serveur ne traite qu’un client a la fois. Les systemes de files d’attente fonctionnent avec serveur unique ou serveurs multiples (plusieurs serveurs travaillant en equipe constituent un serveur unique, par exemple une equipe chirurgicale). Les exemples de systemes de files d’attente avec serveur unique sont nombreux : les petits magasins avec une seule caisse, tels que les depanneurs, certains cinemas, certains lave-autos et etablissements de restauration rapide avec guichet unique.

Les systemes a multiples serveurs sont les banques, les billetteries d’aeroports, les garages et les stations-service. La figure 19. 3 illustre les systemes de files d’attente les plus courants. Pour des raisons pratiques, ceux qui sont etudies dans le cadre de ce chapitre comprennent une seule etape. Serveur unique, etape unique Figure 19. 3 Quatre types de systemes de files d’attente Serveur unique, etapes multiples Serveurs multiples, etape unique Serveurs multiples, etapes multiples 19. 4. 3 Les tendances quant a l’arrivee et au service

Les files d’attente resultent de la variabilite des tendances d’arrivee et de service. Elles se forment parce que le degre eleve de variation dans les intervalles entre les arrivees et dans les temps de service cause des congestions temporaires. Dans plusieurs cas, on peut representer ces variations par des distributions theoriques de probabilites. Dans les principaux modeles utilises, on suppose que le nombre d’arrivees dans un intervalle donne suit la loi de Poisson, alors que le temps de service suit une loi exponentielle. La figure 19. 4 illustre ces deux distributions.

En general, la distribution de Poisson donne un assez bon apercu du nombre de clients qui arrivent par unite de temps (par exemple le nombre de clients a l’heure). La figure 19. 5 A illustre les arrivees distribuees selon la loi de Poisson (par exemple des accidents) pendant une periode de trois jours. Durant certaines heures, on note de trois a quatre accidents ; a d’autres, un ou deux, et pour certaines, aucun. CHAPITRE 19 LES FILES D’ATTENTE 0,20 0,18 0,16 0,14 Frequence 0,12 0,10 0,08 0,06 0,04 0,02 0,00 0 1 2 3 4 5 6 7 8 9 10 11 12 Nombre de clients par unite de temps 97 Figure 19. 4 Distributions de Poisson et exponentielle Loi de Poisson Frequence (%) Loi (distribution) exponentielle (temps) 0 Temps La distribution exponentielle, quant a elle, donne une assez bonne approximation des temps de service (par exemple avant l’arrivee des premiers secours aupres des victimes d’accidents). La figure 19. 5 B illustre le temps de service pour des clients qui arrivent selon le processus illustre a la figure 19. 5 A. Remarquez que la plupart des temps de service sont tres courts — certains sont proches de zero — et quelques-uns, assez longs.

C’est la caracteristique typique de la distribution exponentielle. Par exemple, les operations traitees au guichet d’une banque prennent approximativement le meme temps (assez court), alors qu’un nombre limite de clients requierent un temps de traitement assez long. Les files d’attente se forment plus souvent lorsque les arrivees se font en groupe ou que les temps de service sont particulierement longs ; elles se creent presque a coup sur si ces deux facteurs se manifestent. Par exemple, notez, a la figure 19. 5 B, le temps de service particulierement long pour le client no 7 au jour 1.

A la figure 19. 5 A, le client no 7 arrive a 10 heures et les 2 clients suivants arrivent juste apres, ce qui cree alors une file d’attente. Une situation similaire s’est presentee le jour 3 avec les 3 derniers clients : le temps de service assez long pour le client no 13 (figure 19. 5 B) combine au temps relativement court entre les deux arrivees suivantes (figure 19. 5 A, jour 3) va certainement engendrer (ou augmenter) une file d’attente. Remarquez qu’il existe une relation entre la distribution de Poisson et la distribution exponentielle.

En d’autres termes, si le temps de service suit la loi exponentielle, le taux de service (nombre de clients servis par unite de temps) suit la loi de Poisson. De la meme maniere, si le taux d’arrivee suit la loi de Poisson, le temps interarrivees (temps entre deux arrivees successives) suit une loi exponentielle. Par exemple, si un centre de service a la capacite de traiter en moyenne 12 clients a l’heure (taux de service), le temps moyen de service est de cinq minutes. Si le taux moyen d’arrivee est de 10 clients a l’heure, le temps moyen entre 2 arrivees successives est de 6 minutes.

Ainsi, les modeles de files d’attente decrits dans ce chapitre ont generalement comme processus d’arrivee un processus de Poisson ou, de facon equivalente, des temps interarrivees exponentiels et des temps de service distribues selon une loi exponentielle. En pratique, avant d’utiliser un modele, il faut verifier ces caracteristiques. Dans certains cas, on peut le faire en colligeant des donnees et en les representant graphiquement. On ajuste ensuite la distribution observee a la distribution theorique. temps interarrivees Temps entre deux arrivees successives. 98 PARTIE V LA GESTION ET L’EXPLOITATION DU SYSTEME Nombre d’arrivees par jour 18 8 9 10 11 12 Heures 1 2 3 4 Figure 19. 5 Arrivees distribuees selon la loi de Poisson et temps de service distribues de facon exponentielle A. Processus d’arrivee = Arrivee 7 Jour 1 Jour 2 8 9 10 11 12 Heures 1 2 3 4 14 Jour 3 8 9 10 11 12 Heures 1 2 3 4 15 B. Temps de service Jour 1 client 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 0 Temps Jour 2 client 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 Temps Jour 3 client 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 Temps

Il est toutefois preferable pour ce type de probleme d’utiliser le test du chi-deux (? 2) : ce sujet ne fait pas l’objet d’etude de ce chapitre et il est developpe dans la majorite des ouvrages de statistique. Aujourd’hui, il existe des logiciels tres puissants qui permettent d’ajuster tres rapidement une serie d’observations a une distribution theorique de probabilite. L’un des plus complets est ExpertFit, concu par Averill Law et associes. Par ailleurs, les recherches ont demontre que si ces hypotheses sont generalement appropriees pour le processus d’arrivee, elles le sont moins pour le processus de service.

Dans ce cas, les solutions a considerer consistent a : 1) mettre au point un modele plus approprie ; 2) utiliser un meilleur modele (generalement plus complexe) ; 3) avoir recours a la simulation numerique. Ces solutions requierent generalement plus d’efforts, de temps et d’argent que les modeles de files d’attente presentes dans ce chapitre. CHAPITRE 19 LES FILES D’ATTENTE 699 19. 4. 4 La discipline de la file d’attente La discipline de la file d’attente concerne l’ordre de traitement des clients.

Dans tous les modeles decrits dans les pages suivantes, on suppose que la regle de priorite est : premier entre, premier servi (PEPS). C’est la regle la plus communement utilisee dans les entreprises de services ; elle procure aux clients un sentiment de justice, bien qu’elle penalise les clients dont le temps de service est court. Elle est appliquee dans les banques, les magasins, les cinemas, les restaurants, les intersections avec arret obligatoire, les controles douaniers, etc. Certains systemes ne s’en servent pas : les salles d’urgence des hopitaux, en general, utilisent trois niveaux de riorite (les cas graves etant traites en priorite) ; les usines traitent les commandes urgentes et les ordinateurs centraux traitent les taches par ordre d’importance. Certains clients devront donc attendre plus longtemps, meme s’ils sont arrives plus tot. Prenons un exemple. Vous venez d’avoir un bebe et vous etes une personne plutot anxieuse. Si vous allez a l’urgence de l’hopital Sainte-Justine de Montreal a la moindre petite fievre de votre bebe, armez-vous de patience et priez pour qu’il n’y ait pas trop de cas graves ce jour-la.

Les autres regles de priorite susceptibles d’etre appliquees sont les temps d’operation les plus courts, les commandes ou les clients les plus importants, les urgences, les reservations en priorite, les delais de livraison les plus courts, etc. discipline de la file d’attente Ordre dans lequel les clients sont traites. 19. 5 LES MESURES DE PERFORMANCE Les gestionnaires ont a leur disposition cinq outils de mesure ou indices pour evaluer la performance d’un systeme de production de biens ou de services existant ou celle d’un systeme qu’ils veulent concevoir.

Ces mesures sont : 1. Le nombre moyen de clients qui attendent en file ou dans le systeme1. 2. Le temps moyen d’attente en file et dans le systeme. 3. Le taux d’utilisation du systeme, c’est-a-dire le pourcentage de la capacite utilisee. 4. Le cout associe au niveau de service (capacite) mis en place. 5. La probabilite qu’un client potentiel attende pour etre servi. Parmi ces cinq outils de mesure, le taux d’utilisation du systeme necessite quelques eclaircissements. Il reflete l’etendue de l’occupation des serveurs plutot que leur inactivite.

Il est logique de penser qu’une bonne gestion des ressources implique un taux d’utilisation de 100 %. Cependant, comme le montre la figure 19. 6, le fait d’augmenter le taux d’utilisation revient a augmenter a la fois le nombre de clients qui attendent et le temps moyen d’attente. En fait, ces deux mesures augmentent indefiniment lorsque le taux d’utilisation approche de 100 %. Si tous les serveurs sont occupes, il est certain que les clients potentiels qui arrivent vont attendre. Cela implique que dans des conditions normales d’operation, un taux d’utilisation de 100 % est irrealiste.

Le gestionnaire devrait plutot essayer d’equilibrer le systeme de telle sorte que la somme des couts de service et d’attente soit minimale, tel qu’illustre a la figure 19. 11. 19. 6 LES PRINCIPAUX MODELES DE FILES D’ATTENTE 19. 6. 1 Modeles avec population infinie Plusieurs modeles de files d’attente sont a la disposition des gestionnaires pour leur permettre de concevoir des systemes de production de biens ou de services ou de representer un systeme reel afin d’en analyser la performance. Dans ce chapitre, nous 1. Voir la figure 19. 2. 700

PARTIE V LA GESTION ET L’EXPLOITATION DU SYSTEME Nombre moyen de clients qui attendent 0 Taux d’utilisation du systeme Figure 19. 6 Le nombre moyen de clients qui attendent en file et le temps moyen d’attente des clients en file augmentent de facon exponentielle a mesure que le taux d’utilisation augmente. 100 % presentons les quatre modeles de base les plus utilises. Le but n’est pas d’etudier de facon exhaustive les modeles, mais plutot d’analyser un certain nombre d’entre eux. Tous ont pour hypothese que le taux d’arrivee est distribue selon la loi de Poisson.

On suppose aussi que le systeme etudie est en regime permanent (stationnaire), c’esta-dire que les taux d’arrivee et de service sont stables. Les quatre modeles presentes sont : 1. Serveur unique, temps de service exponentiel. 2. Serveur unique, temps de service constant. 3. Serveurs multiples, temps de service exponentiel. 4. Serveurs multiples, regles de priorite multiples, temps de service exponentiel. Afin de faciliter l’utilisation des modeles, le tableau 19. 1 presente les symboles et la terminologie utilises pour les modeles avec population infinie. TABLEAU 19. Symboles (modeles avec population infinie) Symbole ? µ ? nl ns 1 µ tl ts P0 Pn M Signification Taux d’arrivee des clients Taux de service Taux d’utilisation du systeme Nombre moyen de clients qui attendent d’etre servis Nombre moyen de clients dans le systeme (clients qui attendent et clients qui sont en train d’etre servis) Temps de service Temps moyen d’attente en file Temps moyen d’attente dans le systeme (temps d’attente en file, plus le temps de service) Probabilite qu’il y ait zero unite (client) dans le systeme Probabilite qu’il y ait n unites (clients) dans le systeme Nombre de serveurs 9. 6. 1. 1 Les relations de base Dans les modeles de files d’attente avec population infinie, il existe certaines relations de base (entre certains parametres et les mesures de performance) qui permettent de determiner les mesures de performance desirees grace a quelques valeurs cles. Les principales relations sont presentees ci-dessous : Remarque : les taux d’arrivee (? ) et de service (µ) doivent etre exprimes dans la meme unite de mesure (clients a l’heure, clients par minute, etc. ). CHAPITRE 19 LES FILES D’ATTENTE 701

Le taux d’utilisation du systeme : il represente le rapport entre la demande (mesuree grace au taux d’arrivee, ? ) et la capacite de service (produit du nombre de serveurs M par le taux de service, µ). ?= ? Mµ (19-1) Le nombre moyen de clients en train d’etre servis si M = 1 : ?=? µ (19-2) Le nombre moyen de clients en file : nl est obtenu a partir d’une table ou de la formule appropriee, selon le modele en question. Le nombre de clients dans le systeme : ns = nl + ? Le temps moyen d’attente en file : tl = nl ? (19-3) (19-4) Le temps moyen d’attente dans le systeme : ts = tl + 1 = ns ? (19-5) Pour ces modeles, le taux d’utilisation du systeme doit etre inferieur a 1 (? < Mµ). D’autre part, ces modeles ne s’appliquent qu’a des systemes non congestionnes. Il n’y a aucune utilite a analyser les systemes dans lesquels ? > Mµ, car il est evident que dans de tels cas, ils sont congestionnes. Le nombre moyen de clients qui attendent en file (nl) est l’element cle qui sert a determiner les autres mesures de performance du systeme, tels le nombre moyen de clients dans le systeme, le temps moyen passe en file et le temps moyen passe dans le systeme.

Par consequent, lorsqu’on veut resoudre des problemes de files d’attente, la premiere mesure de performance a considerer est nl. Les clients d’une boulangerie se presentent generalement en matinee (calcul effectue selon la loi de Poisson), a raison de 18 clients en moyenne a l’heure. On estime que chaque vendeur au comptoir peut servir un client (temps distribue selon une loi exponentielle) en moyenne en quatre minutes. a) Quels sont les taux d’arrivee et de service ? Calculez le nombre moyen de clients en train d’etre servis (supposez que le taux d’utilisation du systeme est inferieur a 1). ) En supposant que le nombre moyen de clients qui attendent en file est egal a 3,6, determinez le nombre moyen de clients dans le systeme, le temps moyen passe en file et le temps moyen passe dans le systeme. c) Determinez le taux d’utilisation du systeme lorsque M = 2, 3, 4 serveurs. a) Le taux d’arrivee est donne dans l’enonce du probleme : ? = 18 clients a l’heure. Il faut traduire le temps moyen de service en heures, puis deduire le taux sachant que pour une distribution exponentielle, la moyenne est egale a 1 / µ. Donc, 1 / µ = 4 minutes par client / 60 minutes par heure = 1 / 15, ce qui donne un taux moyen de service µ 15 clients a l’heure. ? = ? = 18 = 1,2 client µ 15 Solution Exemple 1 702 PARTIE V LA GESTION ET L’EXPLOITATION DU SYSTEME b) Nombre moyen de clients dans le systeme : ns = nl + ? = 3,6 + 1,2 = 4,8 clients (puisque nl est egal a 3,6) Temps moyen d’attente en file : tl = nl = 3,6 = 0,20 heure par client, ou 0,20 ? 60 minutes = 12 minutes ? 18 Temps moyen passe dans le systeme : ts = tl + 1 = nl + 1 = 0,20 + 1 = 0,267 heure, soit environ 16 minutes µ ? µ 15 c) Taux d’utilisation du systeme ? = ? /Mµ : M = 2, M = 3, M = 4, ? = 18 = 0,60 2(15) ? = 18 = 0,40 3(15) ? = 18 = 0,30 4(15)

Par consequent, lorsque la capacite de service augmente, le taux d’utilisation du systeme diminue. 19. 6. 1. 2 Modele 1 : serveur unique, temps de service exponentiel Le modele classique (le plus simple) d’analyse des files d’attente concerne les systemes comptant un seul serveur (ou une seule equipe). La regle de priorite est « premier entre, premier servi (PEPS) » ; on suppose que le processus d’arrivee suit une loi de Poisson et que le temps de service suit une loi exponentielle. Il n’y a aucune restriction quant a la longueur de la file proprement dite. Le tableau 19. presente les formules servant a calculer les mesures de performance pour un modele avec serveur unique. On les utilise conjointement avec les formules des tableaux 19. 1 a 19. 5. TABLEAU 19. 2 Formules pour le modele de base (serveur unique, temps de service exponentiel) Mesure de performance Nombre moyen de clients en file Nombre moyen de clients dans le systeme Temps moyen d’attente en ligne Temps moyen passe dans le systeme Probabilite qu’il y ait zero unite dans le systeme Probabilite qu’il y ait n unites dans le systeme Probabilite qu’il y ait moins de n unites dans le systeme Equation nl = 2 µ(µ – ? ) ? ns = (µ – ? ) ? tl = µ(µ – ? ) ts = 1 (µ – ? ) (19–6) P0 = 1 – ? Pn 0 P< n (µ) = P (? ) µ = 1 – (? ) µ n (19–7) (19–8a) n (19–8b) Exemple 2 Une compagnie aerienne envisage d’ouvrir un point de vente dans un nouveau centre commercial. Elle compte y faire travailler un agent qui sera responsable des reservations et de la vente de billets. On prevoit un achalandage de 15 clients a l’heure en moyenne ; on estime aussi que la distribution des arrivees peut etre calculee selon la loi de Poisson et que le temps de service sera de 3 minutes en moyenne par client (distribution exponentielle).

Determinez les mesures de performance suivantes : CHAPITRE 19 LES FILES D’ATTENTE 703 a) Taux d’utilisation du systeme. b) Pourcentage d’inactivite de l’agent. c) Nombre moyen de clients qui attendent pour etre servis. d) Temps moyen passe par un client dans le systeme. e) Probabilite qu’il n’y ait aucun client dans le systeme et probabilite qu’il y ait quatre clients dans le systeme. ? = 15 clients a l’heure et 3 minutes/client = temps de service = 1 µ Solution donc µ = ( 1 client ) ? 60 minutes par heure = 20 clients a l’heure 3 minute a) ? ? = 15 = 0,75 Mµ 1(20) b) Pourcentage d’inactivite = 1 – ? = 1 – 0,75 = 0,25, c’est-a-dire 25 % du temps c) nl = d) ts = ?2 152 = = 2,25 clients µ(µ – ? ) 20(20 – 15) 1 = 1 = 0,20 heure ou 12 minutes (µ – ? ) (20 – 15) e) P0 = 1 – ? = 1 – 15 = 0,25 et P4 = P0 ? 4 = 0,25 15 4 = 0,079 µ 20 µ 20 () ( ) 19. 6. 1. 3 Modele 2 : serveur unique, temps de service constant Comme nous l’avons signale precedemment, les files d’attente sont la consequence directe de phenomenes aleatoires et du degre eleve de variabilite des taux d’arrivee et de service.

Si, dans un systeme donne, on arrive a diminuer ou a reduire les variations d’un taux ou des deux, on peut egalement raccourcir les files d’attente de facon significative. Toutefois, dans le cas ou les temps de service sont constants, le nombre moyen de clients qui attendent en file diminue de moitie. 2 µ(µ – ? ) Le temps d’attente en file est aussi reduit de moitie. nl = ?2 (19-9) On retrouve ce modele dans plusieurs situations, notamment lorsque le serveur est une machine automatique. Les lave-autos en sont un exemple. Un lave-auto avec file unique a ete programme pour laver une automobile en cinq minutes.

En fin de semaine, particulierement le samedi, il arrive (selon un processus de Poisson) huit voitures a l’heure en moyenne. Determinez : a) Le nombre moyen de voitures dans la file d’attente. b) Le temps moyen passe dans la file et le temps moyen passe dans le systeme. µ = 1 toutes les 5 minutes ou encore 12 voitures a l’heure ; ? = 8 voitures a l’heure ? 2 Exemple 3 a) nl = 2µ(µ – ? ) = 82 = 0,667 voiture 2(12)(12 – 8) Solution b) tl = nl = 0,667 = 0,083 heure ou 5 minutes ? 8 ts = tl + 1 = ns + 1 = 0,667 + 1 = 0,167 heure ou 10 minutes µ ? µ 8 12 704 PARTIE V LA GESTION ET L’EXPLOITATION DU SYSTEME 19. 6. 1. Modele 3 : serveurs multiples, temps de service exponentiel Un tel modele existe lorsqu’il y a deux serveurs ou plus qui travaillent en parallele, de facon independante. Il faut tout d’abord verifier les hypotheses suivantes : 1. Le processus d’arrivee est distribue selon une loi de Poisson et le processus de service, selon une loi exponentielle. 2. Le taux de service moyen est identique pour tous les serveurs. 3. Les clients sont traites selon l’ordre d’arrivee : premier entre, premier servi (regle PEPS). Dans le tableau 19. 3, vous trouverez les formules permettant de calculer les mesures de performance de ce modele.

Vous constaterez qu’elles sont beaucoup plus complexes que celles du modele 1, particulierement celles qui determinent nl et P0. Nous vous les presentons pour montrer leur complexite et completer la description de ce modele, mais on utilise plutot le tableau 19. 4, qui donne les valeurs de nl et de P0 pour differentes valeurs de ? /µ et de M. Pour se servir du tableau 19. 4, on commence par calculer la valeur de ? /µ (arrondie aux decimales pres comme dans le tableau), puis on lit tout simplement les valeurs de nl et de P0 correspondant au nombre approprie de serveurs, M.

Par exemple, si ? /µ = 0,50 et M = 2, on peut lire : nl = 0,033 et P0 = 0,600. On peut se servir de ces valeurs pour determiner d’autres mesures de performance. Notez que les formules du tableau 19. 3 et les valeurs du tableau 19. 4 donnent des moyennes. On peut utiliser le tableau 19. 4 pour le modele 1 (serveur unique, temps de service exponentiel) en prenant M = 1. TABLEAU 19. 3 Formules pour le modele de files d’attente (serveurs multiples, temps de service exponentiel) Mesure de performance Nombre moyen de clients en file Equation M ? µ ? µ nl = P0 (M – 1)! (Mµ – ? )2 () (19–10) M –1

Probabilite qu’il y ait zero unite dans le systeme Temps moyen d’attente pour un client potentiel non servi immediatement Probabilite qu’un client potentiel attende avant d’etre servi M–1 P0 = n–0 ? (? ) µ n! n + (? ) µ ( M! 1 – ? Mµ ) (19–11) ta = PW = l Mµ – ? tl ta (19–12) (19–13) TABLEAU 19. 4 Valeurs de nl et de P0 pour des valeurs de ? /µ et de M donnees ?/µ 0,15 0,20 0,25 0,30 0,35 0,40 0,45 M 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 nl 0,026 0,001 0,050 0,002 0,083 0,004 0,129 0,007 0,188 0,011 0,267 0,017 0,368 0,024 0,002 P0 ,850 ,860 ,800 ,818 ,750 ,778 ,700 ,739 ,650 ,702 ,600 ,667 ,550 ,633 ,637 /µ 1,3 M 3 4 5 2 3 4 5 2 3 4 5 2 3 4 5 nl 0,130 0,023 0,004 1,345 0,177 0,032 0,006 1,929 0,237 0,045 0,009 2,844 0,313 0,060 0,012 P0 ,264 ,271 ,272 ,176 ,236 ,245 ,246 ,143 ,211 ,221 ,223 ,111 ,187 ,199 ,201 ?/µ 2,7 M 3 4 5 6 7 3 4 5 6 7 3 4 5 6 7 nl 7,354 0,811 0,198 0,053 0,014 12,273 1,000 0,241 0,066 0,018 27,193 1,234 0,293 0,081 0,023 P0 ,025 ,057 ,065 ,067 ,067 ,016 ,050 ,058 ,060 ,061 ,008 ,044 ,052 ,054 ,055 1,4 2,8 1,5 2,9 1,6 CHAPITRE 19 LES FILES D’ATTENTE 705 ?/µ 0,50 M 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 4 1 2 3 4 1 2 3 4 2 3 4 2 3 4 2 3 4 5 2 5 6 7 8 9 4 5 6 7 8 9 l 0,500 0,033 0,003 0,672 0,045 0,004 0,900 0,059 0,006 1,207 0,077 0,008 1,633 0,098 0,011 2,250 0,123 0,015 3,200 0,152 0,019 4,817 0,187 0,024 0,003 8,100 0,229 0,030 0,004 18,050 0,277 0,037 0,005 0,333 0,045 0,007 0,477 0,066 0,011 0,675 0,094 0,016 0,003 0,951 1,519 0,412 0,129 0,041 0,013 36,859 1,830 0,485 0,153 0,050 0,016 P0 ,500 ,600 ,606 ,450 ,569 ,576 ,400 ,538 ,548 ,350 ,509 ,521 ,300 ,481 ,495 ,250 ,455 ,471 ,200 ,429 ,447 ,150 ,404 ,425 ,427 ,100 ,379 ,403 ,406 ,050 ,356 ,383 ,386 ,333 ,364 ,367 ,290 ,327 ,367 ,250 ,294 ,300 ,301 ,212 ,017 ,021 ,022 ,022 ,022 ,002 ,015 ,019 ,020 ,020 ,020 /µ 1,7 M nl P0 ,081 ,166 ,180 ,182 ,053 ,146 ,162 ,165 ,026 ,128 ,145 ,149 ,149 ,111 ,130 ,134 ,135 ,096 ,117 ,121 ,122 ,081 ,105 ,109 ,111 ,068 ,093 ,099 ,100 ,056 ,083 ,089 ,090 ,091 ,045 ,074 ,080 ,082 ,082 ,035 ,065 ,072 ,074 ,074 ,004 ,008 ,009 ,010 ,010 ,010 ,003 ,007 ,008 ,008 ,009 ?/µ 3,0 M nl P0 ,038 ,047 ,049 ,050 ,050 ,032 ,042 ,044 ,045 ,045 ,027 ,037 ,040 ,040 ,041 ,023 ,033 ,036 ,037 ,037 ,019 ,029 ,032 ,033 ,033 ,015 ,026 ,029 ,030 ,030 ,030 ,011 ,023 ,026 ,027 ,027 ,027 ,008 ,020 ,023 ,024 ,025 ,025 ,005 ,005 ,005 ,005 ,005 ,005 ,005 ,004 ,004 ,004 ,004 ,005 0,55 ,8 0,60 1,9 0,65 0,70 2,0 0,75 2,1 0,80 0,85 2,2 0,90 2,3 0,95 2,4 1,0 2,5 1,1 1,2 2,6 1,3 3,8 4,6 3,9 4,7 2 4,426 3 0,409 4 0,080 5 0,017 2 7,674 3 0,532 4 0,105 5 0,023 2 17,587 3 0,688 4 0,136 5 0,030 6 0,007 3 0,889 4 0,174 5 0,040 6 0,009 3 1,149 4 0,220 5 0,052 6 0,012 3 1,491 4 0,277 5 0,066 6 0,016 3 1,951 4 0,346 5 0,084 6 0,021 3 2,589 4 0,431 5 0,105 6 0,027 7 0,007 3 3,511 4 0,533 5 0,130 6 0,034 7 0,009 3 4,933 4 0,658 5 0,161 6 0,043 7 0,011 5 9,289 6 1,487 7 0,453 8 0,156 9 0,054 10 0,018 5 13,382 6 1,752 7 0,525 8 0,181 9 0,064 3,1 3,2 3,3 3,4 3,5 3,6 3,7 3,8 5,3 1,528 5 0,354 6 0,099 7 0,028 8 0,008 4 1,902 5 0,427 6 0,120 7 0,035 8 0,010 4 2,386 5 0,513 6 0,145 7 0,043 8 0,012 4 3,027 5 0,615 6 0,174 7 0,052 8 0,015 4 3,906 5 0,737 6 0,209 7 0,063 8 0,019 4 5,165 5 0,882 6 0,248 7 0,076 8 0,023 9 0,007 4 7,090 5 1,055 6 0,295 7 0,019 8 0,028 9 0,008 4 10,347 5 1,265 6 0,349 7 0,109 8 0,034 9 0,010 4 16,937 8 0,422 9 0,155 10 0,057 11 0,021 12 0,007 12 0,007 7 1,444 8 0,483 9 0,178 10 0,066 11 0,024 TABLEAU 19. 4 (suite) 706 PARTIE V LA GESTION ET L’EXPLOITATION DU SYSTEME TABLEAU 19. 4 (suite) ?/µ 4,0 M 5 6 7 8 9 5 6 7 8 9 5 6 7 8 9 10 5 6 7 8 9 10 5 6 7 8 9 10 5 6 7 8 9 10 l 2,216 0,570 0,180 0,059 0,019 2,703 0,668 0,212 0,070 0,023 3,327 0,784 0,248 0,083 0,027 0,009 4,149 0,919 0,289 0,097 0,033 0,011 5,268 1,078 0,337 0,114 0,039 0,013 6,862 1,265 0,391 0,133 0,046 0,015 P0 ,013 ,017 ,018 ,018 ,018 ,011 ,015 ,016 ,016 ,017 ,009 ,013 ,014 ,015 ,015 ,015 ,008 ,012 ,130 ,013 ,014 ,014 ,006 ,010 ,012 ,012 ,012 ,012 ,005 ,009 ,010 ,011 ,011 ,011 ?/µ 4,8 M nl P0 ,009 ,002 ,006 ,008 ,008 ,008 ,008 ,001 ,005 ,007 ,007 ,007 ,007 ,077 ,005 ,006 ,006 ,007 ,007 ,007 ,004 ,005 ,006 ,006 ,006 ,006 ,003 ,005 ,005 ,005 ,005 ,006 ,003 ,004 /µ 5,5 M 12 6 7 8 9 10 11 12 6 7 8 9 10 11 12 6 7 8 9 10 11 12 6 7 8 9 10 11 12 6 7 8 9 10 nl 0,009 8,590 1,674 0,553 0,204 0,077 0,028 0,010 11,519 1,944 0,631 0,233 0,088 0,033 0,012 16,446 2,264 0,721 0,266 0,102 0,038 0,014 26,373 2,648 0,823 0,303 0,116 0,044 0,017 56,300 3,113 0,939 0,345 0,133 P0 ,005 ,002 ,003 ,004 ,004 ,004 ,004 ,004 ,001 ,003 ,003 ,004 ,004 ,004 ,004 ,001 ,002 ,003 ,003 ,003 ,003 ,003 ,001 ,002 ,003 ,003 ,003 ,003 ,003 ,000 ,002 ,002 ,003 ,003 4. 2 4,9 4,2 5,0 4,3 5,1 4,4 5,2 4,5 5,3 0 0,022 5 21,641 6 2,071 7 0,607 8 0,209 9 0,074 10 0,026 5 46,566 6 2,459 7 0,702 8 0,242 9 0,087 10 0,031 11 0,011 6 2,938 7 0,810 8 0,279 9 0,101 10 0,036 11 0,013 6 3,536 7 0,936 8 0,321 9 0,117 10 0,042 11 0,015 6 4,301 7 1,081 8 0,368 9 0,135 10 0,049 11 0,017 6 5,303 7 1,249 5,6 5,7 5,8 5,9 Exemple 4 La compagnie Taxi-Air possede sept taxis stationnes a l’aeroport de Dorval. Les statistiques de la compagnie indiquent que durant les heures tardives des jours ouvrables de la semaine, les clients se presentent pour prendre un taxi (selon un processus de Poisson) a une cadence moyenne de 6,6 clients a l’heure.

Le service, quant a lui, suit une distribution exponentielle de 50 minutes en moyenne. Le service consiste a prendre un client a l’aeroport, a le conduire a destination et a revenir a l’aeroport pour se placer en file, dans l’attente d’autres clients. Determinez chacune des mesures de performance presentees dans le tableau 19. 3, ainsi que le taux d’utilisation du systeme. ? = 6,6 clients a l’heure et M = 7 voitures (serveurs) µ= Solution 1 client/voyage = 1,2 client a l’heure (50 min/voyage ? 60 min/h) A partir du tableau 19. 4 : en considerant ? /µ = 5,5 et M = 7, on peut lire : a) nl = 1,674 b) P0 = 0,003 c) ta = 1 – ? 1 (1,2) – 6,6 = 0,556 heure ou 33,36 minutes 7 Mµ CHAPITRE 19 LES FILES D’ATTENTE 707 d) tl = nl = 1,674 = 0,2536 heure ou 15,22 minutes, donc : ? 6,6 PW = tl = 0,2536 = 0,456 ; ta 0,556 il y a 45,6 % de chances qu’un client potentiel attende avant d’etre servi. e) ? = ? = 6,6 (1,2) = 0,786 ; le systeme est utilise a 78,6 % de sa capacite. 7 Mµ Avec Excel, la solution de l’exemple 4 apparait comme suit : Le processus de resolution peut etre inverse, c’est-a-dire que l’analyste peut determiner la capacite requise pour satisfaire a des niveaux specifies de performance. L’exemple ci-dessous illustre cette approche.

La compagnie Taxi-Air envisage de desservir une nouvelle gare. Le taux moyen d’arrivee des clients a la gare est de 4,8 clients a l’heure et le taux de service (aller-retour) est de 1,5 client a l’heure. Combien de taxis seront necessaires pour obtenir un temps d’attente moyen tolerable de 20 minutes ou moins ? ? = 4,8 clients a l’heure, µ = 1,5 client a l’heure, M = ? ? = ? = 4,8 = 3,2 µ 1,5 Exemple 5 Solution tl = 20 minutes ou 0,333 heure (attente moyenne desiree) nl = ? ? tl = 4,8 ? 0,333 = 1,6 unite. Donc, le nombre moyen de clients qui attendent ne doit pas depasser 1,6. A partir du tableau 19. , avec ? /µ = 3,2, nl = 2,386 pour M = 4 et nl = 0,513 pour M = 5. Taxi-Air a besoin de 5 voitures pour obtenir 20 minutes comme temps d’attente moyen tolerable. 19. 6. 1. 5 Optimisation des files d’attente Pour concevoir un systeme, on calcule et on compare le cout associe au niveau de service (capacite de service) et le cout d’attente des clients (cout encouru par l’entreprise en raison de l’attente des clients dans le systeme). Par exemple, lorsqu’on concoit un quai de chargement pour un entrepot, on etudie le cout du quai plus le cout des 708 PARTIE V LA GESTION ET L’EXPLOITATION DU SYSTEME quipes de chargement par rapport au cout associe a l’attente des camions (chargement et dechargement). Meme chose pour le cout du mecanicien qui attend des outils devant un centre d’outillage : il doit etre equilibre avec le cout du serveur du centre d’outillage. Dans le cas ou les clients sont externes a l’entreprise (commerces de detail, par exemple), les couts vont inclure les ventes perdues a cause du refus du client d’attendre, le cout associe a l’espace d’attente mis en place par l’entreprise et le cout associe a la congestion du systeme (perte de clients, vols a l’etalage, etc. ).

La capacite optimale de service (en general, le nombre de serveurs qui travaillent en parallele) est celle qui permet de reduire le cout total de gestion de l’attente. Ce cout total est la somme du cout d’attente des clients et du cout de la capacite de service. L’objectif est donc de minimiser le cout total. Cout total (CT) = cout d’attente (Ca) + cout de service (Cs) L’approche d’optimisation consiste a calculer le cout total du systeme en fonction de differentes valeurs correspondant au nombre de serveurs. Apres un certain nombre d’iterations, on etablit la capacite qui minimise le cout total.

Comme la courbe representant le cout total est en forme de U, le fait d’augmenter le nombre de serveurs va faire en sorte que le cout total va diminuer jusqu’a atteindre le minimum. A partir de la, le fait d’augmenter la capacite va plutot engendrer une augmentation du cout total. C’est donc a ce point que se situe la capacite optimale. Le cout d’attente se calcule en fonction du nombre moyen de clients dans le systeme. Cela n’est peut-etre pas intuitivement evident et on serait plutot tente de considerer le temps moyen d’attente dans le systeme. Or, ce serait ne tenir compte que d’un seul client.

Cela ne donnerait pas d’informations concernant le nombre de clients qui attendent pendant ce temps. Il est evident que le cout engendre par la presence de cinq clients en moyenne qui attendent va etre moindre que celui d’en avoir neuf. Par consequent, il est necessaire de se concentrer sur le nombre de clients en attente. Par ailleurs, si on a en moyenne deux clients dans le systeme, cela equivaut a avoir exactement deux clients dans le systeme en tout temps, malgre le fait qu’en realite, on aura a certains moments zero, un, deux, trois clients ou plus dans le systeme. Exemple 6

Les camions arrivent a un entrepot durant les jours ouvrables de la semaine selon un processus de Poisson, a raison de 15 camions a l’heure. Les equipes de manutention dechargent 5 camions a l’heure ; le processus de service suit une distribution exponentielle. Le taux eleve de dechargement est du au fait que le transport se fait par conteneurs, ce qui rend le processus plus facile. La mise en application de la derniere convention syndicale etant prevue pour tres bientot, le directeur de la logistique voudrait reexaminer son processus de chargement/dechargement, notamment le nombre de manutentionnaires requis au quai.

Les nouveaux couts sont le salaire d’un manutentionnaire, auquel s’ajoute le cout d’exploitation du quai, estime a 100 dollars l’heure, alors que le cout d’attente d’un chauffeur et de son camion est estime a 120 dollars l’heure. A partir du tableau 19. 4, on determine nl en utilisant : ? / µ = 15 / 5 = 3. Taille de l’equipe Cout de service Cs = 100 $ ? M Nombre moyen de clients dans le systeme ns = nl + ? µ 1,528 + 3 = 4,528 0,354 + 3 = 3,354 0,099 + 3 = 3,099 0,028 + 3 = 3,028 Cout d’attente Ca = 120 $ ? nl Cout total (CT) Solution 4 5 6 7 400 500 600 700 43,36 402,48 371,88 363,36 943,36 902,48 971,88 1063,36 CHAPITRE 19 LES FILES D’ATTENTE 709 La configuration optimale est une equipe de manutentionnaires composee de cinq personnes. Puisque le cout total va continuer d’augmenter une fois le minimum atteint, il n’est pas necessaire de calculer les couts totaux correspondant a des equipes de huit personnes ou plus. On voit bien que le cout total correspondant a la solution optimale est de 902,48 dollars et qu’il ne cesse d’augmenter. Apres le cout total de 902,48 dollars, on entame la phase ascendante de la courbe en U.

Remarque : Soulignons que lorsqu’on fait de l’optimisation, les couts d’attente et de service sont des estimations, donc la solution optimale obtenue peut ne pas etre la vraie. Le fait de calculer le cout total au cent pres ou meme au dollar pres semble indiquer un degre eleve de precision, ce qui n’est pas corrobore par les estimations des couts. Cela est egalement complique par le fait que les approximations des taux d’arrivee et de service par les distributions de Poisson et exponentielle peuvent etre fausses.

Une autre solution serait d’estimer les couts par intervalles (par exemple, le cout d’attente des clients serait compris entre 40 et 50 dollars l’heure). Dans ce cas, on devrait calculer le cout total pour chacune des limites afin de verifier si la solution optimale est affectee. Si oui, le gestionnaire devra decider s’il est necessaire de faire des efforts supplementaires pour obtenir plus de precision dans les estimations des couts ou tout simplement choisir une des deux solutions optimales obtenues. Le gestionnaire choisira probablement cette derniere approche si es variations dans le cout total pour differents niveaux de capacite sont minimes par rapport aux solutions optimales obtenues. 19. 6. 1. 6 Capacite maximale de la file d’attente Un autre point important est a considerer : la capacite maximale de la file d’attente proprement dite, c’est-a-dire la longueur maximale en termes d’espace disponible. Theoriquement, dans le cas d’une population infinie, la file d’attente peut devenir indefiniment longue, et l’espace disponible peut etre insuffisant pour accueillir tous les clients.

Par exemple, les clients qui arrivent pour laver leur automobile dans une station libre-service proviennent d’une population infinie, et l’espace disponible est limite au nombre de voitures qui peuvent attendre en file sans perturber la circulation. Par contre, dans le cas des voitures qui arrivent de l’Etat de New York et qui se presentent au controle frontalier de Lacolle, au Quebec, la longueur de la file correspond a toute l’autoroute 87. D’un point de vue pratique, on peut toujours determiner la longueur de la file d’attente qui ne sera pas depassee pour un certain pourcentage de temps specifie.

Par exemple, un analyste pourrait determiner la longueur de la file qui ne sera pas depassee 98 % ou 99 % du temps. Pour fixer la longueur de la file d’attente, on utilise les equations suivantes : n = log K ou ln K ou K = 1 – pourcentage specifie log ? ln ? nl(1 – ? ) (19-14) La valeur de n n’est generalement pas un nombre entier ; il faudra donc arrondir le nombre. Cependant, en pratique, si la valeur de n est inferieure a 0,10 au-dessus du nombre entier le plus petit, on arrondit vers le bas. Par exemple, si n = 15,2, alors n = 16 ; si n = 15,06, alors n = 15, n etant le nombre d’unites a servir.

Determinez la longueur maximale de la file permettant d’atteindre des niveaux de satisfaction de 95 % et de 98 %. Les caracteristiques du systeme sont : M = 2, ? = 8 a l’heure, µ = 5 a l’heure ? = ? = 8 = 1,6 µ 5 Exemple 7 et ? = ? = 8 = 0,80 Mµ 2(5) Solution A partir du tableau 19. 4, on obtient nl = 2,844 clients. 710 PARTIE V LA GESTION ET L’EXPLOITATION DU SYSTEME Si on utilise la formule 19-4, on obtient, pour 95 % : 1 – 0,95 K = 1 – pourcentage specifie = = 0,088 2,844 (1 – 0,80) nl(1 – ? ) n = ln K = ln 0,088 = –2,4304 ? 10,89 ? 11 ln ? ln 0,80 –0,2231 Pour 98 % : K= 1 – 0,98 ? 0,035 2,844(1 – 0,80) = ln 0,035 = –3,352 = 15,02 ? 15 ln 0,80 –0,2231 19. 6. 1. 7 Modele 4 : serveurs multiples et regles de priorite Dans la majorite des systemes de files d’attente, particulierement ceux des services, la regle de priorite pour le traitement des clients est la regle du premier entre, premier servi (PEPS). Cependant, dans plusieurs situations, cette regle est inapplicable, car le cout ou les consequences qui en resultent ne sont pas les memes. Par exemple, dans les salles d’urgence des hopitaux, ou les clients sont malades ou accidentes, la rapidite de la prise en charge des patients depend de la gravite de la situation.

Certains patients peuvent etre traites assez rapidement par l’infirmiere, alors que d’autres, dont la vie est en danger, ont besoin de plusieurs intervenants. C’est pourquoi, dans les hopitaux, il existe trois niveaux de priorite, qui vont de l’urgence (intervention immediate) au cas le plus simple. Meme chose pour le traitement des programmes a executer sur un ordinateur central, qui se fait selon la regle donnant la priorite au temps d’operation le plus court. Ces exemples illustrent l’importance des modeles de files d’attente qui prennent en consideration plusieurs regles de priorite.

Dans ces systemes, on attribue aux clients qui se presentent une des regles de priorite 2 disponibles. Par regle de priorite, on entend l’ordre de traitement des clients (dans une salle d’urgence, une personne inconsciente ou ayant une crise cardiaque aura la priorite la plus elevee, celle qui a subi une blessure mineure aura la priorite la plus faible, et les autres auront une priorite intermediaire). Ainsi, les clients sont classes par categories en fonction de la regle de priorite qui leur est attribuee.

Dans chaque classe ou categorie, le traitement se fait selon la regle du premier entre, premier servi (PEPS), puisque les clients d’une meme categorie ont la meme importance. Lorsque les clients d’une classe ont tous ete servis, on passe a la classe inferieure. Si un client de la classe superieure se presente, deux situations sont possibles, selon qu’il y a preseance ou non. S’il n’y a pas priorite, son traitement ne commence que lorsque le client en traitement a fini de se faire servir ; dans le cas contraire, il est traite immediatement.

Quant aux hypotheses, ce sont les memes que celles du modele 3 (serveurs multiples avec temps de service exponentiel), excepte que ce modele utilise des regles de priorite de traitement autres que la regle PEPS. On attribue aux clients qui arrivent une priorite (priorite 1 a n). Une file d’attente organisee selon des regles de priorite aurait l’allure de celle qui est representee ci-dessous : File d’attente modele avec regles de priorite multiples Les clients sont traites par ordre d’importance. Arrivees 4 3 3 3 2 1 1 Traitement Sortie Chaque client est traite selon la regle PEPS dans chacune des categories.

On commence par servir le client no 1 de la classe 1, puis le no 2 de la classe 1, puis le no 1 de 2. Pour plus de details sur ce sujet, voir le chapitre 17. CHAPITRE 19 LES FILES D’ATTENTE 711 la classe 2, et ainsi de suite. A ce point, si un client de la classe 1 ou 2 se presente, on le placera devant le premier client de la classe 3. Si un client de la classe 4 se presente, il sera place a la fin de la file, juste apres le seul client de la classe 4. Il est evident que les clients dont la priorite est la moins elevee pourraient attendre assez longtemps, ce qui serait intolerable. Dans ce cas, on leur attribue une priorite plus elevee.

Le tableau 19. 5 donne les formules permettant de calculer les principales mesures de performance de ce modele. Mesure de performance Taux d’utilisation Formule ? = ? Mµ A= ? (1 – ? )nl c=1 Reference (19-15) TABLEAU 19. 5 Formules pour le modele avec regles de priorite multiples Mesures intermediaires (nl a determiner a partir du tableau 19. 4) (19-16) ? Mµ Bk = 1 – (B0 = 1) ? k (19-17) Temps moyen d’attente en file pour les clients de la classe k (priorite k) Temps moyen d’attente dans le systeme pour les clients de la classe k (priorite k) Nombre moyen de clients de la classe k (priorite k) qui attendent en file k = 1 A * Bk – 1 * Bk (19-18) ts = tk + 1 µ (19-19) nk = ? k * tk (19-20) Une entreprise dispose de son propre centre de maintenance, ou sont repares les equipements et les outils de l’entreprise. Chaque fois qu’un equipement ou qu’un outil arrive au centre, on y attribue une priorite en fonction de l’urgence du besoin. Le taux de demandes de reparations peut etre etabli avec une distribution de Poisson. Les taux d’arrivee sont : ? 1 = 2 a l’heure, ? 2 = 2 a l’heure, et ? 3 = 1 a l’heure. Le taux de service est de un equipement ou outil a l’heure par reparateur et il y a six reparateurs dans le centre de maintenance.

Determinez les mesures de performance suivantes : a) Le taux d’utilisation du systeme. Pour chaque categorie de priorite, determinez : b) Le temps moyen d’attente pour la reparation. c) Le temps moyen passe dans le systeme pour chaque equipement ou outil. d) Le nombre moyen d’equipements ou d’outils en attente d’etre repares. ?= Exemple 8 ?? k = 2 + 2 + 1 = 5 a l’heure Solution M = 6 serveurs µ = 1 client a l’heure a) ? = ? = 5 = 0,833 Mµ 6(1) b) Valeurs intermediaires pour ? = 5 = 5 ; a partir du tableau 19. 4, nl = 2,938 µ 1 A= 5 = 10,19 (1 – 0,833)2,938 712

PARTIE V LA GESTION ET L’EXPLOITATION DU SYSTEME B0 = 1 B1 = 1 – 2 = 2 = 0,667 6(1) 3 B2 = 1 – 2 + 2 = 1 = 0,333 6(1) 3 B3 = 1 – 2 + 2 + 1 = 1 = 0,167 6(1) 6 t1 = t2 = t3 = 1 1 = = 0,147 heure A * B0 * B1 10,19(1)(0,667) 1 1 = = 0,442 heure A * B1 * B2 10,19(0,667)(0,333) 1 = A * B2 * B3 1 = 1,765 heure 10,19(0,333)(0,167) µ µ 1 c) Temps moyen dans le systeme = ts = tk + 1 ; dans ce cas-ci, 1 = 1 = 1 Categorie 1 2 3 ts = tk + 1 0,147 + 1 = 1,147 0,442 + 1 = 1,442 1,765 + 1 = 2,765 d) Le nombre moyen d’unites qui attendent d’etre reparees : Categorie 1 2 3 ? • t k = n k 2(0,147) = 0,294 2(0,442) = 0,884 1(1,765) = 1,765 La solution de l’exemple 8 etablie avec le tableur Excel est presentee ci-dessous : CHAPITRE 19 LES FILES D’ATTENTE 713 Si les gestionnaires jugent trop longs les temps d’attente calcules dans l’exemple 8 (par exemple le temps moyen d’attente de 0,147 heure, soit environ 9 minutes pour les equipements de priorite 1), ils peuvent choisir d’autres options. L’une d’elles serait d’augmenter le nombre de serveurs. Une autre option serait d’essayer d’augmenter le taux de service, par exemple en introduisant de nouvelles methodes de travail.

Si toutes ces tentatives s’averent infructueuses, ils devraient revoir l’attribution de l’ordre de priorite et ramener certaines demandes de reparation de la classe de priorite 1 a la classe inferieure. Cela aura pour effet de diminuer le temps moyen d’attente de la classe de priorite 1, tout simplement parce que le taux d’arrivee aura diminue. L’exemple 9 illustre des resultats interessants concernant cette approche. On constate que la reduction du taux d’arrivee de la classe superieure — grace a l’attribution d’une cote de priorite inferieure a certains clients — a pour consequence de reduire le temps moyen d’attente de cette classe.

On constate aussi que le temps moyen d’attente de la classe inferieure a diminue, meme si on a augmente le nombre de clients de cette classe. Notez que le temps total d’attente (quand toutes les arrivees sont prises en consideration) restera inchange. On peut le verifier en comparant le nombre moyen de clients qui attendent (exemple 8d) : 0,294 + 0,884 + 1,765 = 2,943) avec le nombre d’unites en attente dans les trois classes, qui est (a partir des temps moyens d’attente de chaque classe de l’exemple 9) : =1 ? 3 ?k * tk = 1,5(0,131) + 2,5(0,393) + 1,0 (1,765) = 2,944 Les totaux sont pratiquement identiques, a part une difference negligeable due aux nombres arrondis. On peut faire une autre observation interessante : le temps moyen d’attente des clients de la troisieme classe n’a pas change par rapport a l’exemple precedent. Par consequent, les unites ayant priorite la plus faible vont toujours etre en competition avec le taux d’arrivee combine de 4 des deux autres classes superieures.

Apres avoir analyse les besoins de ses clients internes, le directeur de la logistique voudrait maintenant reviser la liste des outils classes dans la categorie ayant la priorite la plus elevee. Ce besoin se traduit par la revision des taux d’arrivee. Les nouveaux taux sont : ? 1 = 1,5 ; ? 2 = 2,5 ; ? 3 reste inchange, egal a 1. Determinez les mesures de performance suivantes : a) Le taux d’utilisation du systeme. b) Le temps moyen d’attente pour chacune des classes. ?= Exemple 9 ?? k = 1,5 + 2,5 + 1 = 5 a l’heure Solution M = 6 serveurs µ = 1 client a l’heure Notez