Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Определение [ править ]

Очередь со стационарным распределением является quasireversible , если ее состояние в момент времени т , х (т) не зависит от

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

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

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

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

тогда, учитывая только клиентов определенного класса, процессы прибытия и отправления являются одним и тем же процессом Пуассона (с параметром ), поэтому

где M x - такой набор, который означает, что состояние x ' представляет собой единственное прибытие конкретного класса потребителей в состояние x .

Примеры [ править ]

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

См. Также [ править ]

Ссылки [ править ]

  1. ^ Muntz, Р. Р. (1972). Пуассоновский процесс вылета и сети очередей (IBM Research Report RC 4145) (Технический отчет). Йорктаун-Хайтс, штат Нью-Йорк: Исследовательский центр IBM Томаса Дж. Ватсона.
  2. Перейти ↑ Kelly, FP (1975). «Сети очередей с разными типами клиентов». Журнал прикладной теории вероятностей . 12 (3): 542–554. DOI : 10.2307 / 3212869 . JSTOR 3212869 . 
  3. Перейти ↑ Kelly, FP (1976). «Сети очередей». Достижения в прикладной теории вероятностей . 8 (2): 416–432. DOI : 10.2307 / 1425912 . JSTOR 1425912 . 
  4. ^ Харрисон, Питер Г .; Патель, Нареш М. (1992). Моделирование производительности сетей связи и компьютерных архитектур . Эддисон-Уэсли. п. 288 . ISBN 0-201-54419-9.
  5. Перейти ↑ Kelly, FP (1982). Сети квазиобратимых узлов . В прикладной теории вероятностей и информатике: интерфейс (Ральф Л. Дисней и Теунис Дж. Отт, редакторы). 1 3-29. Биркхойзер, Бостон
  6. ^ Чао, X .; Миядзава, М .; Серфозо, РФ; Такада, Х. (1998). «Марковские сетевые процессы с продуктом из стационарных распределений». Системы массового обслуживания . 28 (4): 377. DOI : 10,1023 / A: 1019115626557 .
  7. Перейти ↑ Kelly, FP, Reversibility and Stochastic Networks , 1978, страницы 66-67.
  8. Перейти ↑ Burke, PJ (1956). «Выход системы массового обслуживания» . Исследование операций . 4 (6): 699–704. DOI : 10.1287 / opre.4.6.699 .
  9. Перейти ↑ Burke, PJ (1968). "Процесс вывода стационарной системы массового обслуживания M / M / s" . Летопись математической статистики . 39 (4): 1144–1152. DOI : 10.1214 / АОМ / 1177698238 .
  10. ^ О'Коннелл, N .; Йор, М. (декабрь 2001 г.). «Броуновские аналоги теоремы Берка». Случайные процессы и их приложения . 96 (2): 285–298. DOI : 10.1016 / S0304-4149 (01) 00119-3 .
  11. Перейти ↑ Kelly, FP (1979). Обратимость и стохастические сети . Нью-Йорк: Вили.
  12. ^ Дао-Тхи, TH; Майресс, Дж. (2005). «Нулевые автоматические очереди». Формальные методы для компьютерных систем и бизнес-процессов . Конспект лекций по информатике. 3670 . п. 64. DOI : 10.1007 / 11549970_6 . ISBN 978-3-540-28701-8.