В теории массового обслуживания , дисциплине в рамках математической теории вероятностей , алгоритм Бузена (или алгоритм свертки ) представляет собой алгоритм для вычисления нормировочной константы G ( N ) в теореме Гордона – Ньюэлла . Этот метод был впервые предложен Джеффри П. Бузеном в 1973 году. [1] Вычисление G ( N ) требуется для вычисления стационарного распределения вероятностей замкнутой сети массового обслуживания. [2]
Выполнение наивного вычисления нормирующей константы требует перечисления всех состояний. Для системы с N работами и M состояниями существуюткомбинации. Алгоритм Buzen в "вычисляет G (1), G (2), ..., G ( N ) , используя в общей сложности NM умножений и NM дополнений." Это значительное улучшение, позволяющее проводить вычисления в гораздо более крупных сетях. [1]
Настройка проблемы
Рассмотрим замкнутую сеть массового обслуживания с M обслуживающими устройствами и N обращающимися запросами. Напишите n i ( t ) для количества клиентов, присутствующих в i- м учреждении в момент времени t , так что. Мы предполагаем, что время обслуживания заявки на i- м предприятии задается экспоненциально распределенной случайной величиной с параметром μ i, и что после завершения обслуживания на i- м предприятии заявитель перейдет к j- му объекту с вероятностью p ij . [2]
Из теоремы Гордона – Ньюэлла следует, что равновесное распределение этой модели имеет вид
где X i находятся путем решения
и G ( N ) - нормирующая константа, выбранная так, чтобы сумма вышеуказанных вероятностей равнялась 1. [1]
Алгоритм Бузена - эффективный метод вычисления G ( N ). [1]
Описание алгоритма
Запишите g ( N , M ) для нормирующей константы замкнутой сети массового обслуживания с N обращающимися заявками и M станциями обслуживания. Алгоритм начинается с решения указанных выше соотношений для X i, а затем устанавливается начальные условия [1]
Рекуррентное соотношение [1]
используется для вычисления сетки значений. Искомое значение G ( N ) = g ( N , M ). [1]
Маржинальные распределения, ожидаемое количество клиентов
Коэффициенты g ( n , m ), вычисленные с использованием алгоритма Бузена, также могут использоваться для вычисления маржинальных распределений и ожидаемого количества клиентов в каждом узле.
ожидаемое количество клиентов на объекте i на
Выполнение
Предполагается, что X m были вычислены путем решения соответствующих уравнений и доступны в качестве входных данных для нашей процедуры. Хотя g в принципе является двумерной матрицей, ее можно вычислить по столбцу за столбцом, начиная с самого левого столбца. Подпрограмма использует один вектор-столбец C для представления текущего столбца g .
C [ 0 ] : = 1 для n : = 1 шаг 1, пока N не выполнит C [ n ] : = 0 ;для m : = 1 шаг 1 до тех пор, пока M не выполнит для n : = 1 шаг 1, пока N не сделает C [ n ] : = C [ n ] + X [ m ] * C [ n - 1 ] ;
По завершении C содержит желаемые значения от G (0), от G (1) до G (N) . [1]
Рекомендации
- ^ Б с д е е г ч Buzen, JP (1973). «Вычислительные алгоритмы для замкнутых сетей массового обслуживания с экспоненциальными серверами» (PDF) . Коммуникации ACM . 16 (9): 527. DOI : 10,1145 / 362342,362345 .
- ^ а б Гордон, WJ; Ньюэлл, Г. Ф. (1967). «Замкнутые системы массового обслуживания с экспоненциальными серверами». Исследование операций . 15 (2): 254. DOI : 10,1287 / opre.15.2.254 . JSTOR 168557 .