✖


Jump to content

Решение в форме продукта

    Add links

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

    где B — некоторая константа. Решения такого вида представляют интерес, поскольку их оценка при больших значениях n не требует больших вычислительных затрат . Такие решения в сетях массового обслуживания важны для поиска показателей производительности в моделях многопрограммных компьютерных систем с разделением времени.

    Равновесные распределения

    [ редактировать ]

    Первые решения в виде произведения были найдены для равновесных распределений цепей Маркова . Тривиально, модели, состоящие из двух или более независимых подкомпонентов, демонстрируют решение в форме продукта по определению независимости. Первоначально этот термин использовался в сетях массового обслуживания , подкомпонентами которых были отдельные очереди. Например, теорема Джексона дает совместное равновесное распределение открытой сети массового обслуживания как произведение равновесных распределений отдельных очередей. [1] После многочисленных расширений, в основном сети BCMP, считалось, что локальный баланс является требованием для решения в форме продукта. [2] [3]

    Геленбе Модель G-сети была первой, которая показала, что это не так. Движимый необходимостью смоделировать биологические нейроны, которые имеют точечный процесс, подобный импульсному поведению, он представил предшественника G-сетей, назвав его случайной нейронной сетью . [4] Введя «негативных клиентов», которые могут уничтожить или устранить других клиентов, он обобщил семейство продуктовых сетей. [5] Затем это было расширено в несколько этапов, сначала с помощью «триггеров» Геленбе, которые представляют собой клиентов, которые имеют право перемещать других клиентов из одной очереди в другую. [6] Еще одной новой формой клиентов, которая также привела к формированию продукта, стала «партийная распродажа» Геленбе. [7] Это было дополнительно расширено Эролом Геленбе и Жаном-Мишелем Фурно с помощью типов клиентов, называемых «сбросами», которые могут моделировать устранение сбоев: когда очередь достигает пустого состояния, представляющего (например) сбой, длина очереди может вернуться назад или быть «сброшен» к своему устойчивому распределению прибывшим клиентом сброса, что представляет собой ремонт. Все эти предыдущие типы клиентов в G-Networks могут существовать в одной сети, в том числе с несколькими классами, и все вместе они по-прежнему приводят к решению в форме продукта, выводя нас далеко за пределы обратимых сетей, которые рассматривались ранее. [8]

    Решения в форме продукта иногда описываются как «станции, независимые в равновесии». [9] Решения в форме продукта также существуют в сетях массовых очередей . [10]

    Дж. М. Харрисон и Р. Дж. Уильямс отмечают, что «практически все модели, которые были успешно проанализированы в классической теории сетей массового обслуживания, представляют собой модели, имеющие так называемое стационарное распределение в форме продукта» [9] Совсем недавно были опубликованы решения в форме произведения для алгебр марковских процессов (например, RCAT в PEPA [11] [12] ) и стохастические сети Петри . [13] [14] Теорема Мартина Фейнберга о нулевом дефиците дает достаточное условие для того, чтобы сети химических реакций демонстрировали стационарное распределение в форме продукта. [15]

    Работа Геленбе также показывает, что продукт G-Networks можно использовать для моделирования случайных нейронных сетей с резкими скачками , и, кроме того, такие сети можно использовать для аппроксимации ограниченных и непрерывных функций с действительным знаком. [16] [17]

    Распределение времени пребывания

    [ редактировать ]

    Термин «форма продукта» также использовался для обозначения распределения времени пребывания в циклической системе массового обслуживания, где время, затрачиваемое заданиями на M узлах, определяется как произведение времени, проведенного на каждом узле. [18] В 1957 году Райх показал результат для двух очередей M/M/1 . последовательно соединенных [19] позже расширив это до n очередей M/M/1 в тандеме [20] и было показано, что это применимо к путям без обгона в сетях Джексона . [21] Уолранд и Варайя предполагают, что отсутствие обгона (когда клиенты не могут обогнать других клиентов, выбрав другой маршрут через сеть) может быть необходимым условием сохранения результата. [21] Митрани предлагает точные решения для некоторых простых сетей с обгоном, показывая, что ни одна из них не демонстрирует распределения времени пребывания в форме продукта. [22]

    Для закрытых сетей Чоу показал результат для двух сервисных узлов: [23] который позже был обобщен до цикла очередей [24] и для обгона свободных путей в сетях Гордона–Ньюэлла . [25] [26]

    Расширения

    [ редактировать ]
    • Приблизительные решения в форме продукта вычисляются с учетом независимых предельных распределений, которые при некоторых условиях могут дать хорошее приближение к стационарному распределению. [27] [28]
    • Решения в форме полупродукта — это решения, в которых распределение может быть записано как продукт, где термины имеют ограниченную функциональную зависимость от глобального пространства состояний, которое можно аппроксимировать. [29]
    • Решения в форме квазипродукта либо
      • решения, которые не являются произведением предельных плотностей, но предельные плотности описывают распределение по типу продукта. [30] или
      • приближенная форма для переходных распределений вероятностей, которая позволяет аппроксимировать переходные моменты. [31]

    Ссылки

    [ редактировать ]
    1. ^ Джексон, Джеймс Р. (1963). «Системы массового обслуживания, подобные цеху». Наука управления . 10 (1): 131–142. дои : 10.1287/mnsc.10.1.131 .
    2. ^ Бушери, Ричард Дж.; ван Дейк, Нью-Мексико (1994). «Локальный баланс в сетях массового обслуживания с положительными и отрицательными заявками» . Анналы исследования операций . 48 (5): 463–492. дои : 10.1007/BF02033315 . hdl : 1871/12327 . S2CID   15599820 .
    3. ^ Чанди, К. Мани ; Ховард, Дж. Х. младший; Таусли, Д.Ф. (1977). «Форма продукта и локальный баланс в сетях массового обслуживания» . Журнал АКМ . 24 (2): 250–263. дои : 10.1145/322003.322009 . S2CID   6218474 .
    4. ^ Геленбе, Эрол (1989). «Случайные нейронные сети с отрицательными и положительными сигналами и решение в форме продукта». Нейронные вычисления . 1 (4): 502–510. дои : 10.1162/neco.1989.1.4.502 . S2CID   207737442 .
    5. ^ Геленбе, Эрол (1991). «Продуктовые сети массового обслуживания с отрицательными и положительными заявками» . Журнал прикладной вероятности . 28 (3): 656–663. дои : 10.2307/3214499 . JSTOR   3214499 .
    6. ^ Геленбе, Эрол (1993). «G-сети с триггерным движением клиентов». Журнал прикладной вероятности . 30 (3): 742–748. дои : 10.2307/3214781 . JSTOR   3214781 .
    7. ^ Геленбе, Эрол (1993). «G-Networks с активным движением клиентов». Вероятность в инженерных и информационных науках . 7 (3): 335–342. дои : 10.1017/S0269964800002953 .
    8. ^ Геленбе, Эрол ; Фурно, Жан-Мишель (2002). «G-Networks со сбросами». Оценка производительности . 49 (1): 179–191. дои : 10.1016/S0166-5316(02)00127-X .
    9. ^ Jump up to: а б Харрисон, Дж. М .; Уильямс, Р.Дж. (1992). «Броуновские модели сетей массового обслуживания с прямой связью: квазиобратимость и решения в форме продукта». Анналы прикладной теории вероятности . 2 (2): 263–293. CiteSeerX   10.1.1.56.1572 . дои : 10.1214/aoap/1177005704 .
    10. ^ Хендерсон, В.; Тейлор, П.Г. (1990). «Форма продукта в сетях очередей с пакетными поступлениями и пакетными обслуживаниями». Системы массового обслуживания . 6 : 71–87. дои : 10.1007/BF02411466 . S2CID   30949152 .
    11. ^ Хиллстон, Дж .; Томас, Н. (1999). «Решение формы продукта для класса моделей PEPA» (PDF) . Оценка производительности . 35 (3–4): 171–192. дои : 10.1016/S0166-5316(99)00005-X . hdl : 20.500.11820/13c57018-5854-4f34-a4c9-833262a71b7c .
    12. ^ Харрисон, П.Г. (2003). «Поворот времени вспять в алгебре марковских процессов» . Теоретическая информатика . 290 (3): 1947–2013. дои : 10.1016/S0304-3975(02)00375-4 . Архивировано из оригинала 15 октября 2006 г. Проверено 29 августа 2015 г.
    13. ^ Марин, А.; Бальзамо, С.; Харрисон, П.Г. (2012). «Анализ стохастических сетей Петри с сигналами». Оценка производительности . 69 (11): 551–572. дои : 10.1016/j.peva.2012.06.003 . hdl : 10044/1/14180 .
    14. ^ Мерес, Ж.; Нгуен, ХТ (2009). «Сети Петри с нулевым дефицитом и форма продукта». Приложения и теория сетей Петри . Конспекты лекций по информатике. Том. 5606. с. 103. CiteSeerX   10.1.1.745.1585 . дои : 10.1007/978-3-642-02424-5_8 . ISBN  978-3-642-02423-8 .
    15. ^ Андерсон, DF; Крачун, Г.; Курц, Т.Г. (2010). «Стационарные распределения продуктов в форме для сетей химических реакций с нулевым дефицитом». Бюллетень математической биологии . 72 (8): 1947–1970. arXiv : 0803.3042 . дои : 10.1007/s11538-010-9517-4 . ПМИД   20306147 . S2CID   2204856 .
    16. ^ Геленбе, Эрол (1993). «Обучение в рекуррентной случайной нейронной сети». Нейронные вычисления . 5 (1): 154–164. дои : 10.1162/neco.1993.5.1.154 . S2CID   38667978 .
    17. ^ Геленбе, Эрол ; Мао, Чжи-Хун; Ли, Ян-Да (1991). «Аппроксимация функции случайной нейронной сетью». Транзакции IEEE в нейронных сетях . 10 (1): 3–9. CiteSeerX   10.1.1.46.7710 . дои : 10.1109/72.737488 . ПМИД   18252498 .
    18. ^ Боксма, Огайо ; Келли, ФП ; Конхейм, AG (январь 1984 г.). «Форма продукта для распределения времени пребывания в циклических экспоненциальных очередях» . Журнал АКМ . 31 (1): 128–133. дои : 10.1145/2422.322419 . S2CID   6770615 .
    19. ^ Райх, Эдгар (1957). «Время ожидания в тандемных очередях» . Анналы математической статистики . 28 (3): 768–773. дои : 10.1214/aoms/1177706889 .
    20. ^ Райх, Э. (1963). «Примечание об очередях в тандеме» . Анналы математической статистики . 34 : 338–341. дои : 10.1214/aoms/1177704275 .
    21. ^ Jump up to: а б Уолранд, Дж .; Варайя, П. (1980). «Sojourn Times и условия обгона в джексоновских сетях». Достижения в области прикладной теории вероятности . 12 (4): 1000–1018. дои : 10.2307/1426753 . JSTOR   1426753 .
    22. ^ Митрани, И. (1985). «Проблемы времени отклика в сетях связи». Журнал Королевского статистического общества. Серия Б (Методическая) . 47 (3): 396–406. дои : 10.1111/j.2517-6161.1985.tb01368.x . JSTOR   2345774 .
    23. ^ Чоу, Ве-Мин (апрель 1980 г.). «Распределение времени цикла экспоненциальных циклических очередей» . Журнал АКМ . 27 (2): 281–286. дои : 10.1145/322186.322193 . S2CID   14084475 .
    24. ^ Шассбергер, Р.; Дадуна, Х. (1983). «Время обхода цикла экспоненциальных очередей» . Журнал АКМ . 30 : 146–150. дои : 10.1145/322358.322369 . S2CID   33401212 .
    25. ^ Дадуна, Х. (1982). «Время прохождения путей без обгона в сетях Гордона-Ньюэлла». Достижения в области прикладной теории вероятности . 14 (3): 672–686. дои : 10.2307/1426680 . JSTOR   1426680 .
    26. ^ Келли, ФП ; Поллетт, ПК (1983). «Время пребывания в закрытых сетях массового обслуживания». Достижения в области прикладной теории вероятности . 15 (3): 638–656. дои : 10.2307/1426623 . JSTOR   1426623 .
    27. ^ Байнат, Б.; Даллери, Ю. (1993). «Единый взгляд на методы аппроксимации формы продукта для общих закрытых сетей массового обслуживания». Оценка производительности . 18 (3): 205–224. дои : 10.1016/0166-5316(93)90017-О .
    28. ^ Даллери, Ю.; Цао, XR (1992). «Операционный анализ стохастических замкнутых сетей массового обслуживания». Оценка производительности . 14 : 43–61. дои : 10.1016/0166-5316(92)90019-D .
    29. ^ Томас, Найджел; Харрисон, Питер Г. (2010). «Государственные ставки и полупродуктовая форма посредством обратного процесса». Инженерия производительности компьютеров . Конспекты лекций по информатике. Том. 6342. с. 207. дои : 10.1007/978-3-642-15784-4_14 . ISBN  978-3-642-15783-7 .
    30. ^ Дембицкий, К.; Дикер, AB; Рольски, Т. (2007). «Формы квазипродукта для жидкостных сетей, управляемых Леви». Математика исследования операций . 32 (3): 629–647. arXiv : math/0512119 . дои : 10.1287/moor.1070.0259 . S2CID   16150704 .
    31. ^ Ангиус, А.; Хорват, А.С.; Вольф, В. (2013). «Приблизительный анализ переходных процессов сетей массового обслуживания с помощью форм квазипродуктов». Методы и приложения аналитического и стохастического моделирования . Конспекты лекций по информатике. Том. 7984. с. 22. дои : 10.1007/978-3-642-39408-9_3 . ISBN  978-3-642-39407-2 .
    Retrieved from "https://en.wikipedia.org/w/index.php?title=Product-form_solution&oldid=1186333939"
    Arc.Ask3.Ru: конец переведенного документа.
    Arc.Ask3.Ru
    Номер скриншота №: 0b24a663f158273c77db44175376c5a9__1700644620
    URL1:https://arc.ask3.ru/arc/aa/0b/a9/0b24a663f158273c77db44175376c5a9.html
    Заголовок, (Title) документа по адресу, URL1:
    Product-form solution - Wikipedia
    Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)