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

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

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

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

пример

Распространенным упражнением в обучении построению симуляций дискретных событий является моделирование очередь, например, клиенты, прибывающие в банк для обслуживания кассира. В этом примере системные объекты Клиент-очередь и Кассиры. Системные события Клиент-Прибытие и Клиент-Выезд. (Событие Teller-Begins-Service могут быть частью логики событий прибытия и отправления.) Состояния системы, которые изменяются этими событиями, являются Количество клиентов в очереди (целое число от 0 до n) и Теллер-Статус (занят или свободен). В случайные переменные которые необходимо охарактеризовать для моделирования этой системы стохастически находятся Клиент-Время прибытия и Teller-Service-Time. Агентная среда для моделирования производительности оптимистичного параллельного симулятора дискретных событий является еще одним примером симуляции дискретных событий.[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-событиями). Трехэтапный подход представляет собой уточнение подхода, основанного на событиях, при котором одновременные события упорядочиваются таким образом, чтобы максимально эффективно использовать ресурсы компьютера. Трехэтапный подход используется рядом коммерческих пакетов программного обеспечения для моделирования, но с точки зрения пользователя, особенности лежащего в основе метода моделирования обычно скрыты.

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

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

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

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

Приложения для больниц

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

Идеи повышения производительности лабораторных тестов

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

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

Смотрите также: Методы Монте-Карло в финансах; Корпоративные финансы # Капитальные инвестиционные решения и # Оценка неопределенности.

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

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

Основная статья: Сетевое моделирование

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


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

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

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

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

Дисциплины:

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

  1. ^ Стюарт Робинсон (2004). Моделирование - Практика разработки и использования моделей. Вайли.
  2. ^ Матлофф, Норм. «Введение в моделирование дискретных событий и язык SimPy» (PDF). Получено 24 января 2013.
  3. ^ Адитья Курве; Хашаяр Котоби; Джордж Кесидис (2013). «Агентная структура для моделирования производительности оптимистичного параллельного симулятора дискретных событий». Моделирование сложных адаптивных систем. 1: 12. Дои:10.1186/2194-3206-1-12.
  4. ^ Дуглас В. Джонс, изд. Реализации времени, Материалы 18-й Зимней конференции по моделированию, 1986.
  5. ^ Дуглас В. Джонс, Эмпирическое сравнение реализаций очереди приоритетов и набора событий, Коммуникации АКМ, 29, г. Апрель 1986 г., страницы 300–311.
  6. ^ Ка Леонг Тан и Ли-Джин Тхнг, Очередь календаря SNOOPy, Материалы 32-й зимней конференции по моделированию, 2000 г.
  7. ^ Дикман, Том; Гупта, Соунак; Уилси, Филип А. (2013). «Структуры пула событий для PDES на многоядерных кластерах Beowulf». Материалы конференции ACM SIGSIM 2013 по принципам расширенного дискретного моделирования - SIGSIM-PADS '13. п. 103. Дои:10.1145/2486092.2486106. ISBN  9781450319201. S2CID  17572839.
  8. ^ Фурфаро, Анджело; Сакко, Людовика (2018). «Адаптивная лестничная очередь». Материалы конференции ACM SIGSIM 2018 по принципам расширенного дискретного моделирования - SIGSIM-PADS '18. С. 101–104. Дои:10.1145/3200921.3200925. ISBN  9781450350921. S2CID  21699926.
  9. ^ Маротта, Ромоло; Янни, Мауро; Пеллегрини, Алессандро; Квалья, Франческо (2017). «Устойчивая к конфликтам очередь календаря без блокировки для масштабируемых платформ PDES с общим доступом». Материалы конференции ACM SIGSIM по принципам расширенного дискретного моделирования 2017 года - SIGSIM-PADS '17. С. 15–26. Дои:10.1145/3064911.3064926. HDL:11573/974295. ISBN  9781450344890. S2CID  30460497.
  10. ^ Линден, Джонатан; Йонссон, Бенгт (2013). «Очередь одновременных приоритетов на основе Skiplist с минимальной конкуренцией за память». Материалы конференции 2013 г. по принципам распределенных систем - OPODIS 2013. С. 206–220. Дои: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 ++. Вайли.