Бизнес / Операционный менеджмент
Формула Поллачека — Хинчина: очередь M/G/1
Формула Поллачека — Хинчина выражает среднее ожидание при одном канале через первые два момента времени обслуживания. Она показывает, почему разброс длительностей увеличивает задержку даже при прежней нагрузке.
Формула
При ρ=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. Формула описывает среднее стационарного режима; из неё нельзя получить вероятность превышения срока без дополнительных сведений о распределении обслуживания. Два распределения с одинаковыми первыми моментами могут иметь одинаковое среднее ожидание, но разные хвосты задержки.
Как пользоваться формулой
- Из длительностей обслуживания найдите среднее m и средний квадрат; сначала переведите все времена в одну единицу.
- Проверьте пуассоновский вход и независимость работ; рассчитайте ρ=λm и убедитесь, что оно строго меньше единицы.
- Если известна дисперсия, найдите второй начальный момент как Var(S)+m², не подставляя одну дисперсию вместо него.
- Вычислите 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
Модель M/M/1 связывает интенсивность прихода заявок и скорость одного обслуживающего канала со средним ожиданием. При приближении нагрузки к мощности канала задержка растёт нелинейно.
Бизнес
Формула Эрланга C: ожидание нескольких каналов
Формула Эрланга C даёт вероятность того, что пришедшая заявка застанет все каналы занятыми. Для общей очереди M/M/c из неё находят среднее ожидание до начала обслуживания.
Бизнес
Формула Эрланга B: вероятность отказа без очереди
В системе потерь заявка уходит, если заняты все каналы. Формула Эрланга B определяет вероятность такого отказа по предложенной нагрузке и числу каналов, когда места ожидания нет.
Бизнес
WIP по закону Литтла
Формула связывает незавершенную работу, throughput и среднее время прохождения потока. Такой показатель помогает читать бизнес-модель через проверяемые величины, а не через общие впечатления.