Дискретно-событийное моделирование (англ. discrete-event simulation , DES) — это вид имитационного моделирования. В дискретно-событийном моделировании функционирование системы представляется как хронологическая последовательность событий. Событие происходит в определенный момент времени и знаменует собой изменение состояния системы.

Содержание

Компоненты системы дискретно-событийного моделирования [ править | править код ]

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

Часы [ править | править код ]

Основной компонент системы, синхронизирующий изменения системы, т.е. возникновение событий.

Список событий [ править | править код ]

Система моделирования поддерживает по крайней мере один список событий моделирования.

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

Генераторы случайных чисел [ править | править код ]

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

Статистика [ править | править код ]

Основные данные, которые собираются в системах дискретно-событийного моделирования:

  • Средняя занятость (доступность) ресурсов
  • Среднее количество клиентов в очереди
  • Среднее время ожидания в очереди

Условие завершения [ править | править код ]

Условием завершения могут выступать:

  • Возникновение заданного события (например, достижение 10-минутного времени ожидания в очереди)
  • Прохождение заданного числа циклов по часам системы моделирования

Реализация [ править | править код ]

Системы дискретно-событийного моделирования—это, чаще всего, проблемно-ориентированные языки программирования или библиотеки для высокоуровневых языков. Наиболее известные: Arena, AnyLogic, SIMSCRIPT, SLAM, SIMAN, AweSim, GPSS.

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

состояние системы — совокупность переменных состояния, необходимых для описания системы в определенный момент времени;

часы модельного времени — переменная, указывающая текущее значение модельного времени;

список событий — список, содержащий время возникновения каждого последующего типа событий;

статистические счетчики — переменные, предназначенные для хранения статистической информации о характеристике системы;

программа инициализации — подпрограмма, устанавливающая в исходное состояние имитационную модель в момент времени, равный 0;

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

программа обработки событий — подпрограмма, обновляющая состояние системы, когда происходит событие определенного типа (для каждого типа событий существует отдельная программа обработки событий);

библиотечные программы — набор подпрограмм, применяемых для генерации случайных наблюдений из распределений вероятностей, которые были определены как часть имитационной модели;

генератор отчетов — подпрограмма, которая считывает оценки (со статистических счетчиков) критериев оценки работы и выдает отчет по окончании моделирования;

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

Логические отношения (поток управления) между данными компонентами показаны на рис. 2. Моделирование начинается в момент времени, равный 0. При этом основная программа вызывает программу инициализации, которая устанавливает часы модельного времени в 0, затем задает исходное состояние системы, устанавливает в исходное состояние статистические счетчики и инициализирует список событий. После возвращения управления основной программе она вызывает синхронизирующую программу, чтобы определить тип ближайшего события. Если следующим должно произойти событие типа г, часы имитационного времени переводятся на время возникновения события типа i, и управление возвращается основной программе.

Основная программа активизирует программу обработки событий i, при этом происходят три типа действий: первое — обновляется состояние системы в соответствии с произошедшим событием типа г; второе — собирается информация о критериях оценки работы системы путем обновления статистических счетчиков; третье — генерируется время возникновения будущих событий, и информация о нем добавляется в список событий.

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

И если моделирование должно быть завершено, из основной программы вызывается генератор отчета, для того чтобы считать оценки (со статических счетчиков) необходимых критериев работы и создать отчет. Если время прекращения моделирования еще не настало, управление снова передается основной программе, и цикл «основная программа—синхронизирующая программа—основная программа—программа обработки событий—проверка условия прекращения имитации» повторяется до тех пор, пока условие останова не будет выполнено.

Прежде чем завершить этот раздел, следует сказать несколько слов о состоянии системы. Как уже говорилось в разделе 1, система — это четко определенная совокупность объектов.

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

Объекты с каким-либо общим свойством часто объединяются в списки (в файлы, либо наборы). Для каждого объекта существует запись в списке, состоящем из атрибутов объектов. Порядок размещения объектов в списке определяется некоторым правилом.

В системе, описанной в примере 1, такими объектами являются устройство обслуживания и требования. Здесь устройство имеет атрибут «состояние устройства» (занято или свободно), а требования, ожидающие в очереди, — атрибут «время поступления». (Число требований в очереди можно также считать атрибутом устройства.)

Рис. 2. Поток управления в механизме продвижения времени от события к событию

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

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

Для разработки такого рода имитационных моделей требуется специальное программное обеспечение имитационного моделирования. Даже при использовании процессного подхода моделирование фактически выполняется вне нашего поля зрения — как часть представленной выше логики планирования событий.

Дискретно-событийное моделирование — подход, соответствующий низкому и среднему уровням абстракции. Родоначальником этого подхода, основанного на концепции заявок (требований), ресурсов и потоковых диаграмм, считается Джефри Гордон, разработавший в 1960-х гг. систему моделирования GPSS. Термин «дискретно-событийное моделирование» исторически закрепился за моделированием систем обслуживания потоков объектов некоторой природы: клиентов банка, автомобилей па заправочной станции, телефонных вызовов, пациентов в поликлиниках и т.п. Обслуживание при этом может быть достаточно сложным. Например, рассматривая конвейерные системы для поточной сборки изделий как системы массового обслуживания, разработчик модели должен учитывать характеристики самих конвейеров, алгоритмы сборки изделий и разного рода дополнительные условия (например, наличие ресурсов конкретного типа). Дискретно-событийный подход широко используется в моделировании бизнес-процессов, производства, логистики, здравоохранения и т.д.

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

Довольно часто термин «дискретно-событийное моделирование» используется в более узком смысле — «процессное моделирование», для которого характерно представление динамики моделируемой системы как последовательности операций над некими пассивными заявками (трансактами, требованиями). Заявками могут быть документы, клиенты, транспортные средства, пакеты данных и т.п., а операциями над заявками — задержка, захват ресурса, разделение и т.п. Заявки в дискретно-событийном моделировании не контролируют свою динамику, но обладают определенными атрибутами, которые могут влиять на процесс их обработки (например, тип звонка, сложность работы) или накапливать статистику. Процессное моделирование используется на среднем или низком уровне абстракции — каждый объект моделируется индивидуально, но обезличенно, т.е. многие характеристики объекта не учитываются.

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

банка в терминах системы имитационного моделирования Arena [1] показана на рис. 8.3.

Рис. 8.3. Типичная потоковая диаграмма в терминах системы Arena

Сегодня существует более сотни коммерческих и свободно распространяемых программных продуктов, поддерживающих дискретно-событийное моделирование. Среди них есть системы общего назначения и специализированные инструменты, предназначенные для моделирования в определенной области: обслуживание, бизнес-процессы, производство, логистика и т.д. Пользовательские интерфейсы таких систем могут существенно различаться, но за ними обязательно стоит так называемый дискретнособытийный движок (engine), обеспечивающий перемещение заявки через блоки системы в соответствии с логикой дискретно-событийного подхода.

Примеры инструментов, поддерживающих такой подход в имитационном моделировании, — Any Logic, Arena, Actor Pilgrim, GPSS/PC, GPSS/H, GPSS World, Object GPSS, SimProcess, Enterprise Dynamics, Auto-Mod и др.