Сеть BCMP

В теории массового обслуживания , дисциплине математической теории вероятностей , сеть BCMP — это класс сети массового обслуживания , для которого существует равновесное распределение по форме продукта . Она названа в честь авторов статьи, в которой впервые была описана сеть: Баскетта , Чанди , Мунца и Паласиоса. Теорема является существенным расширением сети Джексона, допускающей практически произвольную маршрутизацию клиентов и распределение времени обслуживания в зависимости от конкретных дисциплин обслуживания.

Статья хорошо известна, и в 1990 году эта теорема была описана Дж. Майклом Харрисоном и Рут Дж. Уильямс как «одно из плодотворных достижений теории массового обслуживания за последние 20 лет» .

Определение сети BCMP

Сеть из m взаимосвязанных очередей называется сетью BCMP, если каждая из очередей относится к одному из следующих четырех типов:

1. Дисциплина FCFS , при которой все клиенты имеют одинаковое отрицательное экспоненциальное распределение времени обслуживания. Скорость обслуживания может зависеть от состояния, поэтому напишите $\scriptstyle {\mu _{j}}$ для скорости обслуживания, когда длина очереди равна j .
2. Очереди совместного использования процессора
3. Бесконечные очереди серверов
4. LCFS с упреждающим резюме (работа не потеряна)

В последних трёх случаях распределения времени обслуживания должны иметь рациональные преобразования Лапласа . Это означает, что преобразование Лапласа должно иметь вид

$L(s)={\frac {N(s)}{D(s)}}.$

Также должны быть соблюдены следующие условия.

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

Теорема

Для сети BCMP из m очередей, которая является открытой, закрытой или смешанной, в которой каждая очередь имеет тип 1, 2, 3 или 4, вероятности состояния равновесия определяются выражением

$\pi (x_{1},x_{2},\ldots ,x_{m})=C\pi _{1}(x_{1})\pi _{2}(x_{2})\cdots \pi _{m}(x_{m}),$

где C — нормировочная константа, выбранная так, чтобы сумма вероятностей состояния равновесия была равна 1 и $\scriptstyle {\pi _{i}(\cdot )}$ представляет равновесное распределение для очереди i .

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

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

Питер Дж. Харрисон предложил альтернативное доказательство. рассматривая обратные процессы.