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

Теория массового обслуживания (ТМО; также теория очередей, queueing theory) — это раздел прикладной математики и исследования операций, изучающий системы, в которых заявки (требования на обслуживание) поступают случайным образом и обслуживаются одним или несколькими устройствами (каналами, приборами) по определённым правилам. Основная цель ТМО — анализ и оптимизация характеристик таких систем: среднего времени ожидания, длины очереди, загрузки обслуживающих устройств и вероятности отказов.

История

Первые работы, заложившие основы теории массового обслуживания, принадлежат датскому математику и инженеру Агнеру Крарупу Эрлангу. В 1909 году он опубликовал статью «Теория вероятностей и телефонные разговоры», в которой исследовал потери вызовов на телефонной станции Копенгагена. Эрланг вывел формулы для расчёта вероятности блокировки вызовов (формула Эрланга B) и средней задержки (формула Эрланга C). Эти результаты стали фундаментом для проектирования телефонных сетей.

В 1920–1930-х годах теория развивалась трудами Ф. Поллачека, А. Я. Хинчина (СССР) и других учёных. Хинчин в 1932 году ввёл понятие простейшего потока событий — пуассоновского потока, ставшего стандартной моделью для входящих заявок. В 1950–1960-х годах, с развитием вычислительной техники и автоматизации, ТМО получила широкое применение в промышленности, логистике, проектировании компьютерных сетей и систем управления.

Основные понятия и определения

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

СМО — это совокупность устройств (каналов обслуживания), правил поступления заявок и дисциплины очереди. Классическая модель включает:

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

Классификация СМО (нотация Кендалла)

В 1953 году Дэвид Кендалл предложил стандартную трёхсимвольную нотацию для описания СМО: A/B/c, где:

• A — распределение интервалов между заявками (M — экспоненциальное, D — детерминированное, G — произвольное);
• B — распределение времени обслуживания (те же обозначения);
• c — число обслуживающих каналов (1, 2, …).

Примеры:

• M/M/1 — пуассоновский входной поток, экспоненциальное обслуживание, один канал. Классическая одноканальная система.
• M/D/1 — пуассоновский вход, детерминированное (постоянное) время обслуживания.
• G/G/c — произвольные распределения, многоканальная система.

Дополнительные символы могут указывать ёмкость очереди (K) и дисциплину обслуживания (FIFO, LIFO, приоритеты).

Характеристики и показатели

Для любой СМО вычисляются ключевые параметры:

• Интенсивность поступления заявок (λ) — среднее число заявок в единицу времени.
• Интенсивность обслуживания (μ) — среднее число заявок, которое может обслужить один канал за единицу времени.
• Загрузка системы (ρ = λ/(c·μ)) — доля времени, когда каналы заняты. При ρ ≥ 1 очередь неограниченно растёт.
• Средняя длина очереди (Lq) — среднее число заявок, ожидающих в очереди.
• Среднее время ожидания в очереди (Wq) — среднее время от поступления заявки до начала её обслуживания.
• Среднее время пребывания в системе (W = Wq + 1/μ).
• Вероятность отказа (Pотк) — доля заявок, покидающих систему необслуженными (для систем с ограниченной очередью).

Формулы для M/M/1

Для системы M/M/1 с бесконечной очередью:

• Средняя длина очереди: Lq = λ²/(μ(μ−λ)).
• Среднее время ожидания: Wq = λ/(μ(μ−λ)).
• Среднее число заявок в системе: L = λ/(μ−λ).
• Среднее время пребывания: W = 1/(μ−λ).

Виды систем массового обслуживания

По числу каналов

• Одноканальные (c=1) — например, касса в магазине.
• Многоканальные (c>1) — например, колл-центр с несколькими операторами.

По дисциплине очереди

• FIFO (First In, First Out) — первым пришёл — первым обслужен. Наиболее распространённая дисциплина.
• LIFO (Last In, First Out) — последним пришёл — первым обслужен (стек).
• Приоритетные — заявки с более высоким приоритетом обслуживаются раньше (например, экстренные вызовы в больнице).
• Случайный выбор — заявка выбирается из очереди по случайному закону.

По поведению заявок

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

По числу фаз обслуживания

• Однофазные — заявка обслуживается одним устройством.
• Многофазные — заявка последовательно проходит несколько этапов (например, производственная линия).

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

ТМО используется в широком спектре отраслей:

Телекоммуникации и сети

• Расчёт числа линий связи для обеспечения заданной вероятности блокировки вызовов (формула Эрланга B).
• Проектирование центров обработки данных и маршрутизаторов (модели M/M/1, M/D/1).

Транспорт и логистика

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

Здравоохранение

• Планирование количества коек в больницах, приёмных покоев, операционных.
• Оптимизация работы скорой помощи (распределение вызовов по бригадам).

Производство и складское хозяйство

• Расчёт числа станков, обслуживаемых одним рабочим (модель М/М/1 с учётом поломок).
• Планирование работы складских погрузчиков.

Информационные технологии

• Оценка производительности серверов, баз данных, веб-приложений.
• Моделирование очередей в операционных системах (планировщики задач).

Обслуживание клиентов

• Расчёт числа касс в супермаркетах, операторов в колл-центрах.
• Оптимизация времени ожидания в банках, почтовых отделениях.

Интересные факты

• В 1917 году Эрланг опубликовал работу, в которой впервые применил пуассоновский процесс для моделирования телефонных вызовов. Его формулы до сих пор используются в телекоммуникациях.
• В СССР теория массового обслуживания активно развивалась в рамках исследования операций и кибернетики. А. Я. Хинчин и Б. В. Гнеденко внесли значительный вклад в теорию потоков событий и систем с ожиданием.
• В современных компьютерных сетях для анализа задержек пакетов часто используют модель M/M/1, хотя реальные распределения могут отличаться от экспоненциального.
• В 2000-х годах ТМО стала применяться в анализе социальных сетей и интернет-трафика, где очереди возникают при передаче данных.

Критика и ограничения

Классические модели ТМО (M/M/1, M/M/c) основаны на предположении о пуассоновском входном потоке и экспоненциальном времени обслуживания. В реальных системах эти допущения часто нарушаются: интервалы между заявками могут быть коррелированы, время обслуживания — иметь тяжелые хвосты или быть детерминированным. Для таких случаев разработаны более сложные модели (G/G/1, G/G/c), но их аналитическое решение часто затруднено, и приходится применять имитационное моделирование (метод Монте-Карло).

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

Источники

• Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. — 4-е изд. — М.: ЛКИ, 2007.
• Клейнрок Л. Теория массового обслуживания. — М.: Машиностроение, 1979.
• Хинчин А. Я. Работы по математической теории массового обслуживания. — М.: Физматгиз, 1963.
• Эрланг А. К. Теория вероятностей и телефонные разговоры. — 1909.
• Kendall D. G. Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain // The Annals of Mathematical Statistics. — 1953. — Vol. 24, No. 3.