Квазиобратимость

В теории массового обслуживания , дисциплине математической теории вероятностей , квазиобратимость (иногда QR ) является свойством некоторых очередей. Эта концепция была впервые сформулирована Ричардом Р. Манцем. ^[1] и далее развит Фрэнком Келли . ^[2]^[3] Квазиобратимость отличается от обратимости тем, что на скорости поступления налагается более сильное условие, а на потоки вероятностей — более слабое. Например, очередь M/M/1 с зависящей от состояния скоростью поступления и зависящим от состояния временем обслуживания является обратимой, но не квазиобратимой. ^[4]

Сеть очередей, в которой каждая отдельная очередь, рассматриваемая изолированно, является квазиобратимой, всегда имеет продукта . форму стационарного распределения ^[5] Предполагалось, что квазиобратимость является необходимым условием решения формы продукта в сети массового обслуживания, но было показано, что это не так. Чао и др. продемонстрировали сеть продуктовой формы, в которой квазиобратимость не была соблюдена. ^[6]

Определение

Очередь со стационарным распределением $\pi$ является квазиобратимым , если его состояние в момент времени t , x (t) не зависит от

время прибытия для каждого класса клиентов после момента времени t ,
время отправления для каждого класса клиентов до момента времени t

для всех классов клиентов. ^[7]

Формулировка частичного баланса

Квазиобратимость эквивалентна особой форме частичного равновесия . Сначала определите обратные ставки q'( x , x' ) по формуле

\pi (\mathbf {x} )q'(\mathbf {x} ,\mathbf {x'} )=\pi (\mathbf {x'} )q(\mathbf {x'} ,\mathbf {x} )

тогда, если рассматривать только клиентов определенного класса, процессы прибытия и ухода представляют собой один и тот же процесс Пуассона (с параметром $\alpha$ ), так

\alpha =\sum _{\mathbf {x'} \in M_{\mathbf {x} }}q(\mathbf {x} ,\mathbf {x'} )=\sum _{\mathbf {x'} \in M_{\mathbf {x} }}q'(\mathbf {x} ,\mathbf {x'} )

где M _x — множество такое, что $\scriptstyle {\mathbf {x'} \in M_{\mathbf {x} }}$ означает, что состояние x' представляет собой однократное прибытие определенного класса клиентов в состояние x .

Примеры

Теорема Берка показывает, что система массового обслуживания M/M/m квазиобратима. ^[8]^[9]^[10]
Келли показал, что каждая станция сети BCMP квазиобратима, если рассматривать ее изолированно. ^[11]
G-очереди в G-сетях квазиобратимы. ^[12]

См. также

Обратимость времени

Ссылки

^ Мунц, Р.Р. (1972). Пуассоновский процесс отправления и сети массового обслуживания (Отчет об исследовании IBM RC 4145) (Технический отчет). Йорктаун-Хайтс, Нью-Йорк: Исследовательский центр IBM Томаса Дж. Уотсона.
^ Келли, ФП (1975). «Сети очередей с клиентами разных типов». Журнал прикладной вероятности . 12 (3): 542–554. дои : 10.2307/3212869 . JSTOR 3212869 . S2CID 51917794 .
^ Келли, ФП (1976). «Сети очередей». Достижения в области прикладной теории вероятности . 8 (2): 416–432. дои : 10.2307/1425912 . JSTOR 1425912 . S2CID 204177645 .
^ Харрисон, Питер Г .; Патель, Нареш М. (1992). Моделирование производительности сетей связи и компьютерных архитектур . Аддисон-Уэсли. п. 288 . ISBN 0-201-54419-9 .
^ Келли, ФП (1982). Сети квазиреверсивных узлов. Архивировано 21 февраля 2007 г. на Wayback Machine . В книге «Прикладная теория вероятности и информатика: интерфейс» (Ральф Л. Дисней и Теунис Дж. Отт, редакторы) 1 3-29. Биркхойзер, Бостон
^ Чао, X.; Миядзава, М.; Серфозо, РФ; Такада, Х. (1998). «Марковские сетевые процессы с продуктами образуют стационарные распределения». Системы массового обслуживания . 28 (4): 377. doi : 10.1023/A:1019115626557 . S2CID 14471818 .
^ Келли, Ф.П., Реверсивность и стохастические сети. Архивировано 19 января 2023 г. в Wayback Machine , 1978 г., страницы 66-67.
^ Берк, П.Дж. (1956). «Результаты системы массового обслуживания». Исследование операций . 4 (6): 699–704. дои : 10.1287/opre.4.6.699 . S2CID 55089958 .
^ Берк, П.Дж. (1968). «Процесс вывода стационарной системы массового обслуживания M/M/s» . Анналы математической статистики . 39 (4): 1144–1152. дои : 10.1214/aoms/1177698238 .
^ О'Коннелл, Н.; Йор, М. (декабрь 2001 г.). «Броуновские аналоги теоремы Берка» . Случайные процессы и их приложения . 96 (2): 285–298. дои : 10.1016/S0304-4149(01)00119-3 .
^ Келли, ФП (1979). Обратимость и стохастические сети . Нью-Йорк: Уайли. Архивировано из оригинала 05 февраля 2012 г. Проверено 2 декабря 2011 г.
^ Дао-Тхи, TH; Майрес, Дж. (2005). «Нулевые автоматические очереди». Формальные методы для компьютерных систем и бизнес-процессов . Конспекты лекций по информатике. Том. 3670. с. 64. дои : 10.1007/11549970_6 . ISBN 978-3-540-28701-8 .

[1] Мунц, Р.Р. (1972). Пуассоновский процесс отправления и сети массового обслуживания (Отчет об исследовании IBM RC 4145) (Технический отчет). Йорктаун-Хайтс, Нью-Йорк: Исследовательский центр IBM Томаса Дж. Уотсона.

[2] Келли, ФП (1975). «Сети очередей с клиентами разных типов». Журнал прикладной вероятности . 12 (3): 542–554. дои : 10.2307/3212869 . JSTOR 3212869 . S2CID 51917794 .

[3] Келли, ФП (1976). «Сети очередей». Достижения в области прикладной теории вероятности . 8 (2): 416–432. дои : 10.2307/1425912 . JSTOR 1425912 . S2CID 204177645 .

[4] Харрисон, Питер Г .; Патель, Нареш М. (1992). Моделирование производительности сетей связи и компьютерных архитектур . Аддисон-Уэсли. п. 288 . ISBN 0-201-54419-9 .

[5] Келли, ФП (1982). Сети квазиреверсивных узлов. Архивировано 21 февраля 2007 г. на Wayback Machine . В книге «Прикладная теория вероятности и информатика: интерфейс» (Ральф Л. Дисней и Теунис Дж. Отт, редакторы) 1 3-29. Биркхойзер, Бостон

[6] Чао, X.; Миядзава, М.; Серфозо, РФ; Такада, Х. (1998). «Марковские сетевые процессы с продуктами образуют стационарные распределения». Системы массового обслуживания . 28 (4): 377. doi : 10.1023/A:1019115626557 . S2CID 14471818 .

[7] Келли, Ф.П., Реверсивность и стохастические сети. Архивировано 19 января 2023 г. в Wayback Machine , 1978 г., страницы 66-67.

[8] Берк, П.Дж. (1956). «Результаты системы массового обслуживания». Исследование операций . 4 (6): 699–704. дои : 10.1287/opre.4.6.699 . S2CID 55089958 .

[9] Берк, П.Дж. (1968). «Процесс вывода стационарной системы массового обслуживания M/M/s» . Анналы математической статистики . 39 (4): 1144–1152. дои : 10.1214/aoms/1177698238 .

[10] О'Коннелл, Н.; Йор, М. (декабрь 2001 г.). «Броуновские аналоги теоремы Берка» . Случайные процессы и их приложения . 96 (2): 285–298. дои : 10.1016/S0304-4149(01)00119-3 .

[11] Келли, ФП (1979). Обратимость и стохастические сети . Нью-Йорк: Уайли. Архивировано из оригинала 05 февраля 2012 г. Проверено 2 декабря 2011 г.

[12] Дао-Тхи, TH; Майрес, Дж. (2005). «Нулевые автоматические очереди». Формальные методы для компьютерных систем и бизнес-процессов . Конспекты лекций по информатике. Том. 3670. с. 64. дои : 10.1007/11549970_6 . ISBN 978-3-540-28701-8 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

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