Основы дискретно-событийного моделирования СМО

Определим основные понятия и термины, используемые в моде­лировании.

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

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

Состояние системы - множество переменных, которые содер­жат всю информацию, необходимую для описания свойств системы в любое время.

Объект - любой элемент или компонент в системе, который должен быть представлен в модели в явном виде (например, обслу­живающее устройство, клиент, машина).

Свойство или атрибут - свойства данного объекта (например, приоритет ожидающего клиента, маршрут процесса выполнения ра­бот в цеху).

Список - множество (постоянное или временное) связанных объектов, упорядоченное некоторым логическим способом (напри­мер, все клиенты, находящиеся в настоящее время в очереди ожида­ния, упорядочены по принципу «раньше прибыл, раньше обслужил­ся» или по приоритету).

Событие - мгновенно возникающее изменение состояние сис­темы (например, прибытие нового требования).

Уведомление о событии - запись события, которое произойдет в потоке событий или в некотором будущем времени наряду с любы­ми связанными данными, необходимыми для обработки события (за­пись всегда включает тип события и время события).

Список событий - список намеченных будущих событий, упо­рядоченных по времени возникновения, известный также как список будущих событий (СБС).

Действие - продолжительность времени указанного промежут­ка (например, время обслуживания или время между поступлениями заявок), для которого известно, когда оно начинается и заканчивается (хотя оно может быть определено в терминах статистического рас­пределения).

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

Модельное время - неотрицательная возрастающая величина, отражающая течение времени в имитационной модели.

Часы - переменная, отражающая протекание времени модели­рования, называется в примерах ЧАСЫ (CLOCK).

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

Для СМО с одним устройством обслуживания событиями будут поступление требования и конец его обслуживания устройством. На­чало обслуживания - это условное событие, которое зависит от со­стояния прибора (занят или свободен) и числа требований, находя­щихся в очереди. Задержку иногда называют условным ожиданием, в то время как действие называют безусловным ожиданием. Дейст­виями будут время между поступлениями требований и время обслу­живания прибором. Завершение действия - событие, часто называе­мое первичным событием, для управления которым в СБС помеща­ется уведомление о событии. Напротив, управление задержками свя­зано с помещением объекта в другой список, возможно представ­ляющий очередь ожидания до такого времени, когда системные усло­вия разрешат обработку требования. Окончание задержки иногда на­зывают условным или вторичным событием, но такие события не представлены в соответствующих уведомлениях о событиях и не по­являются в СБС.

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

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

В табл. 1.1 представлены интервалы времени между приходами покупателей в магазин и требуемыми временами их обслуживания продавцом, а на рис. 1.3 проведено графическим методом «ручное» моделирование СМО с одним устройством.

С точки зрения объектного подхода имеются динамические объ­екты - требования (ПОКУПАТЕЛИ) и некоторый ресурс - устройст­во обслуживания (статический объект ПРОДАВЕЦ), которое они используют. Если требование претендует на ресурс, а он занят, то оно становится в ОЧЕРЕДЬ к ресурсу. ОЧЕРЕДЬ может быть отдельным объектом или просто списком, связанным с ресурсом. Примем за пра­вило обслуживания - FIFO.

Таблица 1.1

№ покупателя
Время поступления,
Время обслуживания,

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

Опишем алгоритм работы системы с точки зрения «жизненного цикла» ПОКУПАТЕЛЯ, т.е. от момента его прихода в магазин до мо­мента выхода из магазина. Так как покупатели непрерывно приходят в магазин на протяжении некоторого периода времени наблюдения за системой (время, в течении которого моделируется система), то необ­ходимо обеспечить поток ПОКУПАТЕЛЕЙ путем их создания в мо­дели (генерации в некоторые моменты времени - моменты их прихода в магазин). Для генерации ПОКУПАТЕЛЕЙ используем специаль­ную подпрограмму ГЕНЕРАТОР (в языке GPSS этой подпрограмме соответствует блок GENERATE). Алгоритм ее работы следующий:

1. Создать динамический объект ПОКУПАТЕЛЬ в виде струк­туры данных, включающей в себя поля: номер покупателя - j, момент его прихода - , а также при необходимости свойства покупателя или его атрибуты (например, его приоритет). Запланировать событие - приход покупателя j на момент времени - т.е. создать уведом­ление о событии в СБС.

2. Запланировать следующее событие для покупателя j -ЗАПРОС-НАЗНАЧЕНИЕ ресурса R (ПРОДАВЦА) на момент време­ни . Запланировать приход следующего динамического объекта ПОКУПАТЕЛЬ j + 1, т.е. определить событие прихода следующего покупателя .

Описание процесса использования ресурса требованием целесо­образно разбить на три подпрограммы.

Первая - это ЗАПРОС-НАЗНАЧЕНИЕ ресурса R требованию / (в языке GPSS этой подпрограмме соответствует блок SEIZE). Алго­ритм ее работы следующий:

1. Если ресурс R (ПРОДАВЕЦ) может быть сразу назначен тре­бованию у, то изменить состояние ресурса R на «занятый». Запомнить момент начала обслуживания требования Передать управление подпрограмме ОБСЛУЖИВАНИЕ требования j.

2. Если ресурс R занятый, то поставить требование j в ОЧЕРЕДЬ к ресурсу R.

Вторая подпрограмма - ОБСЛУЖИВАНИЕ требования j (в язы­ке GPSS этой подпрограмме соответствует блок ADVANCE). Ее ал­горитм работы очень простой - определить событие «конец обслужи­вания требования j» как (где - время обслуживания в устройстве). Т.е. создается уведомление о событии в СБС для переда­чи управления подпрограмме освобождения ресурса R требованием j.

Третья подпрограмма - ОСВОБОЖДЕНИЕ ресурса R требова­нием j (в языке GPSS этой подпрограмме соответствует блок RELEASE). Алгоритм ее работы следующий:

1. Изменить состояние ресурса R (ПРОДАВЕЦ) на «свободный». Передать управление подпрограмме УНИЧТОЖЕНИЕ требования.

2. Проверить, есть ли требования в ОЧЕРЕДИ к ресурсу R? Если есть, то выбрать требование из ОЧЕРЕДИ и запланировать для него событие ЗАПРОС-НАЗНАЧЕНИЕ ресурса R.

Подпрограмма УНИЧТОЖЕНИЕ требования (в языке GPSS этой подпрограмме соответствует блок TERMINATE) необходима для уничтожения структуры данных каждого требования. Если тре­бования не уничтожать, то со временем они переполнят память ком­пьютера.

Кроме перечисленных подпрограмм необходима программа управления процессом моделирования (ПУМ), которая запускает процесс моделирования и отслеживает движение каждого требования по модели путем вызова названных подпрограмм обработки событий. Другое назначение этой программы - вести список упорядоченных во времени событий СБС и продвигать ЧАСЫ модельного времени от события к событию. В языке GPSS функции ПУМ выполняет про­грамма-интерпретатор (транслятор).

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

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

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

(1.12)

Время значения ЧАСОВ - текущее значение времени моде­лирования. Событие, связанное со временем , называется пред­стоящим событием, то есть это следующее событие, которое про­изойдет. После того, как отображающие состояния системы ЧА­СЫ = во время моделирования были модифицированы, ЧАСЫ продвигаются ко времени моделирования ЧАСЫ = , предстоящее намеченное событие удаляется из СБС и выполняется подпрограмма события. Выполнение подпрограммы предстоящего события означа­ет, что отображено новое состояние системы в течение времени , которое создано на основании старого состояния модели во время и характера предстоящего события. Во время новые будущие со­бытия могут произойти или не произойти, но если любые из них на­мечены, то создаются намеченные события и помещаются в соответ­ствующие позиции в СБС. После того, как новое отображение со­стояния системы в течение времени было модифицировано, ЧАСЫ продвигаются ко времени нового предстоящего события, и выполняется подпрограмма этого события. Такой процесс повторяет­ся до окончания имитации. На рис. 1.4 показана структурная схема имитационной модели.

В момент начала моделирования (время моделирования =0) ПУМ передает управление подпрограмме ГЕНЕРАТОР, которая оп­ределяет момент прихода первого покупателя и намечает событие ЗАПРОС-НАЗНАЧЕНИЕ ресурса R в СБС на время = . Так как больше событий в системе нет, то ЧАСЫ переводятся на значение времени , вызывается подпрограмма ГЕНЕРАТОР и подпрограмма ЗАПРОС-НАЗНАЧЕНИЕ ресурса R.

Подпрограмма ГЕНЕРАТОР определяет будущее событие (мо­мент прихода второго покупателя ) и намечает это событие в СБС на время .

Подпрограмма ЗАПРОС-НАЗНАЧЕНИЕ проверяет состояние ресурса (ПРОДАВЦА). Так как ресурс R свободный, то он назначает­ся первому покупателю и состояние ресурса R изменяется на «заня­тый». Запоминается момент начала обслуживания требования . Пе­редается управление подпрограмме ОБСЛУЖИВАНИЕ покупателя 1.

Подпрограмма ОБСЛУЖИВАНИЕ определяет событие конца обслуживания покупателя 1, как , т.е. создается уведомле­ние о будущем событии в СБС для передачи управления подпро­грамме ОСВОБОЖДЕНИЯ ресурса R требованием 1 на время .

Таким образом, в СБС имеется два элемента - один с намечен­ным событием появления покупателя 2 на время , а второй с наме­ченным событием окончания обслуживания покупателя 1 на время . Если время , то ЧАСЫ будут переведены на время , т. е. снова будет вызвана подпрограмма ГЕНЕРАТОР и сгенерирова­но появление покупателя 2. В этот же момент времени произойдет вызов подпрограммы ГЕНЕРАТОР, которая наметит в СБС появле­ние покупателя 3 на время и вызов подпрограммы ЗАПРОС-НАЗНАЧЕНИЕ ресурса R, но так как ресурс занят обслуживанием покупателя 1, то покупатель 2 будет поставлен в очередь к ресурсу R.

В СБС снова окажутся два элемента - один для намеченного со­бытия появления покупателя 3 на время , а второй с намеченным событием окончания обслуживания покупателя 1 на время . Если время , то ЧАСЫ будут переведены на время , т. е. бу­дет вызвана подпрограмма ОСВОБОЖДЕНИЕ ресурса R покупате­лем 1.

Она изменить состояние ресурса R (ПРОДАВЕЦ) на «свобод­ный» и передаст управление подпрограмме УНИЧТОЖЕНИЕ требования. Затем проверит, есть ли требования в ОЧЕРЕДИ к ресурсу R, и выберет покупателя 2 из ОЧЕРЕДИ, наметив для него событие для подпрограммы ЗАПРОС-НАЗНАЧЕНИЕ ресурса R.

Вызванная в это же модельное время подпрограмма УНИЧТОЖЕНИЕ разрушит структуру данных (удалит ссылку на ад­рес) для покупателя 1. Эта же подпрограмма при необходимости мог­ла бы вычислить время пребывания покупателя 1 в системе, как - (, для дальнейшей статистической оценки времени пребыва­ния покупателей в системе.

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

Остается открытым вопрос об окончании процесса моделирова­ния. Возможны три варианта:

1. Через модель пройдут все покупатели, сгенерированные ГЕНЕРАТОРОМ, например, 100 покупателей. В этом случае в СБС после обслуживания последнего, сотого, покупателя не будет ни од­ного намеченного события.

2. Если поток покупателей от генератора не ограничен (напри­мер, генерируется неограниченный пуассоновский поток), то модели­рование можно закончить после прохождения через модель опреде­ленного количества покупателей, например, 1000. Для этого в под­программе УНИЧТОЖЕНИЕ надо поставить счетчик покупателей и прекратить моделирование после 1000 покупателей. В языке GPSS такой счетчик организуется в команде START, которая начинает про­цесс моделирования.

3. Необходимо промоделировать работу системы в течение за­данного периода времени, например, 480 мин. В этом случае можно при каждом продвижении ЧАСОВ модельного времени f проводить сравнение текущего времени со значением 480. Как только значение модельного времени будет больше или равно 480, необходимо пре­кратить моделирование. Однако такой способ неудачный, так как может сильно замедлить работу модели из-за проверки условия. По­этому обычно поступают следующим образом. Генерируют специ­альное требование-таймер с помощью еще одной подпрограммы ГЕНЕРАТОР с намеченным временем входа в модель = 480. Тре­бование-таймер после генерации сразу же направляется в еще одну подпрограмму УНИЧТОЖЕНИЯ, в которой ставят счетчик требова­ний на единицу. По этому счетчику прекращают моделирование. В этом случае в СБС будет все время находиться элемент для требова­ния-таймера со временем наступления события 480. Как только это событие станет предстоящим намеченным, ЧАСЫ будут переведены на время 480 и моделирование прекратится.

В процессе моделирования обычно собирается статистическая информация о работе модели при каждом продвижении ЧАСОВ мо­дельного времени. Такой информацией может быть величина очере­ди, время пребывания в очереди и устройстве обслуживания, загрузка устройства, состояние прибора и другие параметры. Для сбора этой информации обычно создается подпрограмма ВЫБОРОЧНЫЙ ИЗМЕРИТЕЛЬ, которая накапливает ее и по окончании моделирова­ния выдает стандартный статистический отчет. В языке GPSS такая статистическая информация накапливается в системных числовых атрибутах (СЧА) и доступна в процессе моделирования только на считывание. Доступ к СЧА дает возможность управлять процессом движения требований, например, ограничивать размер или время на­хождения в очереди.

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