Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

BENAISSA Mounir Docteur Ing. : Génie Industriel Cours Ingénierie des Systèmes I

BENAISSA Mounir Docteur Ing. : Génie Industriel Cours Ingénierie des Systèmes Industriels ( Planification & Ordonnancement) Chapitre 1: Modèles de Files d’attente Chapitre 2: Planification de la production Chapitre 3: Ordonnancement de la production Le Plan du cours…. Chapitre 1: MODELES DE FILES D’ATTENTE 1.INTRODUCTION 2. MESURES DE PERFERMANCE 3. PROCESSUS DE POISSON 4. DISTRIBUTION EXPONENTIELLE 5. NOTATION DE KENDALL 6. PROCESSUS DE NAISSANCE ET DE MORT: CAS GENERAL 7. PROCESSUS DE NAISSANCE ET DE MORT: CAS PARTICULIERS 1. MODELES DE FILES D’ATTENTE: INTRODUCTION La théorie des files d'attente s’attache à modéliser et à analyser de nombreuses situations très diverses: • Des clients arrivent à intervalles aléatoires dans un système comportant plusieurs serveurs auxquels ils vont adresser une requête. La durée du service auprès de chaque serveur est elle- même aléatoire. Après avoir été servis (ce qui suppose un arrêt chez un ou plusieurs serveurs selon le cas), les clients quittent le système. Le but de l'analyse est de caractériser le degré de performance du système en répondant à des questions du type suivant: • en moyenne, combien de temps attend un client avant d'être servi? • quel est le nombre moyen de clients dans le système? • quel est le taux d'utilisation moyen des serveurs? 1.Structure générale d’un système de files d’attente Départs Clients Arrivées Clients 1. Exemple d’un système de files d’attente Agence bancaire Ici, les serveurs sont les guichets de l'agence. Typiquement, tous les guichets offrent le même service, et chaque client ne devra donc visiter qu'un seul guichet. Atelier de production Les ‘clients’ sont les ordres de fabrication à exécuter, et les 'serveurs' sont les machines nécessaires à l'exécution de chaque ordre de fabrication. Parking Les 'clients' sont les véhicules qui cherchent à stationner. Les 'serveurs' sont les emplacements de parking, et la 'durée de service' est la durée pendant laquelle chaque véhicule reste stationné. 1.Les différents Types d’un système de files d’attente Les systèmes à serveurs parallèles: où chaque client ne réclame le service que d'un seul serveur et tous les serveurs sont capables de fournir ce service. Les systèmes à serveurs en série, où chaque client doit visiter plusieurs serveurs successifs dans un ordre fixe pour recevoir satisfaction. Arrivées Départs Arrivées Départs 1.Caractéristiques d’un système de files d’attente Les arrivées de clients peuvent être groupées ou individuelles; de même pour le service par chaque serveur. Les clients forment une ou plusieurs files d'attente, éventuellement caractérisées par des priorités différentes. Au sein de chaque file, le prochain client à servir est sélectionné sur base d'une règle prédéterminée, appelée discipline de service. Les disciplines de service les plus courantes sont: premier arrivé premier servi (First In First Out, First Come First Served) , temps de service le plus court d'abord (utilisé dans les ateliers de production), dernier arrivé premier servi, sélection aléatoire, etc. La capacité du système, c’est-à-dire le nombre de clients pouvant être simultanément présents dans le système, est limitée ou non. Dans le premier cas, on suppose que les clients qui arrivent lorsque le système est déjà saturé le quittent immédiatement sans obtenir le service désiré. On dit que ces clients sont perdus. Dans le cas d'un système à capacité illimitée, bien sûr, aucun client n'est perdu (mais la longueur des files d'attente peut grandir indéfiniment !). 1. Hypothèses Dans ce cours, nous nous limiterons à l'étude de systèmes • à serveurs parallèles • à arrivées et service individuels. Nous supposerons également que tous les clients demandent le même service et que les serveurs sont identiques. Chapitre 1: MODELES DE FILES D’ATTENTE 1.INTRODUCTION 2. MESURES DE PERFERMANCE 3. PROCESSUS DE POISSON 4. DISTRIBUTION EXPONENTIELLE 5. NOTATION DE KENDALL 6. PROCESSUS DE NAISSANCE ET DE MORT: CAS GENERAL 7. PROCESSUS DE NAISSANCE ET DE MORT: CAS PARTICULIERS 2. Mesures de performance - Comportement à long terme Nous appelons état d'un système à l'instant t le nombre n(t) de clients présents dans le système à cet instant (un client est « présent dans le système » si il est en file d’attente ou en cours de service). Les quantités fondamentales auxquelles s'intéresse l'analyste dans le cadre des modèles de files d'attente sont les probabilités d'état, que nous définissons de la façon suivante: pour n = 0, 1, 2, ... et t 0, • pn(t) = probabilité de l'état n à l'instant t (1) • probabilité que n clients soient présents dans le système à l'instant t  Sous certaines conditions, les probabilités à long terme ou probabilités stationnaires existent pour n = 0, 1, 2, ... et définissent effectivement une mesure de probabilité : ) ( lim t p p n t n ∞ → = ≥ (2) 1 0 = ∑ ∞ = n n p 2. Mesures de performance - Comportement à long terme Lorsque les probabilités (1) et/ou (2) sont connues, il est possible de calculer de nombreuses mesures de performance du système de files d’attente à étudier. Parmi les plus importantes, on considérera les mesures à long terme suivantes: Ls = nombre espéré de clients dans le système (à un instant quelconque dans le long terme) Lq = nombre espéré de clients dans la file d'attente (à un instant quelconque dans le long terme) Ws = temps espéré passé par chaque client dans le système (dans le long terme) Wq = temps espéré passé par chaque client dans la file d'attente (dans le long terme). 2.Mesures de performance - Comportement à long terme Par définition, on a: ∑ ∞ = = 0 n n np Ls (3) De plus, si le système comporte c serveurs parallèles, alors ∑ ∞ + = − = 1 ) ( c n n p c n Lq (4) 2. Mesures de performance - Comportement à long terme • = taux d'entrée moyen des clients dans le système (nombre moyen de clients entrant dans le système par unité de temps). • L’équation suivante, désignée sous le nom de loi de Little, lie les paramètres Ls, Ws et et permet donc de calculer l’une de ces quantités lorsque les deux autres sont connues: eff λ eff λ Proposition 1. (Loi de Little) Pour tout système de files d’attente, eff Ws Ls λ × = eff Wq Lq λ × = (5) (6) De même Notons que: • La durée moyenne du service, par client = Ws - Wq • Le nombre moyen de serveurs occupés = Ls - Lq (7) (8) EXEMPLE 1 Le gestionnaire d'un petit atelier enregistre en moyenne 5 commandes par jour. Les 6 ouvriers employés dans l’atelier sont très polyvalents, si bien que chaque commande peut être réalisée par n’importe lequel d’entre eux. Néanmoins, le gestionnaire est inquiet car il constate que les ouvriers sont occupés en permanence et que son carnet de commandes contient, en moyenne, une vingtaine de commandes en cours (enregistrées, mais non satisfaites). Pour mieux comprendre la situation, le gestionnaire aimerait estimer le temps moyen consacré par les ouvriers à chaque commande. Il voudrai également pouvoir annoncer à ses clients, au moment de la passation de commande, un délai de livraison attendu. Chapitre 1: MODELES DE FILES D’ATTENTE 1.INTRODUCTION 2. MESURES DE PERFERMANCE 3. PROCESSUS DE POISSON 4. DISTRIBUTION EXPONENTIELLE 5. NOTATION DE KENDALL 6. PROCESSUS DE NAISSANCE ET DE MORT: CAS GENERAL 7. PROCESSUS DE NAISSANCE ET DE MORT: CAS PARTICULIERS 3. PROCESSUS DE POISSON Nous notons N(t) le nombre d'arrivées de clients survenues dans l'intervalle de temps [0, t), pour t 0. La quantité N(a+t) - N(a) représente alors le nombre d’arrivées enregistrées entre les instants a et a+t, pour tout a 0 et t 0. ≥ ≥ ≥ Le processus d'arrivée peut bien sûr présenter des caractéristiques variées en fonction de la situation modélisée. Mais il est fréquent dans la pratique que ce processus soit (du moins en première approximation) un processus de Poisson, ce qui signifie qu'il existe un paramètre > 0 (appelé taux du processus) tel que: λ 3. PROCESSUS DE POISSON (i) le nombre d'arrivées dans tout intervalle [a,a+t) de longueur t suit une loi de Poisson de moyenne , c'est-à-dire: pour a, t 0 et n = 0, 1, 2, ... t λ ≥ ! ) ( ] ) ( ) ( Pr[ n t e n a N t a N n t λ λ − = = − + (ii) si [a,b) et [c,d) sont des intervalles de temps disjoints, alors le nombre d'arrivées dans [a,b) est indépendant du nombre d'arrivées dans [c,d). (iii) N(0) = 0. 3. PROCESSUS DE POISSON Pour un intervalle de longueur t fixée, disons [0,t), le nombre espéré d'arrivées se calcule comme suit: ∑ ∞ = = = 0 ] ) ( Pr[ )] ( [ n n t N n t N E ∑ ∞ = − = 0 ! ) ( n n t n t ne λ λ ∑ ∞ = − − − = 1 1 )! 1 ( ) ( n n t n t te λ λ λ Si l'on se souvient que , on obtient ∑ ∞ = = uploads/Industriel/cours-isiii.pdf