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

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

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

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

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

Теорема

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

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

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

$\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 ) определяется выражением

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

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

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

См. также

• Сеть BCMP