Тревожная формула

В теории массового обслуживания формула Энгсета используется для определения вероятности блокировки очереди M/M/c/c/N (в обозначениях Кендалла ).

Формула названа в честь ее разработчика, компании TO Engset .

Пример приложения

Рассмотрим флот из $c$ транспортные средства и $N$ операторы. Операторы входят в систему случайным образом, чтобы запросить использование транспортного средства. Если транспортных средств нет, запрашивающий оператор «блокируется» (т. е. оператор уезжает без транспортного средства). Владелец автопарка хотел бы забрать $c$ небольшой, чтобы минимизировать затраты, но достаточно большой, чтобы обеспечить приемлемую вероятность блокировки.

Формула

Позволять

$c>0$ быть (целым) числом серверов.
$N>c$ быть (целым) количеством источников трафика;
$\lambda >0$ быть скоростью поступления незанятого источника (т. е. скоростью, с которой свободный источник инициирует запросы);
$h>0$ быть средним временем удержания (т. е. средним временем, которое требуется серверу для обработки запроса);

Тогда вероятность блокировки определяется выражением ^[1]

P={\frac {{\binom {N-1}{c}}\left(\lambda h\right)^{c}}{\sum _{i=0}^{c}{\binom {N-1}{i}}\left(\lambda h\right)^{i}}}.

Переставив члены, можно переписать приведенную выше формулу как ^[2]

P={\frac {1}{{}_{2}F_{1}(1,-c;N-c;-1/(\lambda h))}}

где ${}_{2}F_{1}$ Гаусса — гипергеометрическая функция .

Вычисление

Есть несколько рекурсий ^[3] который можно использовать для вычисления $P$ численно стабильным образом.

любой числовой пакет, поддерживающий гипергеометрическую функцию В качестве альтернативы можно использовать . Некоторые примеры приведены ниже.

Python с SciPy

from scipy.special import hyp2f1
P = 1.0 / hyp2f1(1, -c, N - c, -1.0 / (Lambda * h))

MATLAB с набором инструментов символьной математики

P = 1 / hypergeom([1, -c], N - c, -1 / (Lambda * h))

Скорость поступления из неизвестного источника

На практике часто бывает, что скорость поступления источника $\lambda$ неизвестно (или трудно оценить), в то время как $\alpha >0$ , предлагаемый трафик на источник известен. В этом случае можно заменить отношение

\lambda h={\frac {\alpha }{1-\alpha (1-P)}}

между скоростью поступления источника и вероятностью блокировки в формулу Энгсета, чтобы прийти к уравнению фиксированной точки

P=f(P)

где

f(P)={\frac {1}{{}_{2}F_{1}(1,-c;N-c;1-P-1/\alpha )}}.

Вычисление

Хотя вышеизложенное удаляет неизвестное $\lambda$ Судя по формуле, это вносит дополнительную сложность: мы больше не можем вычислять вероятность блокировки напрямую и вместо этого должны использовать итерационный метод. Хотя итерация с фиксированной точкой заманчива, было показано, что такая итерация иногда расходится при применении к $f$ . ^[2] В качестве альтернативы можно использовать один из методов деления пополам или метода Ньютона , для которого реализация с открытым исходным кодом доступна .

Ссылки

^ Таймс, Хенк К. (2003). Первый курс стохастических моделей . Джон Уайли и сыновья. дои : 10.1002/047001363X .
^ Jump up to: ^а ^б Азимзаде, Парсиад; Карпентер, Томми (2016). «Быстрые вычисления Engset». Письма об исследованиях операций . 44 (3): 313–318. arXiv : 1511.00291 . дои : 10.1016/j.orl.2016.02.011 . ISSN 0167-6377 .
^ Цукерман, Моше (2000). «Введение в теорию массового обслуживания и стохастические модели телетрафика» (pdf) . Проверено 27 ноября 2012 г.

[Tijms2003-1] Таймс, Хенк К. (2003). Первый курс стохастических моделей . Джон Уайли и сыновья. дои : 10.1002/047001363X .

[AzimzadehCarpenter2016-2] Jump up to: ^а ^б Азимзаде, Парсиад; Карпентер, Томми (2016). «Быстрые вычисления Engset». Письма об исследованиях операций . 44 (3): 313–318. arXiv : 1511.00291 . дои : 10.1016/j.orl.2016.02.011 . ISSN 0167-6377 .

[Zukerman-3] Цукерман, Моше (2000). «Введение в теорию массового обслуживания и стохастические модели телетрафика» (pdf) . Проверено 27 ноября 2012 г.

[1]

[2]

[3]