Моделирование дискретных событий ( DES ) моделирует эксплуатацию системы как ( дискретная ) последовательность событий во время. Каждое событие происходит в определенный момент времени и отмечает изменение состояния в системе. [1] Предполагается, что между последовательными событиями в системе не произойдет никаких изменений; таким образом, время моделирования может напрямую перейти ко времени наступления следующего события, которое называется временной прогрессией следующего события .
В дополнение к временной прогрессии следующего события существует также альтернативный подход, называемый временной прогрессией с фиксированным приращением , где время разбивается на небольшие временные отрезки, а состояние системы обновляется в соответствии с набором событий / действий, происходящих во времени. ломтик. [2] Поскольку не нужно моделировать каждый временной интервал, моделирование времени следующего события обычно может выполняться намного быстрее, чем соответствующее моделирование времени с фиксированным приращением.
Обе формы DES контрастируют с непрерывным моделированием, в котором состояние системы изменяется непрерывно с течением времени на основе набора дифференциальных уравнений, определяющих скорость изменения переменных состояния.
Пример
Распространенным упражнением в обучении построению симуляций дискретных событий является моделирование очереди , например, клиентов, прибывающих в банк для обслуживания кассира. В этом примере системными объектами являются « Очередь клиентов» и « Счетчики» . Системными событиями являются « Клиент-Прибытие» и « Клиент-Отъезд» . (Событие Teller-Begins-Service может быть частью логики событий прибытия и отправления.) Состояниями системы, которые изменяются этими событиями, являются Number-of-Customers-in-the-Queue (целое число от От 0 до n) и Teller-Status (занят или свободен). В случайном переменных , которые должны быть охарактеризованы моделями этой системы стохастический являются клиентами-Interarrival время и Теллер-служба время . Агентная структура для моделирования производительности оптимистичного параллельного симулятора дискретных событий является еще одним примером симуляции дискретных событий. [3]
Составные части
В дополнение к логике того, что происходит при возникновении системных событий, моделирование дискретных событий включает в себя следующее:
- Приоритетная очередь,
- Обработчик событий анимации и
- Обработчик повторной нормализации времени (при запуске моделирования временные переменные теряют точность. Через некоторое время все временные переменные должны быть повторно нормализованы путем вычитания времени последнего обработанного события).
Состояние
Состояние системы - это набор переменных, который отражает основные свойства исследуемой системы. Траектория состояния во времени S (t) может быть математически представлена ступенчатой функцией , значение которой может изменяться всякий раз, когда происходит событие.
Часы
Моделирование должно отслеживать текущее время моделирования в любых единицах измерения, подходящих для моделируемой системы. В симуляциях дискретных событий, в отличие от непрерывных, время «скачкообразно», потому что события являются мгновенными - часы переходят к следующему времени начала события по мере продолжения симуляции.
Список событий
Моделирование поддерживает как минимум один список событий моделирования. Иногда это называется набором ожидающих событий, потому что в нем перечислены события, ожидающие выполнения в результате ранее смоделированного события, но еще не смоделированные сами. Событие описывается временем его возникновения и типом, указывающим код, который будет использоваться для имитации этого события. Обычно код события параметризуется, и в этом случае описание события также содержит параметры для кода события.
Когда события происходят мгновенно, действия, продолжающиеся во времени, моделируются как последовательности событий. Некоторые структуры моделирования позволяют указывать время события как интервал, давая время начала и время окончания каждого события.
Механизмы однопоточного моделирования, основанные на мгновенных событиях, имеют только одно текущее событие. Напротив, многопоточные механизмы моделирования и механизмы моделирования, поддерживающие модель событий на основе интервалов, могут иметь несколько текущих событий. В обоих случаях возникают серьезные проблемы с синхронизацией между текущими событиями.
Набор ожидающих событий обычно организован в виде очереди с приоритетом , отсортированной по времени события. [4] То есть, независимо от порядка, в котором события добавляются к набору событий, они удаляются в строго хронологическом порядке. Различные реализации приоритетной очереди были изучены в контексте моделирования дискретных событий; [5] изученные альтернативы включали раскрывающиеся деревья , списки пропусков , календарные очереди , [6] и лестничные очереди. [7] [8] На машинах с массовым параллелизмом , таких как многоядерные или многоядерные процессоры, набор ожидающих событий может быть реализован, полагаясь на неблокирующие алгоритмы , чтобы снизить стоимость синхронизации между параллельными потоками. . [9] [10]
Обычно события планируются динамически по мере продолжения моделирования. Например, в примере банка, упомянутом выше, событие CUSTOMER-ARRIVAL в момент времени t, если CUSTOMER_QUEUE было пустым, а TELLER было бездействующим, включало бы создание последующего события CUSTOMER-DEPARTURE, которое произойдет в момент времени t + s, где s число, полученное из распределения ВРЕМЯ ОБСЛУЖИВАНИЯ.
Генераторы случайных чисел
При моделировании необходимо генерировать случайные величины различных типов в зависимости от модели системы. Это выполняется одним или несколькими генераторами псевдослучайных чисел . Использование псевдослучайных чисел в противоположность истинным случайным числам является преимуществом, если симуляция нуждается в повторном запуске с точно таким же поведением.
Одна из проблем с распределениями случайных чисел, используемых при моделировании дискретных событий, заключается в том, что стационарные распределения времени событий могут быть неизвестны заранее. В результате начальный набор событий, помещенных в набор ожидающих событий, не будет иметь время прихода, представляющее установившееся распределение. Эта проблема обычно решается путем начальной загрузки имитационной модели. Прилагаются лишь ограниченные усилия, чтобы назначить реалистичное время для начального набора ожидающих событий. Однако для этих событий запланированы дополнительные события, и со временем распределение времени событий приближается к своему устойчивому состоянию. Это называется начальной загрузкой имитационной модели. При сборе статистики из работающей модели важно либо игнорировать события, которые происходят до достижения устойчивого состояния, либо запускать симуляцию достаточно долго, чтобы поведение начальной загрузки было подавлено поведением в установившемся состоянии. (Такое использование термина начальной загрузки можно противопоставить его использованию как в статистике, так и в вычислениях ).
Статистика
Моделирование обычно отслеживает статистику системы , которая дает количественную оценку интересующих аспектов. В примере с банком интересно отслеживать среднее время ожидания. В имитационной модели показатели производительности не выводятся аналитически из распределений вероятностей , а скорее как средние по повторениям , то есть различные прогоны модели. Доверительные интервалы обычно строятся, чтобы помочь оценить качество выходных данных.
Конечное условие
Поскольку события загружаются, теоретически симуляция дискретных событий может выполняться бесконечно. Поэтому разработчик симуляции должен решить, когда симуляция закончится. Типичный выбор - «в момент времени t» или «после обработки n событий» или, в более общем смысле, «когда статистическая мера X достигает значения x».
Трехэтапный подход
Пидд (1998) предложил трехэтапный подход к моделированию дискретных событий. При таком подходе первая фаза - переход к следующему хронологическому событию. Второй этап - выполнить все события, которые безусловно происходят в это время (они называются B-событиями). Третий этап - выполнить все события, которые условно происходят в это время (они называются C-событиями). Трехэтапный подход представляет собой уточнение подхода, основанного на событиях, при котором одновременные события упорядочиваются таким образом, чтобы максимально эффективно использовать ресурсы компьютера. Трехэтапный подход используется рядом коммерческих пакетов программного обеспечения для моделирования, но с точки зрения пользователя особенности лежащего в основе метода моделирования обычно скрыты.
Общее использование
Диагностика проблем процесса
Подходы к моделированию особенно хорошо оснащены, чтобы помочь пользователям диагностировать проблемы в сложных средах. Теория ограничений иллюстрирует важность понимания узких мест в системе. Выявление и устранение узких мест позволяет улучшить процессы и систему в целом. Например, на производственных предприятиях узкие места могут быть созданы из-за избыточных запасов, перепроизводства , изменчивости процессов и изменчивости маршрутизации или последовательности. Точно документируя систему с помощью имитационной модели, можно получить представление о всей системе с высоты птичьего полета.
Рабочая модель системы позволяет руководству понять драйверы производительности. Моделирование может быть построено так, чтобы включать любое количество показателей эффективности, таких как коэффициент использования работников, уровень своевременной доставки, процент брака, денежные циклы и т. Д.
Приложения для больниц
Операционная обычно используется несколькими хирургическими специалистами. За счет лучшего понимания природы этих процедур можно увеличить количество пациентов. Пример: если операция на сердце длится в среднем четыре часа, изменение расписания работы операционной с восьми доступных часов до девяти не увеличит пропускную способность. С другой стороны, если процедура грыжи занимает в среднем двадцать минут, дополнительный час также может не дать увеличения пропускной способности, если не учитывать вместимость и среднее время, проведенное в палате для восстановления.
Идеи по повышению производительности лабораторных тестов
Многие идеи по улучшению систем основаны на надежных принципах, проверенных методологиях ( Lean , Six Sigma , TQM и т. Д.), Но не могут улучшить систему в целом. Имитационная модель позволяет пользователю понять и протестировать идею повышения производительности в контексте всей системы.
Оценка решений о капиталовложениях
Имитационное моделирование обычно используется для моделирования потенциальных инвестиций. С помощью моделирования инвестиций лица, принимающие решения, могут принимать обоснованные решения и оценивать потенциальные альтернативы.
Сетевые симуляторы
Моделирование дискретных событий используется в компьютерной сети для моделирования новых протоколов, различных системных архитектур (распределенных, иерархических, централизованных, P2P) перед фактическим развертыванием. Можно определить различные метрики оценки, такие как время обслуживания, пропускная способность, отброшенные пакеты, потребление ресурсов и т. Д.
Смотрите также
Подходы к системному моделированию:
- Конечные автоматы и цепи Маркова
- Случайный процесс и частный случай, марковский процесс.
- Теория массового обслуживания и, в частности, процесс рождения и смерти
- Спецификация системы дискретных событий
- Моделирование на уровне транзакций (TLM)
Вычислительные методы:
- Компьютерный эксперимент
- Компьютерное моделирование
- Метод Монте-Карло
- Снижение дисперсии
- Генератор псевдослучайных чисел
Программное обеспечение:
- Список программ компьютерного моделирования
- Список программного обеспечения для моделирования дискретных событий
Дисциплины:
- Промышленная инженерия
- Сетевое моделирование
Рекомендации
- ^ Стюарт Робинсон (2004).Моделирование - Практика разработки и использования моделей.. Вайли.
- ^ Матлофф, Норм. «Введение в моделирование дискретных событий и язык SimPy» (PDF) . Проверено 24 января 2013 года .
- ^ Адитья Курве; Хашаяр Котоби; Джордж Кесидис (2013). «Агентная структура для моделирования производительности оптимистичного параллельного симулятора дискретных событий» . Моделирование сложных адаптивных систем . 1 : 12. DOI : 10,1186 / 2194-3206-1-12 .
- ^ Дуглас В. Джонс , изд. Реализации времени , Труды 18-й Зимней конференции по моделированию, 1986.
- ^ Дуглас У. Джонс , Эмпирическое сравнение реализаций очередей приоритетов и наборов событий , Сообщения ACM, 29 апреля 1986 г., страницы 300–311.
- ^ Ках Леонг Тан и Ли Джин Thng, Snoopy Календарь Queue , Труды 32й Зимний Simulation Conference, 2000
- ^ Дикман, Том; Гупта, Соунак; Уилси, Филип А. (2013). «Структуры пула событий для PDES на многоядерных кластерах Беовульф». Материалы конференции ACM SIGSIM 2013 по принципам расширенного дискретного моделирования - SIGSIM-PADS '13 . п. 103. DOI : 10,1145 / 2486092,2486106 . ISBN 9781450319201. S2CID 17572839 .
- ^ Фурфаро, Анджело; Сакко, Людовика (2018). «Адаптивная лестничная очередь». Материалы конференции ACM SIGSIM 2018 по принципам расширенного дискретного моделирования - SIGSIM-PADS '18 . С. 101–104. DOI : 10.1145 / 3200921.3200925 . ISBN 9781450350921. S2CID 21699926 .
- ^ Маротта, Ромоло; Янни, Мауро; Пеллегрини, Алессандро; Квалья, Франческо (2017). «Устойчивая к конфликтам очередь календаря без блокировок для масштабируемых платформ PDES с общим доступом». Материалы конференции ACM SIGSIM 2017 по принципам расширенного дискретного моделирования - SIGSIM-PADS '17 . С. 15–26. DOI : 10.1145 / 3064911.3064926 . ЛВП : 11573/974295 . ISBN 9781450344890. S2CID 30460497 .
- ^ Линден, Джонатан; Йонссон, Бенгт (2013). «Очередь одновременного приоритета на основе Skiplist с минимальной конкуренцией за память». Материалы конференции 2013 г. по принципам распределенных систем - OPODIS 2013 . С. 206–220. DOI : 10.1007 / 978-3-319-03850-6_15 . ISBN 9783319038490.
дальнейшее чтение
- Майрон Х. Макдугалл (1987). Моделирование компьютерных систем: методы и инструменты . MIT Press.
- Уильям Делани; Эрминия Ваккари (1988). Динамические модели и моделирование дискретных событий . Dekker INC.
- Роджер В. Макхейни (1991). Компьютерное моделирование: практическая перспектива . Академическая пресса.
- Майкл Пидд (1998). Компьютерное моделирование в науке управления - издание четвертое . Вайли.
- A, Алан Прицкер, Жан Дж. О'Рейли (1999). Моделирование с помощью Visual SLAM и AweSim . Вайли.CS1 maint: несколько имен: список авторов ( ссылка )
- Аверилл М. Лоу; В. Дэвид Келтон (2000). Имитационное моделирование и анализ - издание третье . Макгроу – Хилл.
- Бернар П. Зейглер; Герберт Прахофер; Тэг Гон Ким (2000). Теория моделирования и симуляции: интеграция дискретных событийных и непрерывных сложных динамических систем - второе издание . Академическая пресса.
- Джерри Бэнкс; Джон Карсон; Барри Нельсон; Дэвид Никол (2005). Моделирование дискретно-событийных систем - четвертое издание . Пирсон.
- Джеймс Дж. Нутаро (2010). Создание программного обеспечения для моделирования: теория и алгоритмы, с приложениями на C ++ . Вайли.