Теория массового обслуживания: модели очередей и марковские процессы

Любая система массового обслуживания (СМО) концептуально состоит из трех базовых элементов: входящего потока заявок (клиентов, пакетов данных), очереди (буфера ожидания) и обслуживающих устройств (каналов, серверов, кассиров). Для стандартизации описания таких систем в мировой практике принята нотация Кендалла, которая имеет формат A/B/C/K/N/D. Первый символ A описывает закон распределения интервалов времени между поступлениями заявок. Символ B описывает распределение времени самого обслуживания. Символ C указывает количество параллельных каналов обслуживания. Оставшиеся параметры определяют емкость очереди, размер популяции клиентов и дисциплину обслуживания (например, FIFO — первым пришел, первым ушел, или LIFO — последним пришел, первым ушел). Наиболее классической и математически изученной является система M/M/1, где буква M (Markovian) означает экспоненциальное распределение времени (или пуассоновский поток), а канал всего один.

В основе анализа марковских моделей очередей лежит свойство отсутствия последействия. Это означает, что вероятность поступления новой заявки или завершения обслуживания в следующую секунду зависит исключительно от текущего состояния системы (количества людей в ней) и абсолютно не зависит от предыстории процесса (сколько времени система находилась в этом состоянии до этого). Это мощное алгебраическое допущение позволяет описывать динамику СМО с помощью дифференциальных уравнений Колмогорова и графов состояний (процессов гибели и размножения). Переходы между состояниями (0 клиентов, 1 клиент, 2 клиента...) происходят с интенсивностями лямбда (скорость прибытия) и мю (скорость обслуживания). Решая эти уравнения для стационарного режима работы (когда система стабилизировалась во времени), математики находят вероятности нахождения системы в каждом конкретном состоянии.

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

Самой универсальной и красивой теоремой в теории массового обслуживания является Формула Литтла. Она записывается предельно просто: L = лямбда * W, где L — среднее количество заявок в системе (или в очереди), лямбда — средняя интенсивность входящего потока, а W — среднее время пребывания заявки в системе. Потрясающая мощь закона Литтла заключается в его абсолютной общности: он справедлив для любой мыслимой системы обслуживания, независимо от распределения времени, количества серверов или дисциплины очереди, при условии, что система стационарна. Это тождество позволяет менеджерам мгновенно оценивать скрытые параметры бизнес-процессов: зная, сколько клиентов входит в магазин за час и сколько в среднем человек находится в торговом зале, можно с абсолютной математической точностью вычислить, сколько минут в среднем каждый клиент проводит внутри.