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

В академической литературе чаще встречается написание queueing, а не queuing. Например, один из ведущих журналов области называется Queueing Systems.

Теория массового обслуживания является одной из ключевых областей науки об управлении. Эта дисциплина позволяет организациям решать широкий круг задач, применяя научные и математические методы. Анализ систем обслуживания опирается на вероятностный подход, а не на детерминированный, что отражается на характеристиках работы системы (либо так называемых эксплуатационных характеристиках)^[5]. К таким характеристикам относятся вероятность наличия n клиентов в системе, среднее число клиентов в системе, среднее время ожидания в очереди, среднее время пребывания в системе и др^[5] Главная цель анализа — вычислить эти показатели для текущей системы и оценить, как они изменятся при различных модификациях. Это помогает принимать решения, повышающие эффективность и снижающие издержки. Основные модели — это системы с одним и несколькими обслуживающими устройствами (сервером или кассами), которые могут учитывать постоянство/случайность времени обслуживания, ограниченность очереди, конечность потока вызовов и другие параметры.^[5]

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

Очередь как «чёрный ящик»: задачи поступают и покидают систему.

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

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

Пример: касса в магазине. Покупатели приходят, проходят обслуживание (оплату), уходят. Если касса занята и нет зоны ожидания, клиент уходит (нет буфера); если очередь может включать до n клиентов — очередь с буфером размера n.

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

Переходы между состояниями происходят с интенситетами поступления ${\displaystyle \lambda _{i}}$ и обслуживания ${\displaystyle \mu _{i}}$. В большинстве моделей интенсивности считать постоянными, то есть для всей системы существует среднее ${\displaystyle \lambda }$ (поступление) и ${\displaystyle \mu }$ (обслуживание).

Процесс рождения–смерти. В кружках — состояния, которые меняются с теми или иными интенсивностями λ_i и μ_i.

Очередь c одним сервером, интенсивности поступления λ и обслуживания μ.

Стационарные уравнения для процесса рождения–смерти (уравнения баланса):

${\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 {\lambda _{1}\lambda _{0}}{\mu _{2}\mu _{1}}}P_{0}}$

В общем виде

${\displaystyle P_{n}={\frac {\lambda _{n-1}\cdots \lambda _{0}}{\mu _{n}\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}=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}}$ полностью определяет стационарное распределение.

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

Очередь с одним сервером:

• ${\displaystyle \lambda }$ — интенсивность поступления (среднее число клиентов в единицу времени)
• ${\displaystyle \mu }$ — средняя интенсивность обслуживания (обратное среднему времени обслуживания)
• n — число клиентов в системе
• ${\displaystyle P_{n}}$ — вероятность наличия n клиентов в системе в стационарном режиме

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

${\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}=\left(1-\rho \right)\rho ^{n}}$, где ${\displaystyle \rho ={\frac {\lambda }{\mu }}<1}$ — классическое геометрическое распределение.

Базовая система Эрланга (модификация закона Литтла):

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

где λ — интенсивность поступления, σ — интенсивность ухода без обслуживания (отказ, dropout), μ — интенсивность обслуживания, L — средняя длина очереди.

Время ожидания W при экспоненциальных законах определяется как:

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

или

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

Такие модели используются, например, в эпидемиологических задачах^[7].

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

• M — «марковский» (memoryless): поступления происходят по пуассоновскому процессу;
• D — «детерминированный»: фиксированное время обслуживания;
• k — число серверов.

При недостатке серверов работы встают в очередь.

Очередь M/G/1 была решена Феликсом Полячеком (1930)^[10], а позднее — в вероятностном виде Александром Хинчиным; решение известно как формула Полячека–Хинчина^[9].

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

Леонард Клейнрок применял теорию массового обслуживания к коммутации сообщений (1960-е) и пакетной коммутации (1970-е). Его работы оказали большое влияние на развитие сетей ARPANET — предшественника Интернета.

Разработка матричных методов позволила учитывать фазовые распределения времени обслуживания и прихода^[15].

Модели с связанными орбитами применяются, в частности, в теории беспроводных сетей и обработке сигналов^[16].

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

Так, задачи вычисления характеристик для M/G/k-систем во многих случаях до сих пор остаются открытыми^[9].^[11]

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

Первым пришёл — первым обслужен (FIFO, First come, first served)

Пример работы очереди FIFO

Классический принцип: каждый клиент обслуживается по мере поступления, предпочтение у того, кто ждал дольше^[18].^[19]

Последним пришёл — первым обслужен (LIFO)

предпочтение новому клиенту с минимальным временем ожидания; модель также называют стеком^[19].

Processor sharing

Совместное разделение ресурсов между всеми клиентами (например, процессорное время делится поровну)^[19].

Приоритеты

Особо важные заявки обслуживаются раньше (приоритетные очереди бывают вытесняющими и невытесняющими)^[19][20].

Минимальное время выполнения

обслуживается задача с наименьшим объёмом работы^[21].

Прерываемое обслуживание минимальной задачи

обслуживается задача с минимальным исходным объёмом^[22].

Минимальное оставшееся время

выбирается задача с наименьшим оставшимся временем^[23].

Устройство обслуживания

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

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

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

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

• Отказ от входа (balking) — если очередь слишком длинна, клиент не встаёт в очередь;
• Перестановка (jockeying) — клиент меняет очередь, если считает, что в другой обслужат быстрее;
• Ожидание сверх нормы и уход (reneging) — клиент покидает очередь из-за слишком долгого ожидания.

Клиенты, не получившие обслуживание по разным причинам, называются отказниками (dropouts).

Сети массового обслуживания — это системы, состоящие из нескольких взаимосвязанных очередей, между которыми клиенты могут перемещаться после обслуживания. Состояние сети из m узлов описывается вектором из m компонент (x₁, ..., x_m).

Самые простые — тандемные очереди (сети Джексона), для которых найдены эффективные решения (продукт-форма стационарного распределения, анализ средних значений)^[25].^[26][27] Если число клиентов в системе постоянно (замкнутая сеть) — работают формулы Гордона–Ньюэлла, которые затем были обобщены для BCMP-сетей, допускающих произвольные режимы обслуживания и модели маршрутизации^[28]. Быстрые алгоритмы для вычисления нормирующей константы были предложены Джеффри Бузеном^[29].

Изучались также сети с неоднородным приоритетным обслуживанием (сети Келли), различные типы входных потоков (G-сети по Эролу Геленбе)^[30].

В дискретных сетях при ограничениях на активность узлов часто используются max-weight-алгоритмы или маршрутизация по обратному давлению для оптимального распределения пропускной способности^[18]. Выбор конкретного алгоритма очередей влияет на работу всей сети^[31].

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

При больших загрузках систему приближённо описывают с помощью отражённого броуновского движения^[33], орнштейновского процесса и других моделей диффузии^[34]. Число измерений процесса соответствует числу очередных узлов.

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

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

Принципы теории массового обслуживания актуальны и в повседневной жизни — например, при очередях в магазинах или в общественном транспорте. Понимание закономерностей позволяет оптимизировать процессы и повысить удовлетворённость пользователей. В любой сфере, где возникает ожидание, применимы методы этой теории^[36].