Теория массового обслуживания

Сети очередей - это системы, в которых отдельные очереди соединены сетью маршрутизации. На этом изображении серверы представлены кружками, очереди - серией прямоугольников, а сеть маршрутизации - стрелками. При исследовании сетей с очередями обычно пытаются получить равновесное распределение сети, хотя во многих приложениях изучение переходного состояния является фундаментальным.

Теория массового обслуживания - это математическое исследование очередей или очередей . ^[1] Модель организации очередей построена так, чтобы можно было спрогнозировать длину очереди и время ожидания. ^[1] Теория массового обслуживания обычно считается разделом исследования операций, потому что результаты часто используются при принятии бизнес-решений о ресурсах, необходимых для предоставления услуги.

Теория массового обслуживания берет свое начало в исследованиях Агнера Крарупа Эрланга, когда он создал модели для описания системы датской компании Copenhagen Telephone Exchange. ^[1] С тех пор идеи нашли применение, включая телекоммуникации , транспортную инженерию , вычисления ^[2] и, особенно, в промышленном строительстве , при проектировании заводов, магазинов, офисов и больниц, а также в управлении проектами. ^{[3] [4]}

Правописание [ править ]

Написание «в очереди» над «очередью» обычно встречается в области академических исследований. Фактически, одним из ведущих журналов этой профессии является система массового обслуживания .

Одиночные узлы очередей [ править ]

Очередь или узел очередей можно рассматривать как почти черный ящик . Задания или «клиенты» прибывают в очередь, возможно, ждут некоторое время, требуют некоторого времени для обработки, а затем удаляются из очереди.

Черный ящик. Задания приходят в очередь и уходят из нее.

Однако узел очереди - это не совсем чистый черный ящик, поскольку требуется некоторая информация о внутренней части узла очереди. Очередь имеет один или несколько «серверов», каждый из которых может быть связан с поступающим заданием до тех пор, пока он не уйдет, после чего этот сервер будет свободен для соединения с другим поступающим заданием.

Узел очередей с 3 серверами. Сервер a простаивает, поэтому ему передается поступление на обработку. Сервер b в настоящее время занят, и ему потребуется некоторое время, прежде чем он сможет завершить выполнение своей работы. Сервер c только что завершил обслуживание задания и, следовательно, будет следующим, чтобы получить поступившее задание.

Часто используется аналогия с кассиром в супермаркете. Существуют и другие модели, но эта часто встречается в литературе. Клиенты прибывают, обрабатываются кассиром и уходят. Каждый кассир обрабатывает одного клиента за раз, и, следовательно, это узел очереди только с одним сервером. Настройка, при которой покупатель немедленно уходит, если кассир занят, когда приходит покупатель, называется очередью без буфера (или без «зоны ожидания», или аналогичных терминов). Настройка с зоной ожидания для n заявок называется очередью с буфером размера n .

Процесс рождения-смерти [ править ]

Поведение отдельной очереди (также называемой «узлом очереди») можно описать процессом рождения-смерти , который описывает поступления и выбывания из очереди, а также количество заданий (также называемых «клиентами» или «запросами». "или любое количество других вещей, в зависимости от поля), которое в настоящее время находится в системе. Прибытие увеличивает количество работ на 1, а отъезд (работа, завершающая свое обслуживание) уменьшает k на 1.

Уравнения баланса [ править ]

Уравнения установившегося состояния для процесса рождения и смерти, известные как уравнения баланса , следующие. Здесь обозначает вероятность устойчивого состояния нахождения в состоянии n .${\ displaystyle P_ {n}}$

${\ displaystyle \ mu _ {1} P_ {1} = \ lambda _ {0} P_ {0}}$

${\ displaystyle \ lambda _ {0} P_ {0} + \ mu _ {2} P_ {2} = (\ lambda _ {1} + \ mu _ {1}) P_ {1}}$

${\ displaystyle \ lambda _ {n-1} P_ {n-1} + \ mu _ {n + 1} P_ {n + 1} = (\ lambda _ {n} + \ mu _ {n}) P_ { n}}$

Первые два уравнения подразумевают

${\ displaystyle P_ {1} = {\ frac {\ lambda _ {0}} {\ mu _ {1}}} P_ {0}}$

и

${\ displaystyle P_ {2} = {\ frac {\ lambda _ {1}} {\ mu _ {2}}} P_ {1} + {\ frac {1} {\ mu _ {2}}} (\ mu _ {1} P_ {1} - \ lambda _ {0} P_ {0}) = {\ frac {\ lambda _ {1}} {\ mu _ {2}}} P_ {1} = {\ frac {\ lambda _ {1} \ lambda _ {0}} {\ mu _ {2} \ mu _ {1}}} P_ {0}.}$

По математической индукции

${\displaystyle P_{n}={\frac {\lambda _{n-1}\lambda _{n-2}\cdots \lambda _{0}}{\mu _{n}\mu _{n-1}\cdots \mu _{1}}}P_{0}=P_{0}\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}.}$

Состояние приводит к:${\displaystyle \sum _{n=0}^{\infty }P_{n}=P_{0}+P_{0}\sum _{n=1}^{\infty }\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}=1}$

${\displaystyle P_{0}={\frac {1}{1+\sum _{n=1}^{\infty }\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}}},}$

которое вместе с уравнением для полностью описывает требуемые вероятности установившегося состояния.${\displaystyle P_{n}}$ ${\displaystyle (n\geq 1)}$

Обозначения Кендалла [ править ]

Одиночные узлы очередей обычно описываются с использованием нотации Кендалла в форме A / S / c, где A описывает распределение продолжительности между каждым поступлением в очередь, S распределение времени обслуживания для заданий и c количество серверов в узле. ^{[5] [6]} В качестве примера обозначения очередь M / M / 1 представляет собой простую модель, в которой один сервер обслуживает задания, поступающие в соответствии с пуассоновским процессом (где длительность между поступлениями распределяется экспоненциально ) и экспоненциально время распределенного обслуживания (M обозначает марковский процесс ). ВОчередь M / G / 1 , G означает «общий» и указывает произвольное распределение вероятностей для времени обслуживания.

Пример анализа очереди M / M / 1 [ править ]

Рассмотрим очередь с одним сервером и следующими характеристиками:

• λ : частота прибытия (ожидаемое время между прибытием каждого клиента, например, 30 секунд);
• μ : величина, обратная среднему времени обслуживания (ожидаемое количество последовательных завершений обслуживания за одно и то же время, например, за 30 секунд);
• n : параметр, характеризующий количество клиентов в системе;
• P _n : вероятность наличия n клиентов в системе в устойчивом состоянии.

Далее, пусть E _n представляет количество раз, когда система входит в состояние n , а L _n представляет количество раз, когда система выходит из состояния n . Тогда для всех n , | E _n - L _n | ∈ {0, 1}. То есть количество раз, когда система покидает состояние, отличается не более чем на 1 от количества раз, когда она входит в это состояние, поскольку она либо вернется в это состояние в какой-то момент в будущем ( E _n = L _n ), либо нет. (| E _n - L _n | = 1).

Когда система переходит в установившееся состояние, скорость прибытия должна быть равна скорости отправления.

Таким образом, уравнения баланса

${\displaystyle \mu P_{1}=\lambda P_{0}}$

${\displaystyle \lambda P_{0}+\mu P_{2}=(\lambda +\mu )P_{1}}$

${\displaystyle \lambda P_{n-1}+\mu P_{n+1}=(\lambda +\mu )P_{n}}$

подразумевать

${\displaystyle P_{n}={\frac {\lambda }{\mu }}P_{n-1},\ n=1,2,\ldots }$

Тот факт, что приводит к формуле геометрического распределения${\displaystyle P_{0}+P_{1}+\cdots =1}$

${\displaystyle P_{n}=(1-\rho )\rho ^{n}}$

куда ${\displaystyle \rho ={\frac {\lambda }{\mu }}<1.}$

Простая очередь с двумя уравнениями [ править ]

Обычная базовая система очередей приписывается Erlang и является модификацией закона Литтла . Учитывая частоту поступления λ , частоту отсева σ и частоту выбытия μ , длина очереди L определяется как:

${\displaystyle L={\frac {\lambda -\sigma }{\mu }}.}$

Предполагая экспоненциальное распределение ставок, время ожидания W можно определить как долю обслуженных прибывших. Это равно экспоненциальной выживаемости тех, кто не бросает учебу в течение периода ожидания, что дает:

${\displaystyle {\frac {\mu }{\lambda }}=e^{-W{\mu }}}$

Второе уравнение обычно переписывается как:

${\displaystyle W={\frac {1}{\mu }}\mathrm {ln} {\frac {\lambda }{\mu }}}$

Двухэтапная модель одного блока широко распространена в эпидемиологии. ^[7]

Обзор развития теории [ править ]

В 1909 году датский инженер Агнер Краруп Эрланг , работавший в Копенгагенской телефонной станции, опубликовал первую статью о том, что теперь будет называться теорией очередей. ^{[8] [9] [10]} Он смоделировал количество телефонных звонков, поступающих на коммутатор, с помощью процесса Пуассона и решил очередь M / D / 1 в 1917 году и модель организации очереди M / D / k в 1920 году. ^[11] In Обозначения Кендалла:

• M означает марковский или без памяти и означает, что прибытие происходит в соответствии с пуассоновским процессом;
• D означает детерминированный и означает задания, поступающие в очередь, которые требуют фиксированного объема обслуживания;
• k описывает количество серверов в узле очередей ( k = 1, 2, ...).

Если на узле больше заданий, чем серверов, то задания будут стоять в очереди и ждать обслуживания.

Очередь M / G / 1 была решена Феликсом Поллачеком в 1930 году ^[12], решение, позднее преобразованное в вероятностные термины Александром Хинчиным и теперь известное как формула Поллачека – Хинчина . ^{[11] [13]}

После 1940-х годов теория массового обслуживания стала предметом научных исследований математиков. ^[13] В 1953 году Дэвид Джордж Кендалл решил проблему очереди GI / M / k ^[14] и ввел современную нотацию для очередей, теперь известную как нотация Кендалла . В 1957 году Поллачек изучил GI / G / 1 с помощью интегрального уравнения . ^[15] Джон Кингман дал формулу для среднего времени ожидания в очереди G / G / 1 : формула Кингмана . ^[16]

Леонард Клейнрок работал над применением теории очередей к коммутации сообщений (в начале 1960-х) и коммутации пакетов (в начале 1970-х). Первым его вкладом в эту область была докторская диссертация в Массачусетском технологическом институте в 1962 году, опубликованная в виде книги в 1964 году в области коммутации сообщений. Его теоретическая работа, опубликованная в начале 1970-х годов, обосновала использование коммутации пакетов в ARPANET , предшественнике Интернета.

В матричном геометрическом методе и Matrix аналитические методы позволили очередь с фазой типа распределена между поступлениями и распределениями времени обслуживания , которые необходимо учитывать. ^[17]

Системы со связанными орбитами являются важной частью теории массового обслуживания в приложениях к беспроводным сетям и обработке сигналов. ^[18]

Такие проблемы, как показатели производительности для очереди M / G / k, остаются открытой проблемой. ^{[11] [13]}

Дисциплины обслуживания [ править ]

На узлах очередей могут использоваться различные политики планирования:

Первым пришел-первым вышел

Этот принцип, также называемый « первым пришел - первым обслужен» (FCFS) ^[19], гласит, что клиенты обслуживаются по одному, а клиент, который ждал дольше всех, обслуживается первым. ^[20]

Последний пришел - первый ушел

Этот принцип также обслуживает клиентов по одному, но клиент с самым коротким временем ожидания будет обслуживаться первым. ^[20] Также известен как стек .

Совместное использование процессора

Объем услуг распределяется поровну между клиентами. ^[20]

Приоритет

В первую очередь обслуживаются клиенты с высоким приоритетом. ^[20] Приоритетные очереди могут быть двух типов: без вытеснения (когда обслуживаемое задание не может быть прервано) и с вытеснением (где обслуживаемое задание может быть прервано более приоритетным заданием). Никакая работа не теряется ни в одной из моделей. ^[21]

Сначала самая короткая работа

Следующая работа, которую нужно обслужить, - это работа с наименьшим размером.

Первоочередное кратчайшее задание

Следующее задание, которое нужно обслужить, - это задание с исходным наименьшим размером ^[22]

Наименьшее оставшееся время обработки

Следующее задание, которое нужно обслужить, - это задание с наименьшими оставшимися требованиями к обработке. ^[23]

Сервисный центр

• Единый сервер: клиенты выстраиваются в очередь, и есть только один сервер
• Несколько параллельных серверов - Единая очередь: клиенты выстраиваются в очередь, есть несколько серверов.
• Несколько серверов - несколько очередей: есть много счетчиков, и клиенты могут решать, куда идти в очередь.

Ненадежный сервер

Сбои сервера происходят в соответствии со случайным процессом (обычно Пуассоном), и за ними следуют периоды настройки, в течение которых сервер недоступен. Прерванный клиент остается в зоне обслуживания до тех пор, пока сервер не будет отремонтирован. ^[24]

Ожидание клиента

• Отказ: клиенты решают не вставать в очередь, если она слишком длинная
• Жульничество: клиенты переключаются между очередями, если думают, что благодаря этому их обслужат быстрее.
• Возврат: клиенты покидают очередь, если они слишком долго ждали обслуживания

Прибывающие не обслуживаемые клиенты (либо из-за отсутствия буфера в очереди, либо из-за отказа или отказа со стороны клиента) также известны как отсевы, а средний коэффициент отсева является важным параметром, описывающим очередь.

Сети очередей [ править ]

Сети очередей - это системы, в которых несколько очередей связаны так называемой маршрутизацией клиентов. Когда клиент обслуживается на одном узле, он может присоединиться к другому узлу и встать в очередь на обслуживание или покинуть сеть.

Для сетей из m узлов состояние системы может быть описано m -мерным вектором ( x ₁ , x ₂ , ..., x _m ), где x _i представляет количество клиентов в каждом узле.

Простейшая нетривиальная сеть очередей называется тандемными очередями . ^[25] Первые значительные результаты в этой области были сети Джексона , ^{[26] [27]} , для которых эффективной стационарного распределения продукта формы существует , и анализ среднего значения ^[28] , которая позволяет средние показатели , такие как пропускная способности и временные пребывание раз , чтобы быть вычислено. ^[29] Если общее количество клиентов в сети остается постоянным, сеть называется закрытой, и в теореме Гордона – Ньюэлла было показано, что она имеет стационарное распределение в форме продукта . ^[30] Этот результат был распространен наСеть BCMP ^[31], где показано, что сеть с очень общим временем обслуживания, режимами и маршрутизацией клиентов также демонстрирует стационарное распределение в форме продукта. Константа нормализующее можно вычислить с помощью алгоритма Buzen в , предложенный в 1973 г. ^[32]

Также были исследованы сети клиентов , сети Келли, в которых клиенты разных классов имеют разные уровни приоритета на разных узлах обслуживания. ^[33] Другой тип сети - G-сети, впервые предложенные Эролом Геленбе в 1993 году: ^[34] эти сети не предполагают экспоненциального распределения времени, как классическая сеть Джексона.

Алгоритмы маршрутизации [ править ]

В сетях с дискретным временем, где существует ограничение на то, какие узлы обслуживания могут быть активными в любое время, алгоритм планирования с максимальным весом выбирает политику обслуживания, чтобы обеспечить оптимальную пропускную способность в случае, если каждое задание посещает только одного человека ^[19] узел обслуживания. . В более общем случае, когда задания могут посещать более одного узла, маршрутизация противодавления обеспечивает оптимальную пропускную способность. Сети планировщик должен выбрать очереди алгоритма , который влияет на характеристики сети большего размера ^{[ править ]} . См. Также Стохастическое планирование для получения дополнительной информации о планировании систем массового обслуживания.

Пределы среднего поля [ править ]

Модели среднего поля рассматривают предельное поведение эмпирической меры (доля очередей в разных состояниях), когда количество очередей ( m выше) стремится к бесконечности. Влияние других очередей на любую данную очередь в сети аппроксимируется дифференциальным уравнением. Детерминированная модель сходится к тому же стационарному распределению, что и исходная модель. ^[35]

Приближение интенсивного движения / диффузии [ править ]

В системе с высоким уровнем занятости (использование вблизи 1) тяжелое приближение трафика может быть использовано для аппроксимации процесса длины очередей с помощью отраженного броуновского движения , ^[36] процесса Орнштейна-Уленбека , или более общего процесса диффузии . ^[37] Число измерений броуновского процесса равно количеству узлов очереди, при этом распространение ограничено неотрицательным ортантом .

Пределы жидкости [ править ]

Жидкие модели являются непрерывными детерминированными аналогами сетей массового обслуживания, полученными путем принятия предела, когда процесс масштабируется во времени и пространстве, что позволяет использовать неоднородные объекты. Эта масштабированная траектория сходится к детерминированному уравнению, которое позволяет доказать устойчивость системы. Известно, что сеть массового обслуживания может быть стабильной, но иметь нестабильный предел текучей среды. ^[38]

См. Также [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Гросс, Дональд; Карл М. Харрис (1998). Основы теории массового обслуживания . Вайли. ISBN 978-0-471-32812-4. В сети
• Цукерман, Моше. Введение в теорию массового обслуживания и стохастические модели телетрафика (PDF) .
• Дейтель, Харви М. (1984) [1982]. Введение в операционные системы (пересмотренное первое издание). Эддисон-Уэсли. п. 673 . ISBN 978-0-201-14502-1. глава 15, стр. 380–412
• Ньюэлл, Гордрон Ф. (1 июня 1971 г.). Приложения теории массового обслуживания . Чепмен и Холл.
• Леонард Клейнрок, Информационный поток в больших коммуникационных сетях , (Массачусетский технологический институт, Кембридж, 31 мая 1961 г.). Тезис
• Леонард Клейнрок. Информационный поток в больших коммуникационных сетях (Ежеквартальный отчет RLE, июль 1961 г.)
• Леонард Клейнрок. Сети связи: стохастический поток сообщений и задержка (Макгроу-Хилл, Нью-Йорк, 1964)
• Клейнрок, Леонард (2 января 1975 г.). Системы массового обслуживания: Том I - Теория . Нью-Йорк: Wiley Interscience. С.  417 . ISBN 978-0471491101.
• Клейнрок, Леонард (22 апреля 1976 г.). Системы массового обслуживания: Том II - Компьютерные приложения . Нью-Йорк: Wiley Interscience. С.  576 . ISBN 978-0471491118.
• Lazowska, Edward D .; Джон Захоржан; Г. Скотт Грэм; Кеннет С. Севчик (1984). Количественная производительность системы: анализ компьютерной системы с использованием моделей сетей массового обслуживания . ISBN компании Prentice-Hall, Inc. 978-0-13-746975-8.

Внешние ссылки [ править ]

Посмотрите информацию об очередях  или очередях в Викисловаре, бесплатном словаре.

Использование внешних ссылок в этой статье может не соответствовать политикам или рекомендациям Википедии . Пожалуйста, улучшите эту статью , удалив лишние или неприемлемые внешние ссылки и преобразовав полезные ссылки, где это уместно, в сноски . ( Май 2017 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

• Калькулятор теории массового обслуживания
• Учебник и калькуляторы Teknomo по теории массового обслуживания
• Имитация эвакуации при пожаре в офисе на YouTube
• Курс Virtamo по теории массового обслуживания
• Страница теории массового обслуживания Майрона Хлынки
• Основы теории массового обслуживания
• Бесплатный онлайн-инструмент для решения некоторых классических систем массового обслуживания
• JMT: графическая среда с открытым исходным кодом для теории массового обслуживания
• LINE: универсальный движок для решения моделей очередей
• Что вы больше всего ненавидите в ожидании в очереди: (Дело не в продолжительности ожидания.) , Сет Стивенсон, Slate , 2012 - популярное введение