Дискретно-событийное моделирование

Моделирование дискретных событий ( DES ) моделирует работу системы как ( дискретную ) последовательность событий во времени. Каждое событие происходит в определенный момент времени и знаменует собой изменение состояния системы. ^[1] Предполагается, что между последовательными событиями в системе не происходит никаких изменений; таким образом, время моделирования может напрямую перейти к времени возникновения следующего события, которое называется временной прогрессией следующего события .

В дополнение к прогрессу времени следующего события существует также альтернативный подход, называемый инкрементным прогрессом времени , при котором время разбивается на небольшие интервалы времени, а состояние системы обновляется в соответствии с набором событий/действий, происходящих в интервале времени. ^[2] Поскольку не обязательно моделировать каждый временной интервал, моделирование времени следующего события обычно может выполняться быстрее, чем соответствующее моделирование с приращением времени.

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

Пример

Обычное упражнение в обучении построению моделирования дискретных событий — это моделирование системы массового обслуживания , например, когда клиенты приходят к кассиру банка, чтобы их обслуживал служащий. В этом примере системными объектами являются Customer и Teller , а системными событиями — Customer-Arrival , Service-Start и Service-End . Каждое из этих событий имеет свою собственную динамику, определяемую следующими процедурами событий:

Когда происходит событие прибытия клиента переменной состояния , длина очереди увеличивается на 1, и если переменная состояния кассира имеет значение «доступно», запуска обслуживания последующее событие должно произойти без каких-либо задержек. так что вновь прибывший клиент будет обслужен немедленно.
Когда происходит событие начала обслуживания , переменная состояния кассира-статуса устанавливается на «занято», а последующее событие окончания обслуживания запланировано с задержкой (полученной из выборки времени обслуживания ). случайной величины
Когда происходит событие окончания обслуживания переменной состояния , длина очереди уменьшается на 1 (что означает уход клиента). переменной состояния Если длина очереди по-прежнему больше нуля, Service-Start последующее событие должно произойти без каких-либо задержек. В противном случае переменная состояния кассира-статуса имеет значение «доступен».

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

Компоненты

Состояние

Состояние системы — это набор переменных, который отражает основные свойства изучаемой системы. Траектория состояния во времени S(t) может быть математически представлена ступенчатой функцией , значение которой может меняться всякий раз, когда происходит событие.

Часы

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

Список событий

Моделирование поддерживает по крайней мере один список событий моделирования. Иногда его называют набором ожидающих событий , поскольку в нем перечислены события, которые ожидаются в результате ранее смоделированного события, но сами еще не смоделированы. Событие описывается временем, в которое оно происходит, и типом, указывающим код, который будет использоваться для моделирования этого события. Обычно код события параметризуется, и в этом случае описание события также содержит параметры для кода события. ^{[ нужна ссылка ]} Список событий также называется списком будущих событий (FEL) или набором будущих событий (FES). ^[3]^[4]^[5]^[6]

Когда события происходят мгновенно, действия, продолжающиеся во времени, моделируются как последовательности событий. Некоторые среды моделирования позволяют указывать время события в виде интервала, указывая время начала и время окончания каждого события. ^{[ нужна ссылка ]}

Однопоточные механизмы моделирования, основанные на мгновенных событиях, имеют только одно текущее событие. Напротив, механизмы многопоточного моделирования и механизмы моделирования, поддерживающие модель событий на основе интервалов, могут иметь несколько текущих событий. В обоих случаях имеются существенные проблемы с синхронизацией текущих событий. ^{[ нужна ссылка ]}

Набор ожидающих событий обычно организуется в виде приоритетной очереди , отсортированной по времени события. ^[7] То есть независимо от порядка добавления событий в набор событий, они удаляются строго в хронологическом порядке. Различные реализации очереди приоритетов были изучены в контексте моделирования дискретных событий; ^[8] Изученные альтернативы включали в себя деревья воспроизведения , списки пропуска , календарные очереди , ^[9] и лестничные очереди. ^[10]^[11]На машинах с массовым параллелизмом , таких как многоядерные или многоядерные процессоры, набор ожидающих событий может быть реализован с использованием неблокирующих алгоритмов , чтобы снизить стоимость синхронизации между параллельными потоками. ^[12]^[13]

Обычно события планируются динамически по ходу моделирования. Например, в приведенном выше примере банка событие CUSTOMER-ARRIVAL в момент времени t, если CUSTOMER_QUEUE было пустым, а TELLER был в режиме ожидания, включало бы создание последующего события CUSTOMER-DEPARTURE, которое должно произойти в момент t+s, где s — это число, сгенерированное из распределения SERVICE-TIME. ^{[ нужна ссылка ]}

Генераторы случайных чисел

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

Одна из проблем с распределениями случайных чисел, используемыми в моделировании дискретных событий, заключается в том, что стационарные распределения времен событий могут быть неизвестны заранее. В результате первоначальный набор событий, помещенный в набор ожидающих событий, не будет иметь время прибытия, соответствующее установившемуся распределению. Эта проблема обычно решается путем начальной загрузки имитационной модели. Прилагаются лишь ограниченные усилия для назначения реалистичного времени начальному набору ожидающих событий. Однако эти события планируют дополнительные события, и со временем распределение времени событий приближается к устойчивому состоянию. Это называется начальной загрузкой имитационной модели. При сборе статистики из работающей модели важно либо игнорировать события, которые происходят до достижения устойчивого состояния, либо запускать моделирование достаточно долго, чтобы поведение начальной загрузки было подавлено поведением устойчивого состояния. (Такое использование термина «бутстреп» можно противопоставить его использованию как в статистика и вычисления ).

Статистика

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

Конечное условие

Поскольку события загружаются, теоретически моделирование дискретных событий может выполняться вечно. Таким образом, разработчик моделирования должен решить, когда моделирование закончится. Типичными вариантами являются «во время t», «после обработки n событий» или, в более общем смысле, «когда статистическая мера X достигает значения x».

Трехэтапный подход

Пидд (1998) предложил трехэтапный подход к моделированию дискретных событий. В этом подходе первая фаза заключается в переходе к следующему хронологическому событию. Второй этап — выполнение всех событий, которые безусловно происходят в этот момент (они называются B-событиями). Третий этап — выполнение всех событий, которые условно происходят в этот момент (они называются C-событиями). Трехэтапный подход представляет собой усовершенствованный подход, основанный на событиях, при котором одновременные события упорядочиваются таким образом, чтобы наиболее эффективно использовать компьютерные ресурсы. Трехфазный подход используется в ряде коммерческих пакетов программного обеспечения для моделирования, но с точки зрения пользователя особенности базового метода моделирования обычно скрыты.

Обычное использование

Диагностика проблем процесса

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

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

Больничные приложения

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

Идеи по улучшению производительности лабораторных испытаний

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

Оценка решений о капитальных вложениях

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

Сетевые симуляторы

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

См. также

Подходы к системному моделированию:

Конечные автоматы и цепи Маркова.
Стохастический процесс и частный случай, марковский процесс.
Теория массового обслуживания и, в частности, процесс рождения и смерти.
Спецификация системы дискретных событий
Моделирование на уровне транзакций (TLM)

Вычислительные методы:

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

Дисциплины:

Ссылки

^ Стюарт Робинсон (2004). Моделирование – практика разработки и использования моделей . Уайли.
^ Матлофф, Норм. «Введение в дискретно-событийное моделирование и язык SimPy» (PDF) . Проверено 24 января 2013 г.
^ Пак, Хёнук; Фишвик, Пол А. (2010). «Среда приложений на базе графического процессора, поддерживающая быстрое моделирование дискретных событий» . Моделирование . 86 (10): 613–628. дои : 10.1177/0037549709340781 . ISSN 0037-5497 . S2CID 9731021 .
^ Данненберг, Роджер. «Введение в дискретно-событийное моделирование» . Школа компьютерных наук Карнеги-Меллона . Проверено 11 марта 2022 г.
^ Гюнеш, Месут. «Глава 3: Общие принципы» (PDF) . Свободный университет Берлина . Проверено 11 марта 2022 г.
^ Дамерджи, Халим; Глинн, Питер В. (1998). «Теория пределов для моделирования производительности алгоритмов набора будущих событий» . Наука управления . 44 (12): 1709–1722. дои : 10.1287/mnsc.44.12.1709 . ISSN 0025-1909 . JSTOR 2634704 .
^ Дуглас В. Джонс , изд. Реализации времени , Материалы 18-й зимней конференции по моделированию, 1986 г.
^ Дуглас В. Джонс , Эмпирическое сравнение реализаций очереди приоритетов и наборов событий , Сообщения ACM, 29 апреля 1986 г., страницы 300–311.
^ Ка Леонг Тан и Ли-Джин Тнг, Очередь календаря SNOOPy , Материалы 32-й зимней конференции по моделированию, 2000 г.
^ Дикман, Том; Гупта, Сунак; Уилси, Филип А. (2013). «Структуры пулов событий для PDES в многоядерных кластерах Beowulf». Материалы конференции ACM SIGSIM 2013 г. по принципам расширенного дискретного моделирования — SIGSIM-PADS '13 . п. 103. дои : 10.1145/2486092.2486106 . ISBN 9781450319201 . S2CID 17572839 .
^ Фурфаро, Анджело; Сакко, Людовика (2018). «Адаптивная лестничная очередь». Материалы конференции ACM SIGSIM 2018 года по принципам расширенного дискретного моделирования — SIGSIM-PADS '18 . стр. 101–104. дои : 10.1145/3200921.3200925 . ISBN 9781450350921 . S2CID 21699926 .
^ Маротта, Ромоло; Янни, Мауро; Пеллегрини, Алессандро; Квалья, Франческо (2017). «Конфликтоустойчивая календарная очередь без блокировки для масштабируемых платформ PDES с общим доступом ко всему». Материалы конференции ACM SIGSIM 2017 года по принципам расширенного дискретного моделирования — SIGSIM-PADS '17 . стр. 15–26. дои : 10.1145/3064911.3064926 . hdl : 11573/974295 . ISBN 9781450344890 . S2CID 30460497 .
^ Линден, Джонатан; Йонссон, Бенгт (2013). «Очередь с параллельным приоритетом на основе скип-листа с минимальной конкуренцией за память». Материалы конференции 2013 года по принципам распределенных систем — OPODIS 2013 . стр. 206–220. дои : 10.1007/978-3-319-03850-6_15 . ISBN 9783319038490 .
^ Джон Дж. Форбус; Дэниел Берлеант (2022). «Моделирование дискретных событий в учреждениях здравоохранения: обзор» . Моделирование . 3 (4): 417–433. arXiv : 2211.00061 . doi : 10.3390/modelling3040027 .

Дальнейшее чтение

Майрон Х. МакДугалл (1987). Моделирование компьютерных систем: методы и инструменты . МТИ Пресс. ISBN 9780262132299 .
Уильям Делани; Эрминия Ваккари (1988). Динамические модели и дискретное моделирование событий . Деккер ИНК.
Роджер В. Макхейни (1991). Компьютерное моделирование: практический аспект . Академическая пресса.
Майкл Пидд (1998). Компьютерное моделирование в науке управления – четвертое издание . Уайли.
А, Алан Прицкер, Джин Дж. О'Рейли (1999). Моделирование с помощью Visual SLAM и AweSim . Уайли. {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
Аверилл М. Лоу; В. Дэвид Келтон (2000). Имитационное моделирование и анализ – третье издание . МакГроу-Хилл.
Бернард П. Зейглер; Герберт Прехофер; Таг Гон Ким (2000). Теория моделирования и симуляции: Интеграция дискретно-событийных и непрерывных сложных динамических систем – второе издание . Академическая пресса.
Джерри Бэнкс; Джон Карсон; Барри Нельсон; Дэвид Никол (2005). Моделирование дискретно-событийных систем – четвертое издание . Пирсон.
Джеймс Дж. Нутаро (2010). Создание программного обеспечения для моделирования: теория и алгоритмы с приложениями на C++ . Уайли.

[1] Стюарт Робинсон (2004). Моделирование – практика разработки и использования моделей . Уайли.

[matloff-2] Матлофф, Норм. «Введение в дискретно-событийное моделирование и язык SimPy» (PDF) . Проверено 24 января 2013 г.

[3] Пак, Хёнук; Фишвик, Пол А. (2010). «Среда приложений на базе графического процессора, поддерживающая быстрое моделирование дискретных событий» . Моделирование . 86 (10): 613–628. дои : 10.1177/0037549709340781 . ISSN 0037-5497 . S2CID 9731021 .

[4] Данненберг, Роджер. «Введение в дискретно-событийное моделирование» . Школа компьютерных наук Карнеги-Меллона . Проверено 11 марта 2022 г.

[5] Гюнеш, Месут. «Глава 3: Общие принципы» (PDF) . Свободный университет Берлина . Проверено 11 марта 2022 г.

[6] Дамерджи, Халим; Глинн, Питер В. (1998). «Теория пределов для моделирования производительности алгоритмов набора будущих событий» . Наука управления . 44 (12): 1709–1722. дои : 10.1287/mnsc.44.12.1709 . ISSN 0025-1909 . JSTOR 2634704 .

[7] Дуглас В. Джонс , изд. Реализации времени , Материалы 18-й зимней конференции по моделированию, 1986 г.

[8] Дуглас В. Джонс , Эмпирическое сравнение реализаций очереди приоритетов и наборов событий , Сообщения ACM, 29 апреля 1986 г., страницы 300–311.

[9] Ка Леонг Тан и Ли-Джин Тнг, Очередь календаря SNOOPy , Материалы 32-й зимней конференции по моделированию, 2000 г.

[10] Дикман, Том; Гупта, Сунак; Уилси, Филип А. (2013). «Структуры пулов событий для PDES в многоядерных кластерах Beowulf». Материалы конференции ACM SIGSIM 2013 г. по принципам расширенного дискретного моделирования — SIGSIM-PADS '13 . п. 103. дои : 10.1145/2486092.2486106 . ISBN 9781450319201 . S2CID 17572839 .

[11] Фурфаро, Анджело; Сакко, Людовика (2018). «Адаптивная лестничная очередь». Материалы конференции ACM SIGSIM 2018 года по принципам расширенного дискретного моделирования — SIGSIM-PADS '18 . стр. 101–104. дои : 10.1145/3200921.3200925 . ISBN 9781450350921 . S2CID 21699926 .

[12] Маротта, Ромоло; Янни, Мауро; Пеллегрини, Алессандро; Квалья, Франческо (2017). «Конфликтоустойчивая календарная очередь без блокировки для масштабируемых платформ PDES с общим доступом ко всему». Материалы конференции ACM SIGSIM 2017 года по принципам расширенного дискретного моделирования — SIGSIM-PADS '17 . стр. 15–26. дои : 10.1145/3064911.3064926 . hdl : 11573/974295 . ISBN 9781450344890 . S2CID 30460497 .

[13] Линден, Джонатан; Йонссон, Бенгт (2013). «Очередь с параллельным приоритетом на основе скип-листа с минимальной конкуренцией за память». Материалы конференции 2013 года по принципам распределенных систем — OPODIS 2013 . стр. 206–220. дои : 10.1007/978-3-319-03850-6_15 . ISBN 9783319038490 .

[14] Джон Дж. Форбус; Дэниел Берлеант (2022). «Моделирование дискретных событий в учреждениях здравоохранения: обзор» . Моделирование . 3 (4): 417–433. arXiv : 2211.00061 . doi : 10.3390/modelling3040027 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]