{"id":140,"date":"2009-07-27T08:49:43","date_gmt":"2009-07-27T06:49:43","guid":{"rendered":"http:\/\/wp1.fredptitgars.net\/index.php\/2009\/07\/27\/les-files-dattentes\/"},"modified":"2009-07-27T08:49:43","modified_gmt":"2009-07-27T06:49:43","slug":"les-files-dattentes","status":"publish","type":"post","link":"https:\/\/fredptitgars.ovh\/?p=140","title":{"rendered":"Les files d&rsquo;attentes"},"content":{"rendered":"<h2>I\/ D\u00e9finition<\/h2>\n<p><strong>Une file d&rsquo;attente est caract\u00e9ris\u00e9e par :<\/strong><br \/>\n&#8211; Un flot d&rsquo;arriv\u00e9es<br \/>\n&#8211; Un m\u00e9canisme de service<br \/>\n&#8211; Une file d&rsquo;attente<br \/>\n&#8211; Une discipline de service<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\" aligncenter size-full wp-image-139\" src=\"https:\/\/fredptitgars.ovh\/wp-content\/uploads\/2009\/07\/file_attente-3ab.png\" alt=\"file_attente.png\" align=\"center\" width=\"424\" height=\"198\" srcset=\"https:\/\/fredptitgars.ovh\/wp-content\/uploads\/2009\/07\/file_attente-3ab.png 424w, https:\/\/fredptitgars.ovh\/wp-content\/uploads\/2009\/07\/file_attente-3ab-300x140.png 300w\" sizes=\"auto, (max-width: 424px) 100vw, 424px\" \/><\/p>\n<p><strong>Capacit\u00e9 de la file d&rsquo;attente:<\/strong><br \/>\n&#8211; nombre de places possibles : limit\u00e9 ou illimit\u00e9.<br \/>\n&#8211; Si capacit\u00e9 limit\u00e9e: les clients suppl\u00e9mentaires sont perdus ou rejoignent une autre file d&rsquo;attente.<br \/>\n&#8211; Le nombre de clients dans le syst\u00e8me est diff\u00e9rent du nombre de clients dans la file d&rsquo;attente<\/p>\n<p><strong>Discipline de service:<\/strong><\/p>\n<ul>\n<li> r\u00e8gle d&rsquo;ordonnancement des clients au service.\n<ul>\n<li> FIFO: first in first out (exemple file d&rsquo;attente \u00e0 la s\u00e9cu, 1er arriv\u00e9 1er servie)<\/li>\n<li> LIFO : Last in first out (ex: l&rsquo;ascenseur: dernier rentr\u00e9, premier sortie)<\/li>\n<li> PS : processor sharing, un serveur donne \u00e0 chaque client en attente une <em>\u201ctranche\u201d de service<\/em>. (c&rsquo;est du partage de ressources, le processeur accomplit un bout de tache sur un client puis passe au suivant &#8230; )<\/li>\n<li> ALEA un serveur libre choisit un client au hasard dans la file<\/li>\n<li> Priorit\u00e9: on ajoute une suite <em>Un<\/em>, n appartient \u00e0 N+, au flot des arriv\u00e9es o\u00f9 Un est une variable al\u00e9atoire prenant ses valeurs dans l&rsquo;ensemble des classes de priorit\u00e9s P. Un=i, signifie que le neme client, arrivant au temps Tn est de la classe i.<\/li>\n<li> Priorit\u00e9 pr\u00e9emptive : le programme preemptif passe en premier devant tous les autres et est servi en premier <\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p><strong>Notation de KENDALL A\/B\/C\/D\/E<\/strong><br \/>\n&#8211; A: statistique du processus d&rsquo;arriv\u00e9e (M = markovien; D=d\u00e9terministe; G=g\u00e9n\u00e9rale)<br \/>\n&#8211; B: statistique des lois de service (M = markovien; D=d\u00e9terministe; G=g\u00e9n\u00e9rale)<br \/>\n&#8211; C: nombre de serveurs<br \/>\n&#8211; D: nombre de clients dans le syst\u00e8me<br \/>\n&#8211; E: discipline du service<br \/>\n&#8211; M\/M\/1   ==> Mod\u00e8le le plus classique<br \/>\n&#8211; M\/M\/5\/20<br \/>\n&#8211; M\/\/\/5\/infini\/LIFO<\/p>\n<h2>LOI DE LITTLE<\/h2>\n<p>cette loi part du principe que sur le terme, la vitesse d&rsquo;arriv\u00e9e = vitesse de traitement <\/p>\n<p>HYPOTHESES<\/p>\n<ul>\n<li> Lorsqu&rsquo;un client, ayant termin\u00e9 son service, quitte le syst\u00e8me, il laisse, en moyenne, derri\u00e8re lui, un nombre de clients \u00e9gal \u00e0 E(k). Ce client a trouv\u00e9 en arrivant E(k) clients d\u00e9j\u00e0 pr\u00e9sents et a pass\u00e9 dans le syst\u00e8me un temps, E(T).<\/li>\n<li> Nous supposons que:\n<ul>\n<li> Le nombre moyen des arriv\u00e9es est \u00e9gal au nombre moyen des d\u00e9parts du syst\u00e8me.<\/li>\n<li> La longueur moyenne de la file lors des arriv\u00e9es est \u00e9gale \u00e0 la longueur moyenne de la file lors des d\u00e9parts<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>ENONCE<br \/>\n<math><\/p>\n<ul>\n<li> Si on appelle, l, le taux moyen des arriv\u00e9es on a:\n<br \/><em>Nombre moyen de clients arriv\u00e9s pendant le s\u00e9jour du client dans le syst\u00e8me<\/em> =\n$\\lambda$ E(t) = <em>nombre moyen de clients qu&rsquo;il laisse<\/em>\n<\/math><br \/>\nEt en r\u00e9gime permanent, si T temps pass\u00e9 dans la file :<\/li>\n<\/ul>\n<p><math>\n$E(k)= \\lambda E(T)$\n<br \/>$\\bar N = \\lambda \\bar T$<\/p>\n<p>$\\bar N$ : nombre de client dans le syst\u00e8me\n<br \/>$\\lambda$ : taux moyen d&rsquo;arriv\u00e9 des clients\n<br \/>$\\bar T$ : temps pass\u00e9 dans la file\n<\/math><\/p>\n<p>VALIDITE<br \/>\n&#8211; R\u00e9gime permanent<br \/>\n&#8211; Les formules de Little sont valides pour les files G\/G\/S. Elles ont un caract\u00e8re tr\u00e8s g\u00e9n\u00e9ral. En effet, il n&rsquo; y a aucune restriction quant \u00e0 :<\/p>\n<p><strong> <\/p>\n<h2>la loi d&rsquo;arriv\u00e9e, la loi des services, le nombre de serveurs.<\/h2>\n<p> <\/strong><\/p>\n<p>&#8211; Elles peuvent prendre en compte le cas o\u00f9 il existe plusieurs classes de clients mais la discipline de service doit \u00eatre d\u00e9finie, nous avons consid\u00e9r\u00e9 la discipline FIFO.<\/p>\n<h2>II\/ File M\/M\/1<\/h2>\n<p>M\/M\/1 = statistique du processus d&rsquo;arriv\u00e9e : markovien \/ statistique des lois de service :  markovien \/ 1 serveur<\/p>\n<p><strong>Les formules \u00e0 retenir:<\/strong><\/p>\n<p>\u00c9tat: nombre de clients, k, dans le syst\u00e8me<\/p>\n<p><math>\n$\\rho_<em>0<\/em> = \\left (1-<em>\\lambda \\over \\mu<\/em> \\right )=1-\\rho$\n<br \/>$\\rho_<em>0<\/em>$ : probabilit\u00e9 d&rsquo;avoir 0 clients dans la file d&rsquo;attente\n<\/math><\/p>\n<p>Taux de trafic, r (charge, activit\u00e9 du serveur):<\/p>\n<p><math>\n$\\rho = <em>\\lambda \\over \\mu<\/em>$\n<br \/>$\\rho$ : taux de traffic\n<br \/>$\\lambda$ : taux moyen d&rsquo;arriv\u00e9e des clients\n<br \/>$\\mu$ : taux moyen de traitement, d\u00e9bit du serveur, taux de service du serveur\n <\/math><\/p>\n<ul>\n<li> Condition de stabilit\u00e9:\n<ul>\n<li> activit\u00e9 du serveur <1\n<math>\n$\\rho = <em>\\lambda \\over \\mu<\/em> < 1$<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<ul>\n<li> $\\lambda<\\mu$\n\n<ul>\n<li> D\u00e9bit d&rsquo;entr\u00e9e < d\u00e9bit du serveur<\/li>\n<li> Temps moyen inter-arriv\u00e9e > temps de service moyen<\/li>\n<\/ul>\n<\/li>\n<li> Si serveur satur\u00e9 ($\\rho$&#8211;>1):\n<ul>\n<li> La distribution des intervalles de temps s\u00e9parant deux d\u00e9part cons\u00e9cutifs de la file satur\u00e9e tend vers la distribution des temps de service\n<\/math><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>Nombre moyen de clients dans le syst\u00e8me, N<br \/>\n<math>\n$\\bar N  = <em>\\rho \\over <em>1-\\rho<\/strong>$\n<br \/>$\\rho$ : taux de traffic\n<br \/>$\\bar N$ : Nombre de client dans le syst\u00e8me<\/p>\n<p>Nombre moyen de clients dans la file, E(v)<\/p>\n<p>$E(\\nu)  = <em>\\rho^<em>2<\/em> \\over <em>1-\\rho<\/strong>$\n<br \/>$\\rho$ : Taux de traffic\n<br \/>$E(\\nu)$ : Nombre moyen de client dans la file<\/p>\n<p>Temps moyen, T, pass\u00e9 par un client dans le syst\u00e8me<\/p>\n<p>$\\bar T  = <em>1 \\over \\mu<\/em><em>1 \\over <em>1-\\rho<\/strong>$<\/p>\n<p>$\\rho$ : taux de traffic\n<br \/>$\\bar T$ : temps pass\u00e9 par un client dans le syst\u00e8me\n<br \/>$\\mu$ : taux moyen de traitement, d\u00e9bit du serveur, taux de service\n<\/math><\/p>\n<h2>III\/ File M\/M\/S<\/h2>\n<p>M\/M\/S = statistique du processus d&rsquo;arriv\u00e9e : markovien \/ statistique des lois de service :  markovien \/ S serveurs<\/p>\n<p>Les formules \u00e0 retenir:<\/p>\n<p>Taux de trafic<br \/>\n<math>\n$\\rho = <em>\\lambda \\over <em>S\\mu<\/strong> < 1$\n\n\n$\\rho$ : taux de traffic\n<br \/>$\\lambda$ : taux moyen d&rsquo;arriv\u00e9e des clients\n<br \/>$\\mu$ : taux moyen de traitement, d\u00e9bit du serveur, taux de service du serveur\n<br \/>S : Nombre de serveurs<\/p>\n<p>Nombre moyen de guichets, g, occup\u00e9s:<\/p>\n<p>$\\bar g = <em>\\lambda \\over \\mu<\/em>$<\/p>\n<p>$\\bar g$ : Nombre de guichets occup\u00e9s\n<br \/>$\\lambda$ : taux moyen d&rsquo;arriv\u00e9e des clients\n<br \/>$\\mu$ : taux moyen de traitement, d\u00e9bit du serveur, taux de service du serveur<\/p>\n<p>Nombre moyen de clients, v , dans la file:\n<br \/>k>s, k: nombre de clients, s nombre de serveurs<\/p>\n<p>$\\nu= <em>1 \\over <em>S!S<\/strong> \\left (<em>\\lambda \\over \\mu<\/em> \\right) ^<em>S+1<\/em> <em>1 \\over <em>\\left(1- <em>\\lambda \\over <em>S \\mu<\/strong>\\right)^<em>2<\/strong><\/em> \\rho_<em>0<\/em>$<\/p>\n<p>$\\nu$ : nombre moyen de clients dans la file\n<br \/>$\\lambda$ : taux moyen d&rsquo;arriv\u00e9e des clients\n<br \/>$\\mu$ : taux moyen de traitement, d\u00e9bit du serveur, taux de service du serveur\n<br \/>$\\rho_<em>0<\/em>$ : probabilit\u00e9 qu&rsquo;il y ait 0 client dans le syst\u00e8me\n<br \/>S : nombre de serveurs<\/p>\n<p>Temps d&rsquo;attente moyen, tf , dans la file:<\/p>\n<p>$t_<em>f<\/em>= <em>1 \\over <em>S!<\/strong> \\left(<em>\\lambda \\over \\mu<\/em> \\right)^<em>S<\/em> <em>1 \\over <em>S\\mu<\/strong> <em>1 \\over <em>\\left (1- <em>\\lambda \\over <em>S\\mu<\/strong> \\right )^<em>2<\/strong><\/em>\\rho_<em>0<\/em>$<\/p>\n<p>$t_f$ : temps d&rsquo;attente moyen des clients dans la file\n<br \/>$\\lambda$ : taux moyen d&rsquo;arriv\u00e9e des clients\n<br \/>$\\mu$ : taux moyen de traitement, d\u00e9bit du serveur, taux de service du serveur\n<br \/>$\\rho_<em>0<\/em>$ : probabilit\u00e9 qu&rsquo;il y ait 0 client dans le syst\u00e8me\n<br \/>S : nombre de serveurs<\/p>\n<p>Nombre moyen de clients dans le syst\u00e8me<\/p>\n<p>$\\bar N= <em>\\lambda \\over \\mu<\/em> \\left ( \\mu \\bar t _f +1 \\right)$<\/p>\n<p>$\\bar N$ : Nombre de client dans le syst\u00e8me\n<br \/>$t_f$ : temps d&rsquo;attente moyen des clients dans la file\n<br \/>$\\lambda$ : taux moyen d&rsquo;arriv\u00e9e des clients\n<br \/>$\\mu$ : taux moyen de traitement<\/p>\n<p>Temps d&rsquo;attentes dans le syst\u00e8me<\/p>\n<p>$\\bar T= <em>\\bar N \\over \\lambda$<\/em><\/p>\n<p>$\\bar T$ : temps d&rsquo;attente dans le syst\u00e8me\n<br \/>$\\bar N$ : Nombre de client dans le syst\u00e8me\n<br \/>$\\lambda$ : taux moyen d&rsquo;arriv\u00e9e des clients<\/p>\n<p><\/math><\/p>\n","protected":false},"excerpt":{"rendered":"<p>I\/ D\u00e9finition Une file d&rsquo;attente est caract\u00e9ris\u00e9e par : &#8211; Un flot d&rsquo;arriv\u00e9es &#8211; Un m\u00e9canisme de service &#8211; Une file d&rsquo;attente &#8211; Une discipline de service Capacit\u00e9 de la file d&rsquo;attente: &#8211; nombre de places possibles : limit\u00e9 ou illimit\u00e9. &#8211; Si capacit\u00e9 limit\u00e9e: les clients suppl\u00e9mentaires sont perdus ou rejoignent une autre file [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":139,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-140","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-rcp101-recherche-operationnelle-et-aide-a-la-decision"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts\/140","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=140"}],"version-history":[{"count":0,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts\/140\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/media\/139"}],"wp:attachment":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=140"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=140"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=140"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}