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

«Первым пришел — первым обслужен» перенаправляется сюда. Чтобы узнать об альбоме Kool Keith, см. First Come, First Served .

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

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

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

Написание

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

Описание

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

Одиночные узлы массового обслуживания

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

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

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

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

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

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

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

Поведение отдельной очереди (также называемой узлом очередей ) можно описать процессом рождения-смерти , который описывает приходы и уходы из очереди, а также количество заданий, находящихся в настоящее время в системе. Если k обозначает количество заданий в системе (либо обслуживаемых, либо ожидающих, если в очереди есть буфер ожидающих заданий), то прибытие увеличивает k на 1, а отправление уменьшает k на 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 обозначает марковский процесс ). В очереди 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\}$ для всех н . То есть количество раз, когда система покидает состояние, отличается не более чем на 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$.

Простая очередь из двух уравнений

Общая базовая система массового обслуживания принадлежит Эрлангу и является модификацией закона Литтла . Учитывая скорость поступления λ , частоту отсева σ и скорость отправления µ , длина очереди 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-х годов, легла в основу использования коммутации пакетов в ARPANET , предшественнике Интернета.

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

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

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

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

Дисциплины обслуживания

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

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

Пример очереди «первым пришел – первым обслужен» (FIFO)

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

Последний пришёл, первым ушёл

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

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

Возможности обслуживания распределяются поровну между клиентами.

Приоритет

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

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

Следующим будет выполнено задание наименьшего размера.

Вытесняющее самое короткое задание сначала

Следующим будет выполнено задание с наименьшим исходным размером.

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

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

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

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

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

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

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

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

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

Сети массового обслуживания

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

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

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

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

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

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

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

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

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

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

Основная статья: Приближение интенсивного движения

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

Пределы жидкости

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

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

Приложения для организации очередей

Теория массового обслуживания находит широкое применение в информатике и информационных технологиях. Например, в сетях очереди являются неотъемлемой частью маршрутизаторов и коммутаторов, где пакеты выстраиваются в очередь для передачи. Применяя принципы теории массового обслуживания, проектировщики могут оптимизировать эти системы, обеспечивая высокую производительность и эффективное использование ресурсов. Помимо технологической сферы, теория массового обслуживания актуальна для повседневной жизни. Независимо от того, стоите ли вы в очереди в супермаркете или в общественном транспорте, понимание принципов теории массового обслуживания дает ценную информацию по оптимизации этих систем для повышения удовлетворенности пользователей. В какой-то момент каждый будет вовлечен в какой-то аспект организации очередей. То, что некоторые могут посчитать неудобством, возможно, является наиболее эффективным методом. Теория массового обслуживания, дисциплина, основанная на прикладной математике и информатике, представляет собой область, посвященную изучению и анализу очередей или очередей ожидания, а также их последствий для широкого спектра приложений. Эта теоретическая основа оказалась полезной для понимания и оптимизации эффективности систем, характеризующихся наличием очередей. Изучение очередей имеет важное значение в таких контекстах, как системы дорожного движения, компьютерные сети, телекоммуникации и сервисные операции. Теория массового обслуживания углубляется в различные основополагающие концепции, центральными из которых являются процесс прибытия и процесс обслуживания. Процесс прибытия описывает способ, которым объекты присоединяются к очереди с течением времени, часто моделируемый с использованием стохастических процессов, таких как процессы Пуассона. Эффективность систем массового обслуживания оценивается с помощью ключевых показателей производительности. К ним относятся средняя длина очереди, среднее время ожидания и пропускная способность системы. Эти показатели дают представление о функциональности системы и помогают принимать решения, направленные на повышение производительности и сокращение времени ожидания. Ссылки: Гросс Д. и Харрис К.М. (1998). Основы теории массового обслуживания. Джон Уайли и сыновья. Кляйнрок, Л. (1976). Системы массового обслуживания: Том I - Теория. Уайли. Купер, Б.Ф., и Митрани, И. (1985). Сети массового обслуживания: фундаментальный подход. Джон Уайли и сыновья

См. также

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

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

• Гросс, Дональд; Карл М. Харрис (1998). Основы теории массового обслуживания . Уайли. ISBN  978-0-471-32812-4 . Онлайн
• Цукерман, Моше (2013). Введение в теорию массового обслуживания и стохастические модели телетрафика (PDF) . arXiv : 1307.2968 .
• Дейтел, Харви М. (1984) [1982]. Введение в операционные системы (пересмотренное первое издание). Аддисон-Уэсли. п. 673 . ISBN  978-0-201-14502-1 . гл.15, стр. 380–412.
• Геленбе, Эрол; Иси Митрани (2010). Анализ и синтез компьютерных систем . Всемирное научное 2-е издание. ISBN  978-1-908978-42-4 .
• Ньюэлл, Гордрон Ф. (1 июня 1971 г.). Приложения теории массового обслуживания . Чепмен и Холл.
• Леонард Кляйнрок, Информационный поток в больших коммуникационных сетях , (MIT, Кембридж, 31 мая 1961 г.) Предложение на соискание степени доктора философии. Диссертация
• Леонард Клейнрок. Информационный поток в больших сетях связи (ежеквартальный отчет RLE, июль 1961 г.)
• Леонард Клейнрок. Сети связи: стохастический поток сообщений и задержка (МакГроу-Хилл, Нью-Йорк, 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 .
• Лазовска, Эдвард Д.; Джон Захоржан; Дж. Скотт Грэм; Кеннет С. Севчик (1984). Количественная производительность системы: анализ компьютерной системы с использованием моделей сетей массового обслуживания . Прентис-Холл, Inc. ISBN  978-0-13-746975-8 .
• Джон Кляйнберг; Ева Тардос (30 июня 2013 г.). Алгоритм проектирования . Пирсон. ISBN  978-1-292-02394-6 .

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

• Учебное пособие по теории массового обслуживания и калькуляторы Teknomo
• Курс теории массового обслуживания Виртамо
• Страница теории массового обслуживания Мирона Глинки
• LINE: механизм общего назначения для решения моделей очередей.