Дискретно -событийное моделирование ( DES ) моделирует работу системы как ( дискретную ) последовательность событий во времени. Каждое событие происходит в определенный момент времени и отмечает изменение состояния в системе. [1] Между последовательными событиями не предполагается, что происходит никаких изменений в системе; таким образом, время моделирования может напрямую переходить ко времени возникновения следующего события, что называется прогрессией времени следующего события .
В дополнение к прогрессии времени следующего события существует также альтернативный подход, называемый прогрессией приращения времени , при котором время разбивается на небольшие временные отрезки, а состояние системы обновляется в соответствии с набором событий/действий, происходящих в течение временного отрезка. [2] Поскольку не каждый временной отрезок должен моделироваться, моделирование времени следующего события обычно может выполняться быстрее, чем соответствующее моделирование приращения времени.
Обе формы DES контрастируют с непрерывным моделированием , в котором состояние системы непрерывно изменяется с течением времени на основе набора дифференциальных уравнений, определяющих скорости изменения переменных состояния.
В прошлом эти три типа моделирования также назывались соответственно: моделированием планирования событий, моделированием сканирования активности и моделированием взаимодействия процессов. Можно также отметить, что существуют сходства между реализацией очереди событий в планировании событий и очередью планирования , используемой в операционных системах.
Распространенным упражнением в обучении построению дискретно-событийных симуляций является моделирование системы очередей , например, клиентов, приходящих к кассиру банка для обслуживания клерком. В этом примере системными объектами являются Customer и Teller , а системными событиями — Customer-Arrival , Service-Start и Service-End . Каждое из этих событий имеет свою собственную динамику, определяемую следующими процедурами событий:
Случайными величинами , которые необходимо охарактеризовать для стохастического моделирования этой системы, являются время между прибытиями повторяющихся событий «Прибытие клиента» и время обслуживания для задержек событий «Окончание обслуживания» .
Состояние системы — это набор переменных, который фиксирует основные свойства изучаемой системы. Траектория состояния с течением времени 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) перед фактическим развертыванием. Можно определить различные метрики оценки, такие как время обслуживания, пропускная способность, отброшенные пакеты, потребление ресурсов и т. д.
Подходы к моделированию систем:
Вычислительные методы:
Программное обеспечение:
Дисциплины:
{{cite book}}
: CS1 maint: несколько имен: список авторов ( ссылка )