Бизнес / Операционный менеджмент
Среднее ожидание в одноканальной очереди M/M/1
Модель M/M/1 связывает интенсивность прихода заявок и скорость одного обслуживающего канала со средним ожиданием. При приближении нагрузки к мощности канала задержка растёт нелинейно.
Формула
По вертикали μWq=ρ/(1−ρ): ожидание в единицах среднего обслуживания. Область графика заканчивается до ρ=1.
Обозначения
- $\lambda$
- средняя интенсивность входного потока, ч⁻¹
- $\mu$
- интенсивность обслуживания занятого канала, ч⁻¹
- $\rho$
- доля времени занятости канала, —
- $W_q$
- среднее время до начала обслуживания, ч
- $W$
- среднее время в системе вместе с обслуживанием, ч
Условия применения
Заявки приходят по однородному пуассоновскому потоку, длительности обслуживания независимы и имеют экспоненциальное распределение со средним 1/μ. Есть один непрерывно работающий канал и неограниченное место ожидания. Порядок обслуживания — по приходу; λ<μ, рассматривается стационарный режим.
Ограничения
Смена интенсивности по часам, пакетные поступления, перерывы оператора и уход клиентов из очереди нарушают модель. При λ≥μ конечного стационарного среднего нет. Даже при λ<μ среднее ожидание не является гарантией для отдельного клиента и не определяет требуемый процентиль задержки.
Подробное объяснение
Интенсивность μ относится к занятому каналу: среднее обслуживание длится 1/μ. Она не равна фактическому числу завершений за час, если канал иногда простаивает. При устойчивой работе фактический выход равен λ, а доля занятости равна ρ=λ/μ. Разность μ−λ показывает запас мощности в тех же единицах, что и интенсивности.
Для числа заявок n в системе баланс соседних состояний даёт pₙ₊₁=ρpₙ. Нормировка геометрической последовательности приводит к pₙ=(1−ρ)ρⁿ. Среднее число заявок L=ρ/(1−ρ), а время в системе W=L/λ=1/(μ−λ). Вычитая собственное среднее обслуживание 1/μ, получаем Wq. Так отделяются ожидание и работа канала.
Если μ постоянно, удвоение λ не означает удвоения задержки: одновременно уменьшается свободный запас мощности. При нагрузке 0,5 среднее ожидание равно одному среднему обслуживанию, а при 0,9 — уже девяти. Поэтому планирование работы на стопроцентную среднюю загрузку несовместимо с конечной стационарной задержкой в этой модели.
Из среднего ожидания получается и средняя длина очереди Lq=λWq=ρ²/(1−ρ). Здесь не учитывается обслуживаемая заявка. Число в системе L отличается от Lq на ρ, а не на единицу: канал занят лишь часть времени. Для проверки расчёта полезно независимо сопоставить обе длины и оба времени.
Как пользоваться формулой
- Оцените число поступлений за достаточно однородный период; разделите его на длительность периода, получив интенсивность λ.
- Измерьте среднее время работы над одной заявкой без простоев и возьмите обратную величину, чтобы получить μ.
- Приведите обе интенсивности к одной единице времени и проверьте λ<μ до вычисления среднего стационарного ожидания.
- Вычислите Wq и прибавьте среднее обслуживание 1/μ; сравните сумму с независимо найденным W=1/(μ−λ).
Историческая справка
Одноканальная марковская очередь относится к классическим моделям массового обслуживания. Её современная запись через процессы рождения и гибели систематизирует две конкурирующие причины изменения длины: приход увеличивает состояние на единицу, завершение работы уменьшает его. Для вывода среднего достаточно стационарного баланса, а не имитации каждого отдельного клиента.
В университетских курсах начала XXI века, в том числе лекциях Эйтана Модиано в MIT, эта модель применяется к задержкам пакетов и буферам вычислительных сетей. Такой переход к сетям сохраняет математическую схему одного канала, но требует обоснования случайного входа и распределения обслуживания. Обозначение M/M/1 фиксирует именно предпосылки модели; оно не сообщает, что любая очередь с одним оператором обязана вести себя так же.
Историческая линия формулы
Формулы M/M/1 рассматриваются как классический результат теории марковских очередей. Приведённые учебные источники объясняют их балансом состояний; приписывать каждую из эквивалентных записей ожидания отдельному изобретателю оснований нет. Закон Литтла используется как связь средних.
Пример
На пост поступает в среднем 6 заявок в час. Среднее обслуживание длится 6 минут, время между приходами и длительности работ согласуются с предпосылками M/M/1. Требуется среднее время ожидания и полное время заявки. Переведём обслуживание в часы: 6/60=0,1 ч, поэтому μ=10 ч⁻¹. Нагрузка ρ=6/10=0,6 меньше единицы. Wq=6/[10·(10−6)]=0,15 ч=9 мин. Полное время W=1/(10−6)=0,25 ч=15 мин. Проверка: 9+6=15 мин; среднее число ожидающих Lq=6·0,15=0,9 заявки. Дробное число допустимо, поскольку это среднее по времени, а не размер конкретной очереди.
Частая ошибка
Нельзя подставлять 6 минут вместо μ: μ — обратное среднему времени. Не следует считать Wq полным сроком заявки: к нему прибавляют обслуживание. Условие λ<μ проверяют до вычисления, иначе отрицательное значение формулы не имеет смысла среднего ожидания. Среднюю загрузку 60% нельзя толковать как отсутствие очередей: случайные сгущения приходов создают ожидание и при свободной мощности.
Практика
Задачи с решением
Рост входного потока
Условие. При μ=10 ч⁻¹ вход вырос до λ=8 ч⁻¹. Найдите Wq и W.
Решение. Wq=8/(10·2)=0,4 ч=24 мин; W=1/2 ч=30 мин. Разность 6 мин равна среднему обслуживанию.
Ответ. 24 мин ожидания; 30 мин в системе.
Допустимая интенсивность
Условие. При μ=12 ч⁻¹ нужно Wq≤5 мин. Найдите максимальную λ в модели.
Решение. 5 мин=1/12 ч. λ/[12(12−λ)]≤1/12, откуда λ≤12−λ, то есть λ≤6 ч⁻¹. При границе W=10 мин.
Ответ. Не более 6 заявок в час.
Дополнительные источники
- https://web.mit.edu/modiano/www/6.263/lec5-6.pdf
- https://archive.nptel.ac.in/content/storage2/courses/117103017/module3/lec1/4.html
- https://www.columbia.edu/~ww2040/8100S12/Qmodels.html
Связанные формулы
Бизнес
Формула Эрланга C: ожидание нескольких каналов
Формула Эрланга C даёт вероятность того, что пришедшая заявка застанет все каналы занятыми. Для общей очереди M/M/c из неё находят среднее ожидание до начала обслуживания.
Бизнес
Формула Эрланга B: вероятность отказа без очереди
В системе потерь заявка уходит, если заняты все каналы. Формула Эрланга B определяет вероятность такого отказа по предложенной нагрузке и числу каналов, когда места ожидания нет.
Бизнес
Формула Поллачека — Хинчина: очередь M/G/1
Формула Поллачека — Хинчина выражает среднее ожидание при одном канале через первые два момента времени обслуживания. Она показывает, почему разброс длительностей увеличивает задержку даже при прежней нагрузке.
Бизнес
WIP по закону Литтла
Формула связывает незавершенную работу, throughput и среднее время прохождения потока. Такой показатель помогает читать бизнес-модель через проверяемые величины, а не через общие впечатления.