Анализ среднего значения

В теории массового обслуживания , дисциплине математической теории вероятностей , анализ среднего значения ( MVA ) — это рекурсивный метод расчета ожидаемой длины очереди, времени ожидания в узлах очередей и пропускной способности в равновесии для замкнутой разделимой системы очередей. Первые приближенные методы были независимо опубликованы Швейцером. и Бард, позже последовала точная версия Лавенберга и Райзера, опубликованная в 1980 году.

Он основан на теореме прибытия , которая утверждает, что когда один клиент в закрытой системе с M -клиентами прибывает в пункт обслуживания, он / она наблюдает, что остальная часть системы находится в состоянии равновесия для системы с M - 1 клиентами.

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

Рассмотрим замкнутую сеть массового обслуживания из K очередей M/M/1 с M клиентами, циркулирующими в системе. Предположим, что клиенты неотличимы друг от друга, так что в сети имеется один класс клиентов. Для расчета средней длины очереди и времени ожидания на каждом из узлов, а также пропускной способности системы мы используем итерационный алгоритм, начиная с сети с 0 клиентами.

Запишите µ _i для скорости обслуживания в узле i и P для матрицы маршрутизации клиентов, где элемент p _ij обозначает вероятность того, что клиент, завершающий обслуживание в узле i, перейдет в узел j для обслуживания. Чтобы использовать алгоритм, мы сначала вычисляем вектор-строку коэффициента посещений v , вектор такой, что v = v P.

Теперь напишите L _i ( n ) для среднего количества клиентов в очереди i , когда всего в системе n клиентов (включая задание, обслуживаемое в данный момент в очереди i ), и W _j ( n ) для среднего затраченного времени. клиентом в очереди i, всего n когда в системе клиентов. Обозначим пропускную способность системы с m клиентами через λ _m .

Алгоритм

Алгоритм начинается с пустой сети (ноль клиентов), затем увеличивает количество клиентов на 1 на каждой итерации, пока не появится необходимое количество ( M в системе ) клиентов.

Для инициализации установите L _k (0) = 0 для k = 1,..., K . (Это устанавливает нулевую среднюю длину очереди в системе без клиентов на всех узлах.)

Повторите для m = 1,..., M :

1. Для k = 1,..., K вычислите время ожидания в каждом узле, используя теорему прибытия:

$W_{k}(m)={\frac {1+L_{k}\left(m-1\right)}{\mu _{k}}}.$

2. Затем вычислите пропускную способность системы, используя закон Литтла :

$\lambda _{m}={\frac {m}{\sum _{k=1}^{K}W_{k}(m)v_{k}}}.$

3. Наконец, используйте закон Литтла, примененный к каждой очереди, чтобы вычислить среднюю длину очереди для k = 1, ..., K:

$L_{k}(m)=v_{k}\lambda _{m}W_{k}(m).$

Конец повтора.

Метод Барда – Швейцера

Приближение Барда – Швейцера оценивает среднее количество рабочих мест в узле k следующим образом:

$L_{k}(m-1)\approx {\frac {m-1}{m}}L_{k}(m)$

что является линейной интерполяцией. Из приведенных выше формул это приближение дает соотношения с фиксированной точкой , которые можно решить численно. Этот итеративный подход часто называют приблизительным MVA (AMVA) и обычно он быстрее, чем рекурсивный подход MVA.

Псевдокод

набор L _k ( м ) = M / K

повторять до схождения:

$\lambda _{m}={\frac {m}{\sum _{k=1}^{K}{\frac {{\frac {m-1}{m}}L_{k}(m)+1}{\mu _{k}}}v_{k}}}$

$L_{k}(m)=v_{k}\lambda _{m}{\frac {{\frac {m-1}{m}}L_{k}(m)+1}{\mu _{k}}}$

Мультиклассовые сети

В случае многоклассовых сетей с R классами заявок каждая очередь k может иметь разные скорости обслуживания µ _k,r для каждого класса заданий r=1,...,R , хотя в случае очереди в порядке очереди существуют определенные ограничения. -обслуживаемые станции в силу условий теоремы BCMP в многоклассовом случае.

Время ожидания W _k,r, которое испытывают задания класса r в очереди k, по-прежнему можно связать с общей средней длиной очереди в узле k, используя обобщение теоремы о прибытии:

$W_{k,r}(\mathbb {m} )={\frac {1+L_{k}\left(\mathbb {m} -1_{r}\right)}{\mu _{k,r}}}.$

где $\mathbb {m} =(m_{1},\ldots ,m_{R})$ представляет собой вектор совокупности клиентов для классов R и $1_{r}$ вычитает единицу из r -го элемента $\mathbb {m}$, предполагая, что $m_{r}\geq 1$.

Для сетей с одним классом клиентов алгоритм MVA очень быстр, и затрачиваемое время растет линейно с количеством клиентов и количеством очередей. Однако в многоклассовых моделях количество операций умножения и сложения, а также требования к памяти для MVA растут экспоненциально с увеличением числа классов клиентов. Практически алгоритм хорошо работает для 3-4 классов клиентов, хотя это обычно зависит от реализации и структуры модели. Например, метод Tree-MVA можно масштабировать до более крупных моделей, если матрица маршрутизации разрежена.

Точные значения средних показателей производительности можно получить в больших моделях с помощью метода моментов , для которого требуется логарифмически квадратичное время. Метод моментов позволяет на практике решать модели, содержащие до 10 классов требований, а иногда и больше, которые обычно недоступны с помощью точного MVA. Однако этот метод не использует теорему прибытия и основан на решении систем линейных уравнений, включающих нормировочную константу вероятностей состояний сети массового обслуживания.

Приближенные алгоритмы MVA (AMVA), такие как метод Барда-Швейцера, вместо этого предлагают альтернативный метод решения, который обеспечивает низкую сложность также в многоклассовых сетях и обычно дает очень точные результаты.

Расширения

Алгоритм анализа среднего значения был применен к классу моделей PEPA , описывающих сети массового обслуживания и производительность центра распределения ключей .

Программное обеспечение

• JMVA — инструмент, написанный на Java и реализующий MVA.
• queuing — библиотека для GNU Octave , включающая MVA.
• Line , набор инструментов MATLAB, который включает в себя точные и приблизительные алгоритмы MVA.

См. также

• Теория массового обслуживания

Внешние ссылки

• Дж. Виртамо: Сети массового обслуживания . Раздаточный материал от Helsinki Tech дает хороший обзор теоремы Джексона и MVA.
• Саймон Лам: Простое развитие алгоритма MVA . Показывает связь между алгоритмом Бьюзена и MVA.