Fluid queue

В теории массового обслуживания, дисциплине в рамках математической теории вероятностей, жидкостная очередь (жидкостная модель, модель потока жидкости или модель стохастической жидкости ) - математическая модель, используемая для описания уровня жидкости в резервуаре с учетом случайно определенных периодов наполнения и опорожнения. Термин теория плотины использовался в более ранней литературе для этих моделей. Модель использовалась для аппроксимации дискретных моделей, моделирования распространения лесных пожаров, в теории разорения и в режиме l высокоскоростные сети передачи данных. Модель применяет алгоритм дырявого ведра к стохастическому источнику.

Модель была впервые представлена ​​Пэт Моран в 1954 году, когда рассматривалась модель с дискретным временем. Гибкие очереди позволяют поступать непрерывно, а не дискретно, как в таких моделях, как очереди M / M / 1 и M / G / 1.

Гибкие очереди использовались для моделирования производительности сетевой коммутатор, маршрутизатор, протокол IEEE 802.11, асинхронный режим передачи (технология, предназначенная для B-ISDN ), одноранговый обмен файлами, оптическая коммутация пакетов, а также находит применение в гражданском строительстве при проектировании плотин. Этот процесс тесно связан с процессами квазирождения – смерти, для которых известны эффективные методы решения.

• 1 Описание модели
• 2 Стационарное распределение
  • 2.1 Вкл / выкл модель
• 3 Период занятости
  • 3.1 Пример
  • 3.2 Уровень потерь
  • 3.3 Горный процесс
• 4 Сети очередей жидкости
• 5 Очереди жидкости обратной связи
• 6 Очереди жидкости второго порядка
• 7 Внешние ссылки
• 8 Ссылки

Очередь жидкости можно рассматривать как большой резервуар, обычно предполагаемый бесконечной вместимостью, соединенный с рядом труб, по которым жидкость поступает в резервуар и ряд насосов, удаляющих жидкость из резервуара. Оператор управляет трубами и насосами, контролируя скорость, с которой жидкость поступает в буфер, и скорость, с которой жидкость выходит. Когда оператор переводит систему в состояние i, мы пишем r i для обозначения чистой скорости поступления жидкости в этом состоянии (ввод без вывода). Когда буфер содержит жидкость, если мы запишем X (t) для уровня жидкости в момент времени t,

$d\; X\; (t)\; dt\; =\; \{ri,\; если\; X\; (t)>0\; max\; (ri,\; 0),\; если\; X\; (t)\; =\; 0.\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{\backslash \; mathrm\; \{d\}\; X\; (t)\}\; \{\backslash \; mathrm\; \{d\}\; t\}\}\; =\; \{\backslash \; begin\; \{cases\}\; r\_\; \{i\}\; \{\backslash \; text\; \{if\}\}\; X\; (t)>0\; \backslash \backslash \backslash \; max\; (r\_\; \{i\},\; 0)\; \{\backslash \; text\; \{if\}\}\; X\; (t)\; =\; 0.\; \backslash \; end\; \{cases\}\}\}$

Оператор представляет собой цепь Маркова с непрерывным временем и обычно называется процессом среды, фоновым процессом или движением. Поскольку процесс X представляет уровень жидкости в буфере, он может принимать только неотрицательные значения.

Модель представляет собой особый тип кусочно-детерминированного марковского процесса и также может быть рассматривается как марковская модель вознаграждения с граничными условиями.

Стационарное распределение - это фаза-t Распределение типа, как впервые было показано Асмуссеном, может быть вычислено с использованием матрично-аналитических методов.

Метод аддитивного разложения численно устойчив и разделяет собственные значения, необходимые для вычисления с использованием разложения Шура.

Вкл / от модели

Для простой системы, в которой обслуживание имеет постоянную скорость μ, а поступление колеблется между скоростью λ и 0 (в состояниях 1 и 2 соответственно) в соответствии с цепью Маркова с непрерывным временем с генератором матрица

$Q\; =\; (-\; \alpha \; \alpha \; \beta \; -\; \beta )\; \{\backslash \; displaystyle\; Q\; =\; \{\backslash \; begin\; \{pmatrix\}\; -\; \backslash \; alpha\; \backslash \; alpha\; \backslash \backslash \backslash \; beta\; -\; \backslash \; beta\; \backslash \; end\; \{pmatrix\}\}\}$

стационарное распределение может быть вычислено в явном виде и определяется выражением

$F\; (x,\; 1)\; =\; \beta \; \alpha \; +\; \beta \; (1\; -\; e\; (\beta \; \mu \; -\; \alpha \; \lambda \; -\; \mu )\; x)\; \{\backslash \; displaystyle\; F\; (x,\; 1)\; =\; \{\; \backslash \; frac\; \{\backslash \; beta\}\; \{\backslash \; alpha\; +\; \backslash \; beta\}\}\; \backslash \; left\; (1-e\; ^\; \{\backslash \; left\; (\{\backslash \; frac\; \{\backslash \; beta\}\; \{\backslash \; mu\}\}\; -\; \{\backslash \; frac\; \{\backslash \; alpha\}\; \{\backslash \; lambda\; -\; \backslash \; mu\}\}\; \backslash \; right)\; x\}\; \backslash \; right)\}$

$F\; (x,\; 2)\; =\; \alpha \; \alpha \; +\; \beta \; -\; \beta \; (\lambda \; -\; \mu )\; \alpha \; +\; \beta \; e\; (\beta \; \mu \; -\; \alpha \; \lambda \; -\; \mu )\; x\; \{\backslash \; displaystyle\; F\; (x,\; 2)\; =\; \{\backslash \; frac\; \{\backslash \; alpha\}\; \{\backslash \; alpha\; +\; \backslash \; beta\}\}\; -\; \{\backslash \; frac\; \{\backslash \; beta\}\; \backslash \; left\; (\backslash \; lambda\; -\; \backslash \; mu\; \backslash \; right)\}\; \{\backslash \; alpha\; +\; \backslash \; beta\}\}\; e\; ^\; \{\backslash \; left\; (\{\backslash \; frac\; \{\backslash \; beta\}\; \{\backslash \; mu\}\}\; -\; \{\backslash \; frac\; \{\backslash \; alpha\}\; \{\backslash \; lambda\; -\; \backslash \; mu\}\}\; \backslash \; right)\; x\}\}$

и средний уровень жидкости

$(\lambda \; -\; \mu )\; \beta \; (\mu \; (\alpha \; +\; \beta )\; -\; \beta \; \lambda )\; (\alpha \; +\; \beta )\; (\mu ,\; \lambda \; -\; \mu ).\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{(\backslash \; lambda\; -\; \backslash \; mu)\; \backslash \; beta\}\; \{(\backslash \; mu\; (\backslash \; alpha\; +\; \backslash \; beta)\; -\; \backslash \; beta\; \backslash \; lambda)\; (\backslash \; alpha\; +\; \backslash \; beta)\}\}\; (\backslash \; mu,\; \backslash \; lambda\; -\; \backslash \; mu).\}$

Период занятости - это период времени, измеряемый с момента, когда жидкость впервые поступает в буфер (X (t) становится ненулевым), пока буфер снова не станет пустой (X (t) возвращается к нулю). В более ранней литературе его иногда называют влажным периодом (плотины). Преобразование Лапласа – Стилтьеса распределения периодов занятости известно для жидкой очереди с бесконечным буфером и ожидаемого периода занятости в случае конечного буфера и поступлений в виде мгновенных скачков. 56>

Для бесконечного буфера с постоянной скоростью обслуживания μ и поступлениями со скоростью λ и 0, модулированной цепью Маркова с непрерывным временем с параметрами

$Q\; =\; (-\; \alpha \; \alpha \; \beta \; -\; \beta )\; \{\backslash \; displaystyle\; Q\; =\; \{\; \backslash \; begin\; \{pmatrix\}\; -\; \backslash \; alpha\; \backslash \; alpha\; \backslash \backslash \backslash \; beta\; -\; \backslash \; beta\; \backslash \; end\; \{pmatrix\}\}\}$

записываем W * (s) для преобразования Лапласа – Стилтьеса распределения периодов занятости, тогда

$W\; \ast \; (s)\; =\; \beta \; \lambda \; +\; s\; \lambda \; -\; \beta \; \mu \; +\; \alpha \; \mu \; -\; 4\; \beta \; \alpha \; \mu \; (\mu \; -\; \lambda )\; +\; (s\; \lambda \; +\; \beta \; (\lambda \; -\; \mu )\; +\; \alpha \; \mu )\; 2\; 2\; \beta \; (\lambda \; -\; \mu )\; \{\backslash \; displaystyle\; W\; ^\; \{\backslash \; ast\}\; (s)\; =\; \{\backslash \; frac\; \{\backslash \; beta\; \backslash \; lambda\; +\; s\; \backslash \; lambda\; -\; \backslash \; beta\; \backslash \; mu\; +\; \backslash \; alpha\; \backslash \; mu\; -\; \{\backslash \; sqrt\; \{4\; \backslash \; beta\; \backslash \; alpha\; \backslash \; mu\; (\backslash \; му\; -\; \backslash \; лямбда)\; +\; (с\; \backslash \; лямбда\; +\; \backslash \; бета\; (\backslash \; лямбда\; -\; \backslash \; му)\; +\; \backslash \; альфа\; \backslash \; му)\; ^\; \{2\}\}\}\}\; \{2\; \backslash \; бета\; (\backslash \; лямбда\; -\; \backslash \; му)\}\}\}$

что дает среднее значение период занятости

$E\; (W)\; =\; \lambda \; \alpha \; \mu \; +\; \beta \; (\lambda \; -\; \mu ).\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{E\}\; (W)\; =\; \{\backslash \; frac\; \{\backslash \; lambda\}\; \{\backslash \; alpha\; \backslash \; mu\; +\; \backslash \; beta\; (\backslash \; lambda\; -\; \backslash \; mu)\}\}.\}$

В данном случае одного включения / При отключенном источнике распределение периодов занятости, как известно, является функцией убывающей частоты отказов, что означает, что периоды занятости, означающие, что чем дольше длился период занятости, тем дольше он, вероятно, продлится.

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

Пример

Например, если постоянная очередь со скоростью обслуживания μ = 2 питается от двухпозиционного источника с параметрами α = 2, β = 1 и λ = 3, тогда очередь жидкости имеет период занятости со средним значением 1 и дисперсией 5/3.

Скорость потерь

В конечном буфере скорость, с которой жидкость теряется (отклоняется из системы из-за полного буфера), может быть вычислена с использованием преобразований Лапласа-Стилтьеса.

Горный процесс

Термин горный процесс был придуман для описания максимального значения процесса содержимого буфера, достигаемого в период занятости, и может быть вычислен с использованием результатов из очереди G / M / 1.

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

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

Жидкие очереди второго порядка (иногда называемые марковскими модулированными диффузионными процессами или жидкими очередями с броуновским шумом) рассматривают отраженное броуновское движение с параметрами, управляемыми марковским процессом. Обычно рассматриваются два разных типа граничных условий: поглощающие и отражающие.

• BuTools, MATLAB, Python и Реализация некоторых из вышеперечисленных результатов в системе Mathematica.
• PevaTools, MATLAB код для многорежимных моделей
• Учебное пособие по моделям потока жидкости от В. Рамасвами на MAM8