Сеть Джексона - Jackson network

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

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

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

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

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

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

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

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

Теорема

В открытой сети Джексона м M / M / 1 очереди где использование ${ displaystyle rho _ {я}}$ меньше 1 в каждой очереди, распределение вероятностей равновесного состояния существует и для состояния ${ 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})].}$

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

Определение

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

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

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

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

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

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

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

${ displaystyle { begin {align} & 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 {выровнено}}}$

куда ${ Displaystyle mathbf {е} _ {я}}$ обозначить ${ 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)}$

куда ${ Displaystyle M_ {я} (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}}$.⟩

Эта теорема расширяет показанную выше, допуская зависящую от состояния скорость обслуживания каждого узла. Это связано с распределением ${ 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 {для всех}} x_ {i}> 0}$

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

${ displaystyle lambda = (IP ^ {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} справа) ^ {- 1} = { frac {5} {6}}}$

${ Displaystyle P (Y_ {2} = 0) = left ( sum _ {n = 0} ^ { infty} left ({ frac {3.75} {12}} right) ^ {n} справа) ^ {- 1} = { frac {11} {16}}}$

${ Displaystyle P (Y_ {3} = 0) = left ( sum _ {n = 0} ^ { infty} left ({ frac {1.25} {10}} right) ^ {n} справа) ^ {- 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}} приблизительно 0,00326}$

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

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

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

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

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

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

${ Displaystyle тета = альфа - (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}}$

где символы определены как:

Определения символов в формуле аппроксимации

символ	Смысл
${ Displaystyle альфа = ( альфа _ {j}) _ {j = 1} ^ {J}}$	а J-вектор, определяющий скорость поступления на каждый узел.
${ Displaystyle му = ( му) _ {j = 1} ^ {J}}$	а J-вектор, определяющий скорость обслуживания каждого узла.
${ displaystyle P}$	матрица маршрутизации.
${ displaystyle lambda _ {j}}$	эффективное прибытие ${ displaystyle j ^ { text {th}}}$ узел.
${ displaystyle c_ {j}}$	изменение времени обслуживания в ${ displaystyle j ^ { text {th}}}$ узел.
${ displaystyle c_ {0, j}}$	изменение времени между прибытиями в ${ displaystyle j ^ { text {th}}}$ узел.
${ displaystyle delta _ {ij}}$	коэффициенты для определения корреляции между узлами. Они определены так: Пусть ${ Displaystyle А (т)}$ быть процессом прибытия системы, тогда ${ Displaystyle А (т) - альфа т {} приблизительно { шляпа {А}} (т)}$ в распределении, где ${ Displaystyle { шляпа {A}} (т)}$ - броуновский процесс без дрейфа с ковариантной матрицей ${ Displaystyle Gamma ^ {0} = ( Gamma _ {ij} ^ {0})}$, с ${ displaystyle Gamma _ {ij} ^ {0} = alpha _ {i} c_ {0, i} ^ {2} delta _ {ij}}$, для любого ${ displaystyle i, j in {1, dots, J }}$

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Июнь 2012 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

Рекомендации