Алгоритм Бузена

В теории массового обслуживания , дисциплине математической теории вероятностей , алгоритм Бьюзена (или алгоритм свертки ) представляет собой алгоритм вычисления константы нормализации G( N ) в теореме Гордона-Ньюэлла . Этот метод был впервые предложен Джеффри П. Бьюзеном в его докторской диссертации 1971 года. ^{[ 1 ]} и впоследствии опубликовано в рецензируемом журнале в 1973 году. ^{[ 2 ]} Вычисление G( N ) необходимо для вычисления стационарного распределения вероятностей замкнутой сети массового обслуживания. ^{[ 3 ]}

Выполнение простого вычисления нормализующей константы требует перечисления всех состояний. Для закрытой сети с N циркулирующими клиентами и M объектами обслуживания G( N ) представляет собой сумму ${\tbinom {N+M-1}{M-1}}$ отдельные члены, причем каждый член состоит из M факторов, возведенных в степени, сумма которых равна N . Алгоритм Бьюзена вычисляет G( N ), используя только NM умножения и сложения . Это радикальное улучшение открыло возможность применения теоремы Гордона-Ньюэлла к моделям реальных компьютерных систем, а также гибких производственных систем и других случаев, когда в сетях взаимосвязанных сервисных предприятий могут образовываться узкие места и очереди. ^{[ 4 ]} Значения G(1), G(2) ... G( N -1), которые можно использовать для расчета других важных интересующих величин, вычисляются как побочные продукты алгоритма.

Проблема с настройкой

Рассмотрим закрытую сеть массового обслуживания с M объектами обслуживания и N циркулирующими клиентами. Предположим, что время обслуживания клиента в пункте обслуживания i задано экспоненциально распределенной случайной величиной с параметром µ _i и что после завершения обслуживания в пункте обслуживания i клиент перейдет к пункту обслуживания j с вероятностью p _ij . ^{[ 3 ]}

Позволять $\mathbb {P} (n_{1},n_{2},\cdots ,n_{M})$ — стационарная вероятность того, что количество клиентов в пункте обслуживания i равно n _i для i = 1, 2, ..., M . следует Из теоремы Гордона–Ньюэлла , что

$\mathbb {P} (n_{1},n_{2},\cdots ,n_{M})={\frac {1}{{\text{G}}(N)}}$ $\left(X_{1}\right)^{n_{1}}$ $\left(X_{2}\right)^{n_{2}}$ .... $\left(X_{M}\right)^{n_{M}}$

Этот результат обычно записывают более компактно как

$\mathbb {P} (n_{1},n_{2},\cdots ,n_{M})={\frac {1}{{\text{G}}(N)}}\prod _{i=1}^{M}\left(X_{i}\right)^{n_{i}}$

Значения X _i определяются путем решения

$\mu _{j}X_{j}=\sum _{i=1}^{M}\mu _{i}X_{i}p_{ij}\quad {\text{ for }}j=1,\ldots ,M.$

G ( N ) — нормализующая константа, выбранная так, чтобы сумма всех ${\tbinom {N+M-1}{M-1}}$ значения $\mathbb {P} (n_{1},n_{2},\cdots ,n_{M})$ равен 1. Алгоритм Бьюзена представляет собой первую эффективную процедуру вычисления G( N ). ^{[ 2 ]}^{[ 4 ]}

Описание алгоритма

Отдельные члены, которые необходимо сложить вместе для вычисления G( N ), имеют следующую форму:

$\left(X_{1}\right)^{n_{1}}$ $\left(X_{2}\right)^{n_{2}}$ .... $\left(X_{M}\right)^{n_{M}}$ . Обратите внимание, что этот набор терминов можно разделить на две группы. В первую группу входят все члены, у которых показатель степени $\left(X_{M}\right)$ больше или равно 1. Это означает, что $\left(X_{M}\right)$ возведенное в степень 1, можно вычесть из каждого из этих членов.

После разложения $\left(X_{M}\right)$ , возникает неожиданный результат: модифицированные термины в первой группе идентичны терминам, используемым для вычисления константы нормализации для той же сети с одним удаленным клиентом. Таким образом, сумму слагаемых первой группы можно записать как « X _M раз G( N -1)». Это понимание обеспечивает основу для разработки алгоритма. ^{[ 4 ]}

Далее рассмотрим вторую группу. Показатель X _M для каждого члена этой группы равен нулю. В результате объект обслуживания M фактически исчезает из всех членов этой группы (поскольку он в каждом случае уменьшается в 1 раз). общее количество клиентов на остальных объектах обслуживания М -1 остается равным N. В результате Во вторую группу входят все возможные расположения этих N клиентов.

Чтобы точно выразить эту концепцию, предположим, что X ₁ , X ₂ , … X _M были получены для данной сети с M сервисными средствами. Для любых n ≤ N и m ≤ M определите g( n,m ) как нормализующую константу для сети с n клиентами, m объектами обслуживания (1,2, … m ) и значениями X ₁ , X ₂ , … X _m , которые соответствуют первым m членам исходной последовательности X ₁ , X ₂ , … X _M .

Учитывая это определение, сумму членов второй группы теперь можно записать как g( N , M -1).

Отсюда сразу же следует, что « X _M раз G( N -1)», сумму слагаемых первой группы, можно переписать как « X _M раз g( N -1, M )».

Кроме того, нормализующую константу G( N ) в теореме Гордона-Ньюэлла теперь можно переписать как g( N , M ).

Поскольку G( N ) равна сумме членов первой и второй групп,

G( N ) = g( N , M ) = X _M g( N -1, M ) + g( N , M -1)

очевидно, существует для любого промежуточного значения n от 1 до N и для любого промежуточного значения m от 1 до M. Это же рекуррентное соотношение ,

Отсюда следует, что g( n,m ) = X _m g( n -1, m ) + g( n,m -1). Алгоритм Бьюзена — это просто итеративное применение этого фундаментального рекуррентного соотношения вместе со следующими граничными условиями.

g(0, m ) = 1 для m = 1, 2, … M

г( п ,1) знак равно ( Икс _я ) ^н для n = 0, 1, … N

Предельные распределения, ожидаемое количество клиентов

Теорема Гордона-Ньюэлла позволяет аналитикам определить стационарную вероятность, связанную с каждым отдельным состоянием закрытой сети массового обслуживания. Эти отдельные вероятности затем необходимо сложить вместе, чтобы оценить другие важные вероятности. Например, P( n _i ≥ k ), вероятность того, что общее количество клиентов в сервисном центре i больше или равно k , должна суммироваться по всем значениям n _i ≥ k и для каждого такого значения n _i , всеми возможными способами оставшиеся N – n _i клиентов могут быть распределены по другим центрам обслуживания M -1 в сети.

Многие из этих предельных вероятностей можно вычислить с минимальными дополнительными усилиями. В этом легко убедиться для случая P( n _i ≥ k). Очевидно, что X _i необходимо возвести в степень k или выше в каждом штате, где число клиентов в сервисном центре i больше или равно k . Таким образом, X _i ^к можно вычесть из каждой из этих вероятностей, оставив набор модифицированных вероятностей, сумма которых определяется выражением G( N -k)/G( N ). Это наблюдение приводит к следующему простому и весьма эффективному результату:

п ( п _я ≥ k ) знак равно ( Икс _я ) ^к Г( Н - к )/Г( Н )

Затем это соотношение можно использовать для расчета предельных распределений и ожидаемого количества клиентов в каждом пункте обслуживания.

$\mathbb {P} (n_{i}=k)={\frac {X_{i}^{k}}{G(N)}}[G(N-k)-X_{i}G(N-k-1)]\quad {\text{ for }}k=0,1,\ldots ,N-1,$

$\mathbb {P} (n_{i}=N)={\frac {X_{i}^{N}}{G(N)}}.$

Ожидаемое количество клиентов в сервисном центре i определяется выражением

$\mathbb {E} (n_{i})=\sum _{k=1}^{N}X_{i}^{k}{\frac {G(N-k)}{G(N)}}.$

Эти характеристики интересующих величин в терминах G( n ) также принадлежат Бьюзену. ^{[ 2 ]}

Выполнение

Предполагается, что X _m были вычислены путем решения соответствующих уравнений и доступны в качестве входных данных для нашей программы. Хотя g( n,m ) в принципе является двумерной матрицей, ее можно вычислить по столбцам, начиная с верхней части крайнего левого столбца и спускаясь по каждому столбцу до самого низа, прежде чем перейти к следующему столбцу справа. . Процедура использует один вектор-столбец C для представления текущего столбца g .

Первый цикл алгоритма ниже инициализирует вектор-столбец C[n] так, что C[0] = 1 и C(n) = 0 для n≥1. Обратите внимание, что C[0] остается равным 1 на всех последующих итерациях.

Во втором цикле каждое последовательное значение C(n) для n≥1 устанавливается равным соответствующему значению g( n,m) по мере продвижения алгоритма вниз по столбцу m. Это достигается путем установки каждого последующего значения C(n) равным:

g( n,m-1 ) плюс X _m раз g( n-1,m ).

Обратите внимание, что g( n,m-1 ) — это предыдущее значение C(n), а g( n-1,m ) — текущее значение C(n-1).

C[0] := 1
for n := 1 step 1 until N do
   C[n] := 0;

for m := 1 step 1 until M do
  for n := 1 step 1 until N do
     C[n] := C[n] + X[m]*C[n-1];

По завершении окончательные значения C[n] соответствуют столбцу M в матрице g( n,m ). Таким образом, они представляют собой искомые значения G (0), G (1),..., G (N) . ^{[ 2 ]}

Ссылки

^ Бюзен, JP (1 августа 1971 г.). DTIC AD0731575: Модели сетей массового обслуживания при мультипрограммировании .
^ Перейти обратно: ^а ^б ^с ^д Бюзен, JP (1973). «Вычислительные алгоритмы для закрытых сетей массового обслуживания с экспоненциальными серверами» (PDF) . Коммуникации АКМ . 16 (9): 527–531. дои : 10.1145/362342.362345 . S2CID 10702 . Архивировано из оригинала (PDF) 13 мая 2016 г. Проверено 15 апреля 2006 г.
^ Перейти обратно: ^а ^б Гордон, WJ; Ньюэлл, Г. Ф. (1967). «Закрытые системы массового обслуживания с экспоненциальными серверами». Исследование операций . 15 (2): 254. doi : 10.1287/opre.15.2.254 . JSTOR 168557 .
^ Перейти обратно: ^а ^б ^с Деннинг, Питер Дж. (24 августа 2016 г.). «Переосмысление случайности: интервью с Джеффом Бьюзеном, часть I» . Вездесущность . 2016 (август): 1:1–1:17. дои : 10.1145/2986329 .

[:0-1] Бюзен, JP (1 августа 1971 г.). DTIC AD0731575: Модели сетей массового обслуживания при мультипрограммировании .

[buzen-1973-2] Перейти обратно: ^а ^б ^с ^д Бюзен, JP (1973). «Вычислительные алгоритмы для закрытых сетей массового обслуживания с экспоненциальными серверами» (PDF) . Коммуникации АКМ . 16 (9): 527–531. дои : 10.1145/362342.362345 . S2CID 10702 . Архивировано из оригинала (PDF) 13 мая 2016 г. Проверено 15 апреля 2006 г.

[gn-3] Перейти обратно: ^а ^б Гордон, WJ; Ньюэлл, Г. Ф. (1967). «Закрытые системы массового обслуживания с экспоненциальными серверами». Исследование операций . 15 (2): 254. doi : 10.1287/opre.15.2.254 . JSTOR 168557 .

[:1-4] Перейти обратно: ^а ^б ^с Деннинг, Питер Дж. (24 августа 2016 г.). «Переосмысление случайности: интервью с Джеффом Бьюзеном, часть I» . Вездесущность . 2016 (август): 1:1–1:17. дои : 10.1145/2986329 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

v т и Теория массового обслуживания
Одиночные узлы массового обслуживания	Очередь Д/М/1 Очередь М/Д/1 Очередь М/Д/Ц Очередь М/М/1 Теорема Берка Очередь М/М/Ц Очередь М/М/∞ Очередь M/G/1 Формула Поллачека – Хинчина Матричный аналитический метод Очередь M/G/k Очередь G/M/1 Очередь G/G/1 Формула Кингмана Уравнение Линдли Разветвить очередь – присоединиться к ней Массовая очередь
Процессы прибытия	Точный процесс Пуассона Марковский процесс прибытия Рациональный процесс прибытия
Сети массового обслуживания	Сеть Джексона Уравнения дорожного движения Теорема Гордона – Ньюэлла Анализ среднего значения Алгоритм Бузена сеть Келли G-сеть Сеть BCMP
Политика обслуживания	ФИФО ЛИФО Совместное использование процессора Круговой Самая короткая работа следующая Кратчайшее оставшееся время
Ключевые понятия	Цепь Маркова с непрерывным временем Обозначения Кендалла Закон Литтла Решение в форме продукта Уравнение баланса Квазиобратимость Потоко-эквивалентный серверный метод Теорема о прибытии Метод разложения метод Бенеша
Предельные теоремы	Предел жидкости Теория среднего поля Приближение интенсивного движения Отраженное броуновское движение
Расширения	Жидкая очередь Многоуровневая сеть массового обслуживания Система опроса Состязательная сеть массового обслуживания Сеть потерь Очередь повторных попыток
Информационные системы	Буфер данных Эрланг (единица измерения) Распределение Эрланга Управление потоком (данные) Очередь сообщений Перегрузка сети Сетевой планировщик Конвейер (программное обеспечение) Качество обслуживания Планирование (вычисления) Телетрафик инжиниринг
Категория