{"id":6685,"date":"2018-09-19T15:50:18","date_gmt":"2018-09-19T14:50:18","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6685"},"modified":"2022-12-03T23:02:01","modified_gmt":"2022-12-03T22:02:01","slug":"les-files-dattente","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/markov-process\/queues\/","title":{"rendered":"Queues"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6685\" class=\"elementor elementor-6685\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a711824 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a711824\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-4ef8aa8\" data-id=\"4ef8aa8\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a0eddce elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a0eddce\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/markov-process\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Markov process<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-894cc10\" data-id=\"894cc10\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-9af7973 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"9af7973\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-dfe60be\" data-id=\"dfe60be\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-8e55275 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"8e55275\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Th%C3%A9orie_des_files_d%27attente\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c1f1c43 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c1f1c43\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-f5bb33f\" data-id=\"f5bb33f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-145415d elementor-widget elementor-widget-progress\" data-id=\"145415d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"progress.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t<span class=\"elementor-title\" id=\"elementor-progress-bar-145415d\">\n\t\t\t\tDifficulty\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-145415d\" class=\"elementor-progress-wrapper\" role=\"progressbar\" aria-valuemin=\"0\" aria-valuemax=\"100\" aria-valuenow=\"25\" aria-valuetext=\"25% (Facile)\">\n\t\t\t<div class=\"elementor-progress-bar\" data-max=\"25\">\n\t\t\t\t<span class=\"elementor-progress-text\">Easy<\/span>\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-progress-percentage\">25%<\/span>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-37ac9f69 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"37ac9f69\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-5c36b81a\" data-id=\"5c36b81a\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-6bd7fac elementor-widget elementor-widget-text-editor\" data-id=\"6bd7fac\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_85 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/markov-process\/queues\/#Files-dattente\" >Waiting lines<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/markov-process\/queues\/#Notation-de-Kendall\" >Kendall&#039;s notation<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/markov-process\/queues\/#Mesures-de-performance\" >Performance measures<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Files-dattente\"><\/span>Waiting lines<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p class=\"wp-block-paragraph\">A queue (or queues) can be described as follows: clients (men, tasks, messages, etc.) arrive for a service, wait in a queue if they cannot be taken care of immediately , and leave after having had the service.<\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-6688\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/proba52.png\" alt=\"Waiting line\" width=\"458\" height=\"146\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/proba52.png 458w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/proba52-300x96.png 300w\" sizes=\"(max-width: 458px) 100vw, 458px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p class=\"wp-block-paragraph\">The model, originally created by Erlang for the 1909 telephone system, is used to model traffic management, planning and sizing of infrastructure and machining.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Notation-de-Kendall\"><\/span>Kendall&#039;s notation<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p class=\"wp-block-paragraph\">A queue has 6 criteria noted by: T \/ X \/ C \/ K \/ P \/ Z<\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>T: the probability distribution of the inter-arrival time. Customers can leave if they arrive when the line is full. T can take the following values\n<ul>\n<li>M for Markovian process \/ exponential law<\/li>\n<li>G for the general law<\/li>\n<li>D deterministic law<\/li>\n<li>E (k) for Erlang&#039;s law<\/li>\n<li>etc.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>X: the probability distribution of the service time. A client is taken directly by a free server, once the service is completed the client leaves. The distribution is represented by the same symbols as in T.<\/li>\n<li>C: the number of servers. In single queues, the servers all have the same uptime probability distribution.<\/li>\n<\/ul>\n<p><\/p>\n<figure class=\"wp-block-image\"><img decoding=\"async\" class=\"alignnone wp-image-6689\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/proba53.png\" alt=\"Waiting line\" width=\"248\" height=\"159\" title=\"\"><\/figure>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>K: the capacity of the queue. If the queue is a finite number, the customer is lost when the queue is full. Servers count towards the capacity of the queue (1 per server).<\/li>\n<\/ul>\n<p><\/p>\n<figure class=\"wp-block-image\"><img decoding=\"async\" class=\"alignnone wp-image-6690\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/proba54.png\" alt=\"Waiting line\" width=\"210\" height=\"136\" title=\"\"><\/figure>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>P: the size of the population. The size of the population is finite or infinite. In the case of a finite population, the customer arrival rate is a function of the number of customers in the system.<\/li>\n<li>Z: discipline of service\n<ul>\n<li>FCFS \/ FIFO (first come first served \/ first in first out): first come first served<\/li>\n<li>LCFC \/ FILO (last come first served \/ first in last out): last come first served \/ first come last served<\/li>\n<li>RANDOM: random customer service in the waiting list<\/li>\n<li>HL (hold in line): if an &quot;important&quot; customer arrives, he takes the first place in the queue (depending on the &quot;importance&quot; of the first customers)<\/li>\n<li>PR (preemption): if an &quot;important&quot; customer arrives, he is served directly and the &quot;less important&quot; customer leaves the service to go in the queue<\/li>\n<li>PS (processor sharing): all customers are served at the same time with a speed inversely proportional to the number of customers<\/li>\n<li>etc.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p><\/p>\n<p class=\"wp-block-paragraph\">A queue can be traversed by different classes of customers characterized by:<\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>Different arrival processes<\/li>\n<li>Different service times<\/li>\n<li>Different costs<\/li>\n<li>a <a href=\"https:\/\/complex-systems-ai.com\/en\/planning-problem\/\">scheduling<\/a> in the queue according to their class<\/li>\n<\/ul>\n<p><\/p>\n<p class=\"wp-block-paragraph\">We will use the T \/ X \/ C notation when the queue is of infinite capacity, the size of the population is infinite and the service is FIFO discipline. This is equivalent to writing T \/ X \/ C \/ \u221e \/ \u221e \/ FIFO.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Mesures-de-performance\"><\/span>Performance measures<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p class=\"wp-block-paragraph\">The purpose of studying a queue is to calculate or estimate the performance of a system. This calculation is done in stationary mode in order to calculate: the speed X, the number of clients Q, the rate of use of the server U, the response time R. In general, the expectations of these parameters are calculated.<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">In the context of single queues, the system is <a href=\"https:\/\/complex-systems-ai.com\/en\/markov-process\/invariant-law-and-asymptotic-behavior\/\">ergodic<\/a>. We then seek to calculate the stability of the system. Let&#039;s take the following:<\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>A (T): number of arrivals in the system between 0 and T<\/li>\n<li>D (T): number of system departures between 0 and T<\/li>\n<li>Xe (T) = A (T) \/ T: average inlet flow rate between 0 and T<\/li>\n<li>Xs (T) = D (T) \/ T: average outlet flow rate between 0 and T<\/li>\n<li>Q (T): average number of customers between 0 and T<\/li>\n<li>R<sub>k<\/sub>: residence time of the kth customer arrived<\/li>\n<li><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6692 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/09\/proba55.png\" alt=\"Waiting line\" width=\"124\" height=\"51\" title=\"\">: average residence time between 0 and T<\/li>\n<\/ul>\n<p><\/p>\n<p class=\"wp-block-paragraph\">a queue is stable if and only if the limit when T approaches infinity of the average input rate is equal to the limit when T approaches infinity of the average output rate. In other words, when the limit as T approaches infinity of D (T) \/ A (T) = 1. In a stable queue, the number of customers remains finite.<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Let Q be the average number of customers, R the average response time and X the average throughput, Little&#039;s law guaranteed in <a href=\"https:\/\/complex-systems-ai.com\/en\/markov-process\/steady-state\/\">steady state<\/a> for a stable system that Q=RX (one does not then take account of T any more).<\/p>\n<p><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Markov Process Wiki Home Page Difficulty Easy 25% Queues A queue (or queues) can be described as follows: customers\u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":5007,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-6685","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6685","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=6685"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6685\/revisions"}],"predecessor-version":[{"id":18681,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6685\/revisions\/18681"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/5007"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=6685"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}