Бизнес / Операционный менеджмент

Среднее ожидание в одноканальной очереди M/M/1

Модель M/M/1 связывает интенсивность прихода заявок и скорость одного обслуживающего канала со средним ожиданием. При приближении нагрузки к мощности канала задержка растёт нелинейно.

Опубликовано: Обновлено:

Формула

$$\rho=\frac{\lambda}{\mu}<1,\qquad W_q=\frac{\lambda}{\mu(\mu-\lambda)},\qquad W=\frac1{\mu-\lambda}$$
Схема Очередь растёт быстрее нагрузки
00.30.60.90369Ожидание μWqНагрузка ρμWq

По вертикали μ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 на ρ, а не на единицу: канал занят лишь часть времени. Для проверки расчёта полезно независимо сопоставить обе длины и оба времени.

Как пользоваться формулой

  1. Оцените число поступлений за достаточно однородный период; разделите его на длительность периода, получив интенсивность λ.
  2. Измерьте среднее время работы над одной заявкой без простоев и возьмите обратную величину, чтобы получить μ.
  3. Приведите обе интенсивности к одной единице времени и проверьте λ<μ до вычисления среднего стационарного ожидания.
  4. Вычислите 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: ожидание нескольких каналов

$a=\frac\lambda\mu,\quad\rho=\frac ac<1,\quad C=\frac{a^c/[c!(1-\rho)]}{\sum_{k=0}^{c-1}a^k/k!+a^c/[c!(1-\rho)]},\quad W_q=\frac C{c\mu-\lambda}$

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

Бизнес

Формула Эрланга B: вероятность отказа без очереди

$a=\frac\lambda\mu,\qquad B(c,a)=\frac{a^c/c!}{\sum_{k=0}^{c}a^k/k!},\qquad\lambda_{\rm accepted}=\lambda(1-B)$

В системе потерь заявка уходит, если заняты все каналы. Формула Эрланга B определяет вероятность такого отказа по предложенной нагрузке и числу каналов, когда места ожидания нет.

Бизнес

Формула Поллачека — Хинчина: очередь M/G/1

$\rho=\lambda\mathbb E[S]<1,\qquad W_q=\frac{\lambda\mathbb E[S^2]}{2(1-\rho)},\qquad W=W_q+\mathbb E[S]$

Формула Поллачека — Хинчина выражает среднее ожидание при одном канале через первые два момента времени обслуживания. Она показывает, почему разброс длительностей увеличивает задержку даже при прежней нагрузке.

Бизнес

WIP по закону Литтла

$WIP=Throughput\cdot Flow\ Time$

Формула связывает незавершенную работу, throughput и среднее время прохождения потока. Такой показатель помогает читать бизнес-модель через проверяемые величины, а не через общие впечатления.