Теория очереди

«Сначала приходите, сначала подают» перенаправляет здесь. Для альбома Kool Keith см. First Come, впервые обслуживается .

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

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

Теория очередей имеет свое начало в исследованиях Агнера Крарупа Эрлана , который создал модели для описания системы входящих вызовов в Компании по телефону Копенгагена. Эти идеи были основополагающими для области телесетлафической инженерии и с тех пор видели приложения в области телекоммуникаций , инженерии дорожного движения , вычислений , Управление проектами , и особенно промышленная инженерия , где они применяются в разработке фабрик, магазинов, офисов и больниц.

Написание

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

Описание

Теория очереди является одной из основных областей обучения в дисциплине управленческой науки . Благодаря науке управления предприятиями способны решать различные проблемы, используя различные научные и математические подходы. Анализ очереди является вероятностным анализом линий ожидания, и, следовательно, результаты, также называемые рабочими характеристиками, являются вероятностными, а не детерминированными. Вероятность того, что клиенты n находятся в системе очередей, среднее количество клиентов в системе очередей, среднее количество клиентов в линии ожидания, среднее время, потраченное клиентом в общей системе очереди, среднее время, потраченное на Заказчик в линии ожидания, и, наконец, вероятность того, что сервер занят или холостое время, - это все различные рабочие характеристики, которые вычисляют эти модели очереди. Общая цель анализа очереди состоит в том, чтобы вычислить эти характеристики для текущей системы, а затем проверить несколько альтернатив, которые могут привести к улучшению. Вычисление рабочих характеристик для текущей системы и сравнение значений с характеристиками альтернативных систем позволяет менеджерам видеть плюсы и минусы каждого потенциального опции. Эти системы помогают в окончательном процессе принятия решений, показывая способы увеличения сбережений, сокращения времени ожидания, повышения эффективности и т. Д. которые обсуждаются далее ниже. Эти модели могут быть дальше дифференцированы в зависимости от того, является ли время обслуживания постоянными или неопределенными, длина очереди конечна, вызовая популяция конечна и т. Д.

Одиночные узлы очередей

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

Черный ящик. Рабочие места прибывают в очередь и уйти и уйти.

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

Узел очереди с 3 серверами. Сервер А простаивает, и, следовательно, на его обработку дается прибытие. Сервер B в настоящее время занят и займет некоторое время, прежде чем он сможет завершить обслуживание своей работы. Сервер C только что завершил обслуживание работы и, следовательно, будет рядом с тем, чтобы получить прибывающую работу.

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

Процесс смерти рождения

См. Также: Анализ выживания

Поведение одной очереди (также называемой узлом очереди ) может быть описано процессом рождения и смерти , который описывает прибытие и отъезд от очереди, а также количество заданий, которые в настоящее время находятся в системе. Если k обозначает количество заданий в системе (либо обслуживаемое, либо ожидание, если в очереди имеет буфер заданий ожидания), то прибытие увеличивает K на 1, а отъезд уменьшается на 1.

Система переходит между значениями k по «рождению» и «смертью», которые происходят с показателями прибытия $\lambda _{i}$ и ставки отъезда $\mu _{i}$ для каждой работы $i$Полем Для очереди эти ставки, как правило, не варьируются в зависимости от количества рабочих мест в очереди, поэтому предполагается единая средняя скорость прибытия/вылета за единицу. В этом предположении этот процесс имеет скорость прибытия $\lambda ={\text{avg}}(\lambda _{1},\lambda _{2},\dots ,\lambda _{k})$ и уровень отъезда $\mu ={\text{avg}}(\mu _{1},\mu _{2},\dots ,\mu _{k})$.

Процесс рождения. Значения в кругах представляют собой состояние системы, которое развивается на основе скоростей прибытия λ _I и скорости вылета μ _i .

Очередь с 1 сервером, скоростью прибытия λ и скоростью вылета μ

Уравнения баланса

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

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

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

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

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

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

и

$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}$.

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

$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}}}$.

Состояние $\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$ ведет к

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

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

Участок Кендалла

Основная статья: нотация Кендалла

Одиночные узлы очереди обычно описываются с использованием обозначения Кендалла в форме A/ S/ C , где A описывает распределение продолжительности между каждым прибытием в очередь, S, распределение времени обслуживания для заданий и C количество серверов в узле. Для примера обозначения, очередь M/M/1 -это простая модель, где один сервер обслуживает задания, которые поступают в соответствии с процессом Пуассона (где промежуточные промежутки между получениями экспоненциально распределены ) и имеют экспоненциально распределенное время обслуживания (М. обозначает процесс Маркова ). В очереди M/G/1 G обозначает «общий» и указывает на произвольное распределение вероятностей для времени обслуживания.

Пример анализа очереди M/M/1

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

• $\lambda$: Коэффициент прибытия (взаимное ожидаемое время между каждым прибывающим клиентом, например, 10 клиентов в секунду)
• $\mu$: Взаимное среднее время обслуживания (ожидаемое количество последовательных завершений услуг в то же время, например, на 30 секунд)
• N : параметр, характеризующий количество клиентов в системе
• $P_{n}$: вероятность того, что есть n клиентов в системе в системе в стационарном состоянии

Далее, пусть $E_{n}$ представляют количество раз, когда система входит в состояние n , и $L_{n}$ Представляют количество раз, когда система оставляет состояние n . Затем $\left\vert E_{n}-L_{n}\right\vert \in \{0,1\}$ для всех n . То есть количество раз, когда система оставляет состояние, отличается не более 1, от того, сколько раз оно входит в это состояние, поскольку оно вернется в это состояние в какое -то время в будущем ( $E_{n}=L_{n}$) или нет ( $\left\vert E_{n}-L_{n}\right\vert =1$).

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

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

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

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

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

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

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

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

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

где $\rho ={\frac {\lambda }{\mu }}<1$.

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

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

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

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

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

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

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

Двухэтапная модель с одной коробкой распространена в эпидемиологии .

История

В 1909 году Агнер Краруп Эрланг , датский инженер, который работал на телефонной бирже Копенгагена, опубликовал первую статью о том, что теперь будет называться теорией очередей. Он смоделировал количество телефонных звонков, прибывающих на обмен путем пуассонского процесса , и решил очередь M/D/1 в 1917 году и M/D/ K в 1920 году. очереди модели В записи Кендалла:

• M означает «Марков» или «Без памяти» и означает, что прибытие происходит в соответствии с процессом Пуассона
• D означает «детерминированный» и означает, что задания, прибывающие в очередь, требуют фиксированного количества обслуживания
• K описывает количество серверов в узле очереди ( K = 1, 2, 3, ...)

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

Очередь m/g/1 была решена Феликсом Поллаческом в 1930 году, Решение позже в вероятностных терминах пересмотрит Александр Хинчин и теперь известный как формула Поллаца -Хинчина .

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

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

Геометрический метод матрицы и аналитические методы матрицы позволили рассмотреть очереди с распределенным распределением межреквенного и распределения времени обслуживания.

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

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

Такие проблемы, как показатели производительности для M/ G/ K, очереди остаются открытой проблемой.

Служба дисциплины

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

Сначала сначала

Сначала в первом (FIFO) пример очереди

Также называется первым приготовлением, первым сервисным (FCFS), В этом принципе говорится, что клиенты обслуживают по одному и что клиент, который ждал самый длинный, обслуживается первым.

Последнее, сначала

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

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

Сервисная емкость одинаково распределена между клиентами.

Приоритет

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

Самая короткая работа в первую очередь

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

Сначала упреждающая самая короткая работа

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

Кратчайшее оставшееся время обработки

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

Обслуживание

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

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

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

Поведение ожидания клиента

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

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

Стоимость очередей

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

Для сетей узлов M состояние системы может быть описано с помощью M -мерного вектора ( x ₁ , x ₂ , ..., x _M ), где X _I представляет количество клиентов в каждом узле.

Самые простые нетривиальные сети очередей называются тандемными очередями . Первыми значимыми результатами в этой области были Jackson Networks , для которого существует эффективное стационарное распределение в форме продукта и анализ средних значений (которые позволяют вычислять средние метрики, такие как пропускная способность и время пребывания). Если общее количество клиентов в сети остается постоянным, сеть называется закрытой сетью и, как было показано, также имеет стационарное распределение продукта по теореме Гордона -Новая . Этот результат был распространен на сеть BCMP , Там, где сеть с очень общим временем обслуживания, режимы и маршрутизации клиентов также демонстрирует стационарное распределение продукта. Нормализующая константа может быть рассчитана с помощью алгоритма Бузена , предложенного в 1973 году.

Сети клиентов также были исследованы, такие как Kelly Networks , где клиенты разных классов испытывают разные приоритетные уровни в разных узлах обслуживания. Другим типом сети является G-NetWorks , впервые предложенная Erol Gelenbe в 1993 году: Эти сети не предполагают экспоненциальных распределений времени, таких как Classic Jackson Network.

Алгоритмы маршрутизации

Смотрите также: Стохастическое планирование

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

Пределы среднего поля

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

Тяжелый трафик/диффузионные приближения

Основная статья: аппроксимация тяжелого трафика

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

Жидкие ограничения

Основная статья: предел жидкости

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

Заявки на очередь

Теория очереди находит широкое приложение в области информатики и информационных технологий. Например, в сети очереди являются неотъемлемой частью маршрутизаторов и коммутаторов, где пакеты стоят в очереди на передачу. Применяя принципы теории очередей, дизайнеры могут оптимизировать эти системы, обеспечивая адаптивную производительность и эффективное использование ресурсов. Помимо технологической сферы, теория очереди имеет отношение к повседневному опыту. Будь то ожидание в очереди в супермаркете или для общественного транспорта, понимание принципов теории очередей дает ценную информацию об оптимизации этих систем для повышения удовлетворенности пользователей. В какой -то момент все будут участвовать в аспекте очереди. То, что некоторые могут рассматривать как неудобства, может быть наиболее эффективным методом. Теория очередей, дисциплина, основанная на прикладной математике и информатике, является поле, посвященной изучению и анализу очередей или линии ожидания, и их последствия для разнообразных приложений. Эта теоретическая структура оказалась инструментальной в понимании и оптимизации эффективности систем, характеризующихся наличием очередей. Изучение очередей имеет важное значение в таких контекстах, как системы трафика, компьютерные сети, телекоммуникации и операции по обслуживанию. Теория очередей углубляется в различные основополагающие концепции, причем процесс прибытия и процесс обслуживания является центральным. Процесс прибытия описывает, каким образом объекты соединяются в очередь с течением времени, часто моделируемым с использованием стохастических процессов, таких как процессы Пуассона. Эффективность систем очереди измеряется с помощью ключевых показателей производительности. К ним относятся средняя длина очереди, среднее время ожидания и пропускную способность системы. Эти показатели дают представление о функциональности системы, руководящих решениях, направленных на повышение производительности и сокращение времени ожидания. Ссылки: Gross, D. & Harris, CM (1998). Основы теории очередей. Джон Уайли и сыновья. Kleinrock, L. (1976). Системы очередей: Том I - Теория. Уайли. Cooper, Bf, & Mitrani, I. (1985). Сети очереди: фундаментальный подход. Джон Уайли и сыновья

Смотрите также

• Фестивальная модель
• Эрланг Блок
• Управление линиями
• Сетевая моделирование
• Управление производством проекта
• Зона очереди
• Задержка в очереди
• Система управления очередью
• Правило стока
• Случайное раннее обнаружение
• Теория обновления
• Пропускная способность
• Планирование (вычисления)
• Пробка
• Модель генерации трафика
• Потоковая сеть

Дальнейшее чтение

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

Внешние ссылки

• Учебное пособие по теории очередей и калькуляторам теории очередей Тейкномо
• Курс теории очередей Virtamo
• Страница теории очередей Мирона Хлинки
• Линия: двигатель общего назначения для решения моделей очередей