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

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

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

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

Пример

Распространенным упражнением в обучении построению симуляций дискретных событий является моделирование очереди , например, клиентов, прибывающих в банк для обслуживания кассира. В этом примере сущностями системы являются очередь клиентов и кассиры . Системными событиями являются « Клиент-Прибытие» и « Клиент-Отъезд» . (Событие Teller-Begins-Service может быть частью логики событий прибытия и отправления.) Состояниями системы, которые изменяются этими событиями, являются Number-of-Customers-in-the-Queue (целое число от От 0 до n) и Teller-Status (занят или свободен). В случайном переменных , которые должны быть охарактеризованы моделями этой системы стохастический являются клиентами-Interarrival время и Теллер-служба время . Агентная структура для моделирования производительности оптимистичного параллельного симулятора дискретных событий является еще одним примером симуляции дискретных событий.

Составные части

В дополнение к логике того, что происходит при возникновении системных событий, моделирование дискретных событий включает в себя следующее:

  • Приоритетная очередь,
  • Обработчик событий анимации и
  • Обработчик повторной нормализации времени (при запуске моделирования временные переменные теряют точность. Через некоторое время все временные переменные должны быть повторно нормализованы путем вычитания времени последнего обработанного события).

Состояние

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

Часы

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

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

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

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

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

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

Обычно события планируются динамически по мере продолжения моделирования. Например, в примере банка, упомянутом выше, событие CUSTOMER-ARRIVAL в момент времени t, если CUSTOMER_QUEUE было пустым и TELLER было бездействующим, включало бы создание последующего события CUSTOMER-DEPARTURE, которое произойдет в момент времени t + s, где s число, полученное из распределения ВРЕМЯ ОБСЛУЖИВАНИЯ.

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

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

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

Статистика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. Также: Методы Монте-Карло в финансах , Корпоративные финансы § Решения о капиталовложениях и Корпоративные финансы § Количественная оценка неопределенности

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

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

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

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

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

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

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

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

Дисциплины:

Рекомендации

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

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