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

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

История

Первые систематические исследования в области теории очередей относятся к началу XX века. Основоположником считается датский инженер Агнер Краруп Эрланг, который в 1909—1917 годах работал над задачами телефонной связи в Копенгагенской телефонной компании. Эрланг опубликовал работу «Теория вероятностей и телефонные разговоры» (1909), где впервые математически описал процесс поступления вызовов и их обслуживания, предложив модель, известную как система M/M/1 (по классификации Кендалла). Его формулы для вероятности блокировки вызова (формула Эрланга B) и вероятности задержки (формула Эрланга C) до сих пор используются в телекоммуникациях.

В 1930-х годах теория развивалась в работах советских математиков А. Н. Колмогорова и Б. В. Гнеденко, которые внесли вклад в теорию потоков событий и марковских процессов. В 1950-х годах Дэвид Кендалл предложил стандартную нотацию для классификации систем массового обслуживания (A/B/c/K/N/D), что позволило унифицировать описание моделей. В 1960—1970-х годах теория очередей активно применялась в проектировании вычислительных систем, сетей передачи данных и производственных процессов.

Основные понятия

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

Система массового обслуживания — это любая система, состоящая из:

• Входящего потока заявок — последовательности требований, поступающих на обслуживание. Поток может быть детерминированным или случайным (например, пуассоновский поток — наиболее распространённая модель).
• Очереди — буфера, в котором заявки ожидают начала обслуживания. Очередь может быть ограниченной (максимальное число мест) или неограниченной.
• Обслуживающих устройств (каналов) — ресурсов, которые обрабатывают заявки. Число каналов может быть от одного до нескольких десятков и более.
• Дисциплины обслуживания — правила, определяющие порядок выбора заявок из очереди. Наиболее распространённые дисциплины:
• FIFO (First In, First Out) — первым пришёл, первым обслужен;
• LIFO (Last In, First Out) — последним пришёл, первым обслужен;
• SJF (Shortest Job First) — сначала обслуживаются короткие заявки;
• Приоритетное обслуживание (с абсолютным или относительным приоритетом).

Классификация по Кендаллу

Стандартная нотация Кендалла описывает СМО в формате A/B/c/K/N/D, где:

• A — распределение интервалов между поступлениями заявок (например, M — экспоненциальное, D — детерминированное, G — произвольное);
• B — распределение времени обслуживания (аналогично A);
• c — число обслуживающих каналов;
• K — максимальная ёмкость очереди (если не указано, считается бесконечной);
• N — число источников заявок (если не указано, считается бесконечным);
• D — дисциплина обслуживания (если не указана, подразумевается FIFO).

Примеры:

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

Основные модели

Модель M/M/1

Наиболее простая и изученная модель. Предполагает, что:

• Заявки поступают по пуассоновскому процессу с интенсивностью λ (среднее число заявок в единицу времени);
• Время обслуживания распределено экспоненциально с параметром μ (средняя скорость обслуживания);
• Очередь бесконечна;
• Дисциплина — FIFO.

Ключевые характеристики:

• Загрузка системы ρ = λ / μ (должна быть меньше 1 для устойчивости).
• Среднее число заявок в системе L = ρ / (1 — ρ).
• Среднее время пребывания заявки в системе W = 1 / (μ — λ).
• Средняя длина очереди Lq = ρ² / (1 — ρ).
• Среднее время ожидания в очереди Wq = ρ / (μ — λ).

Модель M/M/c

Обобщение M/M/1 на случай c каналов. Характеристики вычисляются с использованием формулы Эрланга C. Эта модель широко применяется для анализа колл-центров, серверных ферм и многоканальных систем связи.

Модель M/G/1

Модель с пуассоновским входным потоком и произвольным распределением времени обслуживания. Для неё существует формула Поллачека — Хинчина, позволяющая вычислить среднюю длину очереди:

• Lq = (λ² Var[S] + ρ²) / (2 (1 — ρ)), где Var[S] — дисперсия времени обслуживания.

Модель G/G/1

Наиболее общая модель, не предполагающая конкретных распределений. Для неё существуют аппроксимации, например, приближение Кингмана, которое даёт оценку среднего времени ожидания.

Применение

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

Теория очередей исторически возникла для задач телефонной связи. Сегодня она используется для расчёта пропускной способности сетей, анализа задержек в маршрутизаторах, проектирования систем с коммутацией пакетов и каналов. Например, модель M/M/1 применяется для оценки задержек в очередях на выходных портах маршрутизаторов.

Вычислительные системы

В операционных системах теория очередей используется для анализа планировщиков задач (например, алгоритмы Round Robin, MLFQ). В архитектуре компьютеров — для оценки производительности кэш-памяти, шин и контроллеров прерываний. В облачных вычислениях — для моделирования работы серверных кластеров и балансировщиков нагрузки.

Производство и логистика

В производственных системах теория очередей помогает оптимизировать загрузку станков, конвейеров и складских помещений. Например, модель M/D/1 используется для анализа поточных линий с постоянным временем обработки. В логистике — для расчёта времени ожидания в портах, на сортировочных центрах и в системах доставки.

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

В больницах и поликлиниках теория очередей применяется для планирования приёма пациентов, расчёта необходимого числа врачей и коек. Например, модель M/M/c используется для анализа работы отделений неотложной помощи.

Транспорт

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

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

Теория очередей имеет ряд ограничений, которые необходимо учитывать при практическом применении:

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

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

• Формула Эрланга B, выведенная в 1917 году, до сих пор используется в телекоммуникациях для расчёта числа линий связи, необходимых для заданного уровня блокировки вызовов.
• В 1950-х годах советский математик Б. В. Гнеденко совместно с И. Н. Коваленко разработал теорию систем массового обслуживания с ненадёжными элементами, что нашло применение в военной технике.
• В 1960-х годах Леонард Клейнрок применил теорию очередей для анализа сетей передачи данных с коммутацией пакетов, что стало основой для разработки ARPANET — предшественника Интернета.
• В 1970-х годах Джон Литтл вывел закон Литтла (L = λW), который является одним из фундаментальных результатов теории очередей и применим к любой стационарной системе.

Источники

• Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. — М.: Наука, 1966.
• Клейнрок Л. Теория массового обслуживания. — М.: Машиностроение, 1979.
• Saaty T. L. Elements of Queueing Theory. — McGraw-Hill, 1961.
• Gross D., Harris C. M. Fundamentals of Queueing Theory. — 4th ed. — Wiley, 2008.
• Эрланг А. К. Теория вероятностей и телефонные разговоры // Математический сборник. — 1909.