stringtranslate.com

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

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

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

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

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

Пример

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

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

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

Компоненты

Состояние

Состояние системы — это набор переменных, который фиксирует основные свойства изучаемой системы. Траектория состояния с течением времени 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».

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

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

Распространенное использование

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

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

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

Дисциплины:

Ссылки

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

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