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

Формула Поллачека — Хинчина: очередь 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]$$
Схема Разброс обслуживания и задержка
01230123Отношение Wq/mКвадрат вариации Cs²Wq/m

При ρ=0,6 отношение Wq/m равно 0,75(1+Cs²). Отмечены постоянная и экспоненциальная длительности.

Обозначения

$\lambda$
интенсивность пуассоновских приходов, ч⁻¹
$S$
случайная длительность обслуживания, ч
$\mathbb E[S]$
первый момент обслуживания, ч
$\mathbb E[S^2]$
второй начальный момент обслуживания, ч²
$\rho$
доля времени занятости, —
$W_q$
среднее ожидание до начала работы, ч

Условия применения

Приходы пуассоновские и однородные. Длительности работ независимы, одинаково распределены и независимы от входа. Один канал обслуживает по порядку прихода без прерываний, перерывов и простоев при непустой очереди; буфер бесконечен. Требуются λE[S]<1 и конечный E[S²].

Ограничения

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

Подробное объяснение

Средняя загрузка зависит от первого момента m=E[S], но заявка ждёт окончания уже начатой работы и обслуживания тех, кто стоит перед ней. При случайном наблюдении длинные работы встречаются чаще коротких. Поэтому средний остаток текущего обслуживания определяется вторым моментом, а не половиной среднего времени каждой работы.

Средний вклад остатка по всем моментам наблюдения равен λE[S²]/2: каждый сеанс длительности s создаёт площадь остаточного времени s²/2. Ещё λWq заявок в среднем стоят в очереди перед приходом, и каждая требует среднее время m. Уравнение Wq=λE[S²]/2+λmWq после переноса слагаемого даёт знаменатель 1−ρ.

Через коэффициент вариации Cs²=Var(S)/m² второй момент записывается как m²(1+Cs²). Следовательно, Wq=[ρm/(2(1−ρ))](1+Cs²). При фиксированных ρ и m задержка линейно растёт с квадратом коэффициента вариации. Постоянная длительность даёт Cs²=0, экспоненциальная — Cs²=1: у второй ожидание вдвое больше.

Размерность λE[S²] равна времени, а знаменатель безразмерен. Полное время W получается добавлением m. Формула описывает среднее стационарного режима; из неё нельзя получить вероятность превышения срока без дополнительных сведений о распределении обслуживания. Два распределения с одинаковыми первыми моментами могут иметь одинаковое среднее ожидание, но разные хвосты задержки.

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

  1. Из длительностей обслуживания найдите среднее m и средний квадрат; сначала переведите все времена в одну единицу.
  2. Проверьте пуассоновский вход и независимость работ; рассчитайте ρ=λm и убедитесь, что оно строго меньше единицы.
  3. Если известна дисперсия, найдите второй начальный момент как Var(S)+m², не подставляя одну дисперсию вместо него.
  4. Вычислите Wq; затем добавьте m для полного времени и проверьте единицы произведения λE[S²].

Историческая справка

Название Поллачека — Хинчина относится к классической теории одноканальной очереди с общим распределением обслуживания. По сравнению с марковской моделью здесь отказываются от экспоненциальной длительности, сохраняя пуассоновский приход. Это позволяет отделить влияние среднего объёма работы от влияния разброса длительностей и объяснить эффект редких длинных сеансов.

В лекции Уорда Уитта от 1 ноября 2012 года M/G/1 рассматривается через вложенную марковскую цепь и формулы Поллачека — Хинчина для средних. Современный учебный вывод через остаточную работу даёт наглядное объяснение появления второго момента. Название относится к семейству связанных результатов, включая распределительные преобразования; приведённая запись — формула среднего ожидания для порядка обслуживания по приходу, а не полное распределение задержки.

Историческая линия формулы

Источники называют этот результат формулой Поллачека — Хинчина. Здесь используется её версия для среднего ожидания в M/G/1 с обслуживанием по приходу. Из названия не следует, что все варианты вывода и современные обозначения принадлежат одному автору или одной публикации.

Пример

На одно устройство приходит 4 запроса в час. Обработка занимает 6 или 12 минут с равными вероятностями, независимо от других работ и приходов. Вход принят пуассоновским. Найдём среднее ожидание в общей очереди. В часах S равна 0,1 или 0,2. m=(0,1+0,2)/2=0,15 ч, E[S²]=(0,01+0,04)/2=0,025 ч². Нагрузка ρ=4·0,15=0,6. Wq=4·0,025/[2·0,4]=0,125 ч=7,5 мин. Полный срок W=7,5+9=16,5 мин. Для проверки Var(S)=0,025−0,0225=0,0025 ч² и Cs²=1/9; подстановка альтернативной записи даёт те же 7,5 мин. Подстановка дисперсии вместо второго момента ошибочно уменьшила бы ответ в десять раз.

Частая ошибка

Второй начальный момент равен среднему квадрату времени, а не квадрату среднего; разность этих величин есть дисперсия. Нельзя смешивать λ в час⁻¹ с S в минутах без перевода. Уменьшение разброса не меняет ρ при прежнем среднем, но снижает ожидание. Стационарная нагрузка меньше единицы сама по себе не гарантирует конечного Wq: необходим конечный второй момент.

Практика

Задачи с решением

Постоянная длительность

Условие. При λ=4 ч⁻¹ все работы занимают ровно 9 минут. Найдите Wq.

Решение. m=0,15 ч, E[S²]=0,0225 ч², ρ=0,6. Wq=4·0,0225/(2·0,4)=0,1125 ч=6,75 мин.

Ответ. 6,75 мин.

Экспоненциальное обслуживание

Условие. Сохранены λ=4 ч⁻¹ и m=9 минут, но S экспоненциальна. Найдите ожидание.

Решение. E[S²]=2m²=0,045 ч². Wq=4·0,045/0,8=0,225 ч=13,5 мин. Это вдвое больше постоянного обслуживания.

Ответ. 13,5 мин.

Дополнительные источники

  • https://www.columbia.edu/~ww2040/6711F12/lect1101.pdf
  • https://www.columbia.edu/~ww2040/8100S12/Qmodels.html

Связанные формулы

Бизнес

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

$\rho=\frac{\lambda}{\mu}<1,\qquad W_q=\frac{\lambda}{\mu(\mu-\lambda)},\qquad W=\frac1{\mu-\lambda}$

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

Бизнес

Формула Эрланга 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 определяет вероятность такого отказа по предложенной нагрузке и числу каналов, когда места ожидания нет.

Бизнес

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

$WIP=Throughput\cdot Flow\ Time$

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