Теорема Гордона–Ньюэлла

В теории очередей , дисциплине в математической теории вероятностей , теорема Гордона–Ньюэлла является расширением теоремы Джексона с открытых сетей очередей на закрытые сети очередей экспоненциальных серверов, где клиенты не могут покинуть сеть. ^[1] Теорема Джексона не может быть применена к закрытым сетям, поскольку длина очереди в узле в закрытой сети ограничена населением сети. Теорема Гордона–Ньюэлла вычисляет решение для открытой сети, а затем устраняет недопустимые состояния путем перенормировки вероятностей. Вычисление нормализующей константы делает обработку более неудобной, поскольку необходимо перечислить все пространство состояний. Алгоритм Бузена или анализ среднего значения можно использовать для более эффективного вычисления нормализующей константы. ^[2]

Определение сети Гордона–Ньюэлла

Сеть из m взаимосвязанных очередей известна как сеть Гордона–Ньюэлла ^[3] или закрытая сеть Джексона ^[4], если она удовлетворяет следующим условиям:

1. сеть закрыта (клиенты не могут войти или выйти из сети),
2. все времена обслуживания распределены экспоненциально, а дисциплина обслуживания во всех очередях равна FCFS ,
3. клиент, завершивший обслуживание в очереди i, перейдет в очередь j с вероятностью , при этом , ${\displaystyle P_{ij}}$ ${\displaystyle P_{ij}}$ ${\textstyle \sum _{j=1}^{m}P_{ij}=1}$
4. коэффициент использования всех очередей меньше единицы.

Теорема

В замкнутой сети Гордона–Ньюэлла из m очередей с общей популяцией K индивидуумов запишите (где k _i — длина очереди i ) для состояния сети и S ( K ,  m ) для пространства состояний ${\displaystyle \scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}}$

${\displaystyle S(K,m)=\left\{\mathbf {k} \in \mathbb {N} ^{m}{\text{ such that }}\sum _{i=1}^{m}k_{i}=K\right\}.}$

Тогда распределение вероятностей равновесного состояния существует и определяется выражением

${\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})={\frac {1}{G(K)}}\prod _{i=1}^{m}\left({\frac {e_{i}}{\mu _{i}}}\right)^{k_{i}}}$

где время обслуживания в очереди i экспоненциально распределено с параметром μ _i . Нормирующая константа G ( K ) определяется как

${\displaystyle G(K)=\sum _{\mathbf {k} \in S(K,m)}\prod _{i=1}^{m}\left({\frac {e_{i}}{\mu _{i}}}\right)^{k_{i}},}$

и e _i - коэффициент посещений, рассчитанный путем решения одновременных уравнений

${\displaystyle e_{i}=\sum _{j=1}^{m}e_{j}p_{ji}{\text{ for }}1\leq i\leq m.}$

Смотрите также

• сеть БКМП

Ссылки

1. Гордон, У. Дж.; Ньюэлл, Г. Ф. (1967). «Закрытые системы очередей с экспоненциальными серверами». Исследование операций . 15 (2): 254. doi :10.1287/opre.15.2.254. JSTOR  168557.
2. Buzen, JP (1973). "Вычислительные алгоритмы для закрытых сетей очередей с экспоненциальными серверами" (PDF) . Сообщения ACM . 16 (9): 527. doi :10.1145/362342.362345. Архивировано из оригинала (PDF) 2016-05-13 . Получено 2015-08-29 .
3. Дадуна, Х. (1982). «Время прохождения для путей без обгона в сетях Гордона-Ньюэлла». Достижения в прикладной теории вероятностей . 14 (3): 672–686. doi :10.2307/1426680.
4. Gong, Q.; Lai, KK; Wang, S. (2008). «Сети цепочек поставок: закрытые модели и свойства сетей Джексона». Международный журнал экономики производства . 113 (2): 567. doi :10.1016/j.ijpe.2007.10.013.