сеть Джексона

Математическая дисциплина

В теории очередей , дисциплине в математической теории вероятностей , сеть Джексона (иногда сеть Джексона ^[1] ) представляет собой класс сетей очередей, в которых равновесное распределение вычисляется особенно просто, поскольку сеть имеет решение в форме произведения . Это было первое значительное развитие в теории сетей очередей , а обобщение и применение идей теоремы для поиска подобных решений в форме произведения в других сетях стало предметом многих исследований, ^[2] включая идеи, использованные при разработке Интернета. ^[3] Сети были впервые идентифицированы Джеймсом Р. Джексоном ^{[4] [5]} , и его статья была перепечатана в журнале Management Science в разделе «Десять наиболее влиятельных названий наук об управлении за первые пятьдесят лет» ^[6]

Джексон был вдохновлен работой Берка и Райха ^[7], хотя Джин Уолранд отмечает, что «результаты в форме произведения … [являются] гораздо менее непосредственным результатом теоремы о выходе, чем сам Джексон, по-видимому, полагал в своей фундаментальной работе» ^{[8] .}

Более раннее решение в форме продукта было найдено Р. Р. Джексоном для тандемных очередей (конечная цепочка очередей, где каждый клиент должен посетить каждую очередь по порядку) и циклических сетей (цикл очередей, где каждый клиент должен посетить каждую очередь по порядку). ^[9]

Сеть Джексона состоит из ряда узлов, где каждый узел представляет собой очередь, в которой скорость обслуживания может зависеть как от узла (разные узлы имеют разные скорости обслуживания), так и от состояния (скорость обслуживания меняется в зависимости от длины очереди). Задания перемещаются между узлами, следуя фиксированной матрице маршрутизации. Все задания в каждом узле принадлежат к одному «классу», и задания следуют одному и тому же распределению времени обслуживания и одному и тому же механизму маршрутизации. Следовательно, нет понятия приоритета при обслуживании заданий: все задания в каждом узле обслуживаются по принципу «первым пришел, первым обслужен» .

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

Необходимые условия для сети Джексона

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

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

Теорема

В открытой сети Джексона из m очередей M/M/1 , где коэффициент использования меньше 1 в каждой очереди, существует распределение вероятностей равновесного состояния, и для состояния задается произведением распределений равновесного состояния отдельной очереди ${\displaystyle \rho _{i}}$ ${\displaystyle \scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}}$

${\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})=\prod _{i=1}^{m}[\rho _{i}^{k_{i}}(1-\rho _{i})].}$

Результат также справедлив для станций модели M/M/c с серверами c _i на станции с требованием к использованию . ${\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})}$ ${\displaystyle i^{\text{th}}}$ ${\displaystyle \rho _{i}<c_{i}}$

Определение

В открытой сети задания поступают извне в соответствии с пуассоновским процессом со скоростью . Каждое поступление независимо направляется в узел j с вероятностью и . После завершения обслуживания в узле i задание может перейти в другой узел j с вероятностью или покинуть сеть с вероятностью . ${\displaystyle \alpha >0}$ ${\displaystyle p_{0j}\geq 0}$ ${\displaystyle \sum _{j=1}^{J}p_{0j}=1}$ ${\displaystyle p_{ij}}$ ${\displaystyle p_{i0}=1-\sum _{j=1}^{J}p_{ij}}$

Следовательно, мы имеем общую скорость прибытия в узел i , включая как внешние прибытия, так и внутренние переходы: ${\displaystyle \lambda _{i}}$

${\displaystyle \lambda _{i}=\alpha p_{0i}+\sum _{j=1}^{J}\lambda _{j}p_{ji},i=1,\ldots ,J.\qquad (1)}$

(Поскольку коэффициент использования в каждом узле меньше 1, а мы рассматриваем равновесное распределение, т.е. долгосрочное среднее поведение, скорость перехода заданий из j в i ограничена долей скорости поступления в j , и мы игнорируем скорость обслуживания в приведенном выше выражении.) ${\displaystyle \mu _{j}}$

Определим , тогда мы сможем решить . ${\displaystyle a=(\alpha p_{0i})_{i=1}^{J}}$ ${\displaystyle \lambda =(I-P^{T})^{-1}a}$

Все задания покидают каждый узел также в соответствии с процессом Пуассона и определяются как скорость обслуживания узла i, когда в узле i есть задания . ${\displaystyle \mu _{i}(x_{i})}$ ${\displaystyle x_{i}}$

Пусть обозначим число работ в узле i в момент времени t , и . Тогда равновесное распределение , определяется следующей системой уравнений баланса: ${\displaystyle X_{i}(t)}$ ${\displaystyle \mathbf {X} =(X_{i})_{i=1}^{J}}$ ${\displaystyle \mathbf {X} }$ ${\displaystyle \pi (\mathbf {x} )=P(\mathbf {X} =\mathbf {x} )}$

${\displaystyle {\begin{aligned}&\pi (\mathbf {x} )\sum _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(x_{i})(1-p_{ii})]\\={}&\sum _{i=1}^{J}[\pi (\mathbf {x} -\mathbf {e} _{i})\alpha p_{0i}+\pi (\mathbf {x} +\mathbf {e} _{i})\mu _{i}(x_{i}+1)p_{i0}]+\sum _{i=1}^{J}\sum _{j\neq i}\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+1)p_{ij}.\qquad (2)\end{aligned}}}$

где обозначают единичный вектор . ${\displaystyle \mathbf {e} _{i}}$ ${\displaystyle i^{\text{th}}}$

Теорема

Предположим, что вектор независимых случайных величин , каждая из которых имеет функцию массы вероятности, как ${\displaystyle (Y_{1},\ldots ,Y_{J})}$ ${\displaystyle Y_{i}}$

${\displaystyle P(Y_{i}=n)=p(Y_{i}=0)\cdot {\frac {\lambda _{i}^{n}}{M_{i}(n)}},\quad (3)}$

где . Если ie хорошо определено, то равновесное распределение открытой сети Джексона имеет следующую форму произведения: ${\displaystyle M_{i}(n)=\prod _{j=1}^{n}\mu _{i}(j)}$ ${\displaystyle \sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}<\infty }$ ${\displaystyle P(Y_{i}=0)=\left(1+\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}\right)^{-1}}$

${\displaystyle \pi (\mathbf {x} )=\prod _{i=1}^{J}P(Y_{i}=x_{i}).}$

для всех .⟩ ${\displaystyle \mathbf {x} \in {\mathcal {Z}}_{+}^{J}}$

Доказательство

Достаточно проверить, что уравнение выполняется. По форме произведения и формуле (3) имеем: ${\displaystyle (2)}$

${\displaystyle \pi (\mathbf {x} )=\pi (\mathbf {x} +\mathbf {e} _{i})\mu _{i}(x_{i}+1)/\lambda _{i}=\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+1)\lambda _{j}/[\lambda _{i}\mu _{j}(x_{j})]}$

Подставляя их в правую часть, получаем: ${\displaystyle (2)}$

${\displaystyle \sum _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(x_{i})(1-p_{ii})]=\sum _{i=1}^{J}[{\frac {\alpha p_{0i}}{\lambda _{i}}}\mu _{i}(x_{i})+\lambda _{i}p_{i0}]+\sum _{i=1}^{J}\sum _{j\neq i}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}\mu _{j}(x_{j}).\qquad (4)}$

Затем используем , имеем: ${\displaystyle (1)}$

${\displaystyle \sum _{i=1}^{J}\sum _{j\neq i}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}\mu _{j}(x_{j})=\sum _{j=1}^{J}[\sum _{i\neq j}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}]\mu _{j}(x_{j})=\sum _{j=1}^{J}[1-p_{jj}-{\frac {\alpha p_{0j}}{\lambda _{j}}}]\mu _{j}(x_{j}).}$

Подставляя вышесказанное в , имеем: ${\displaystyle (4)}$

${\displaystyle \sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}p_{i0}}$

Это можно проверить с помощью . Следовательно, обе стороны равны.⟨ ${\displaystyle \sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}}$ ${\displaystyle (2)}$

Эта теорема расширяет показанную выше, допуская зависящую от состояния скорость обслуживания каждого узла. Она связывает распределение с вектором независимой переменной . ${\displaystyle \mathbf {X} }$ ${\displaystyle \mathbf {Y} }$

Пример

Открытая сеть Джексона с тремя узлами

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

${\displaystyle \alpha =5,\quad p_{01}=p_{02}=0.5,\quad p_{03}=0,\quad }$

${\displaystyle P={\begin{bmatrix}0&0.5&0.5\\0&0&0\\0&0&0\end{bmatrix}},\quad \mu ={\begin{bmatrix}\mu _{1}(x_{1})\\\mu _{2}(x_{2})\\\mu _{3}(x_{3})\end{bmatrix}}={\begin{bmatrix}15\\12\\10\end{bmatrix}}{\text{ for all }}x_{i}>0}$

Тогда по теореме мы можем вычислить:

${\displaystyle \lambda =(I-P^{T})^{-1}a={\begin{bmatrix}1&0&0\\-0.5&1&0\\-0.5&0&1\end{bmatrix}}^{-1}{\begin{bmatrix}0.5\times 5\\0.5\times 5\\0\end{bmatrix}}={\begin{bmatrix}1&0&0\\0.5&1&0\\0.5&0&1\end{bmatrix}}{\begin{bmatrix}2.5\\2.5\\0\end{bmatrix}}={\begin{bmatrix}2.5\\3.75\\1.25\end{bmatrix}}}$

Согласно определению , имеем: ${\displaystyle \mathbf {Y} }$

${\displaystyle P(Y_{1}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {2.5}{15}}\right)^{n}\right)^{-1}={\frac {5}{6}}}$

${\displaystyle P(Y_{2}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {3.75}{12}}\right)^{n}\right)^{-1}={\frac {11}{16}}}$

${\displaystyle P(Y_{3}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {1.25}{10}}\right)^{n}\right)^{-1}={\frac {7}{8}}}$

Следовательно, вероятность того, что в каждом узле будет одно задание, равна:

${\displaystyle \pi (1,1,1)={\frac {5}{6}}\cdot {\frac {2.5}{15}}\cdot {\frac {11}{16}}\cdot {\frac {3.75}{12}}\cdot {\frac {7}{8}}\cdot {\frac {1.25}{10}}\approx 0.00326}$

Поскольку скорость обслуживания здесь не зависит от штата, s просто следуют геометрическому распределению . ${\displaystyle Y_{i}}$

Обобщенная сеть Джексона

Обобщенная сеть Джексона допускает процессы обновления прибытия , которые не обязательно должны быть процессами Пуассона, и независимые, одинаково распределенные неэкспоненциальные времена обслуживания. В общем случае эта сеть не имеет стационарного распределения в форме произведения , поэтому ищутся приближения. ^[13]

Броуновское приближение

При некоторых мягких условиях процесс длины очереди ^{[ необходимо разъяснение ]} открытой обобщенной сети Джексона может быть аппроксимирован отраженным броуновским движением, определяемым как , где — дрейф процесса, — ковариационная матрица, — матрица отражения. Это двухпорядковое приближение, полученное с помощью соотношения между общей сетью Джексона с однородной жидкой сетью и отраженным броуновским движением. ${\displaystyle Q(t)}$ ${\displaystyle \operatorname {RBM} _{Q(0)}(\theta ,\Gamma ;R).}$ ${\displaystyle \theta }$ ${\displaystyle \Gamma }$ ${\displaystyle R}$

Параметры отраженного броуновского процесса задаются следующим образом:

${\displaystyle \theta =\alpha -(I-P^{T})\mu }$

${\displaystyle \Gamma =(\Gamma _{k\ell }){\text{ with }}\Gamma _{k\ell }=\sum _{j=1}^{J}(\lambda _{j}\wedge \mu _{j})[p_{jk}(\delta _{k\ell }-p_{j\ell })+c_{j}^{2}(p_{jk}-\delta _{jk})(p_{j\ell }-\delta _{j\ell })]+\alpha _{k}c_{0,k}^{2}\delta _{k\ell }}$

${\displaystyle R=I-P^{T}}$

где символы определяются как:

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

• Сеть Гордона–Ньюэлла
• сеть БКМП
• G-сеть
• Закон Литтла

Ссылки

1. Walrand, J. ; Varaiya, P. (1980). «Времена пребывания и условие обгона в сетях Джексона». Advances in Applied Probability . 12 (4): 1000–1018. doi :10.2307/1426753. JSTOR  1426753.
2. Келли, Ф. П. (июнь 1976 г.). «Сети очередей». Advances in Applied Probability . 8 (2): 416–432. doi :10.2307/1425912. JSTOR  1425912.
3. Джексон, Джеймс Р. (декабрь 2004 г.). «Комментарии к «Системам очередей типа Jobshop»: Предыстория». Management Science . 50 (12): 1796–1802. doi :10.1287/mnsc.1040.0268. JSTOR  30046150.
4. Джексон, Джеймс Р. (октябрь 1963 г.). «Системы очередей типа Jobshop». Management Science . 10 (1): 131–142. doi :10.1287/mnsc.1040.0268. JSTOR  2627213.Версия от января 1963 года доступна по адресу http://www.dtic.mil/dtic/tr/fulltext/u2/296776.pdf Архивировано 12 апреля 2018 г. на Wayback Machine
5. Джексон, Дж. Р. (1957). «Сети очередей ожидания». Исследование операций . 5 (4): 518–521. doi :10.1287/opre.5.4.518. JSTOR  167249.
6. Джексон, Джеймс Р. (декабрь 2004 г.). «Системы очередей, подобные системам обслуживания заказов». Management Science . 50 (12): 1796–1802. doi :10.1287/mnsc.1040.0268. JSTOR  30046149.
7. Райх, Эдгар (сентябрь 1957 г.). «Время ожидания при очередях в тандеме». Annals of Mathematical Statistics . 28 (3): 768. doi : 10.1214/aoms/1177706889 . JSTOR  2237237.
8. Уолранд, Джин (ноябрь 1983 г.). «Вероятностный взгляд на сети квазиобратимых очередей». Труды IEEE по теории информации . 29 (6): 825. doi :10.1109/TIT.1983.1056762.
9. Джексон, РРП (1995). «Обзор книги: Сети очередей и формы продуктов: системный подход». Журнал IMA по управленческой математике . 6 (4): 382–384. doi :10.1093/imaman/6.4.382.
10. Гордон, У. Дж.; Ньюэлл, Г. Ф. (1967). «Закрытые системы очередей с экспоненциальными серверами». Исследование операций . 15 (2): 254. doi :10.1287/opre.15.2.254. JSTOR  168557.
11. Гудман, Джонатан Б.; Мэсси, Уильям А. (декабрь 1984 г.). «Неэргодическая сеть Джексона». Журнал прикладной вероятности . 21 (4): 860–869. doi :10.2307/3213702.
12. Walrand, J.; Varaiya, P. (декабрь 1980 г.). «Времена пребывания и условие обгона в сетях Джексона». Advances in Applied Probability . 12 (4): 1000–1018. doi :10.2307/1426753.
13. Чен, Хонг; Яо, Дэвид Д. (2001). Основы сетей массового обслуживания: производительность, асимптотика и оптимизация . Springer. ISBN 0-387-95166-0.