3.1.1 Планирование события или алгоритм продвижения времени

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

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

В любое данное время t, СБС содержит все предварительно намеченные будущие события и связанные с этими событиями времена (названые t₁, t₂, … на рис. 3.1). СБС упорядочивает события по времени так, что события размещены хронологически, то есть времена событий удовлетворяют условиям

t < t₁  t₂  t₃  …  t_n.

Время t значения ЧАСОВ – текущее значение времени моделирования. Событие, связанное со временем t₁ названо предстоящим событием, то есть это следующее событие, которое произойдет. После того, как отображающие состояния системы ЧАСЫ = t во времени моделирования были модифицированы, ЧАСЫ продвигаются ко времени моделирования ЧАСЫ = t₁ и предстоящее намеченное событие удаляется из СБС и событие выполняется. Выполнение предстоящего события означает, что новое отображение состояния системы в течение времени t₁ создано на основании старого отображения состояния во время t и характера предстоящего события. Во время t₁, новые будущие события могут или не могут произойти, но если любые из них намечены, то создаются намеченные события и помещаются в соответствующие позиции в СБС. После того, как новое отображение состояния системы в течение времени t₁ было модифицировано, часы продвигаются ко времени нового предстоящего события и это событие выполняется. Этот процесс повторяется до окончания имитации. Последовательность действий, которые имитатор (или язык имитационного моделирования) должно исполнить для продвижения часов и строить новые отображения состояния системы, называется намечающей события или алгоритм продвижения времени. Шаги этого процесса перечислены на рис. 3.2 и объяснены ниже.

Отображение старого состояния системы во время t.

Время	Состояние системы	…	Список будущих событий	…
			(3, t1) – происходит событие типа 3 во время t1 (1, t2) – происходит событие типа 1 во время t2 (1, t3) – происходит событие типа 1 во время t3 … … (2, tn) – происходит событие типа 2 во время tn

Намечающиеся события или алгоритм продвижения времени.

Шаг 1. Удалите намеченное событие для предстоящего события (событие 3, время t₁) из СБС.

Шаг 2. продвижение ЧАСОВ ко времени предстоящего события, (то есть, продвинуть ЧАСЫ от t до t₁).

Шаг 3. Выполните предстоящее событие: обновите состояние системы, изменить свойства объекта и установить принадлежность как необходимо.

Шаг 4. Сгенерировать будущие события (в случае необходимости) и разместить их как намеченные события в СБС, упорядочивая события по времени. (Пример: Событие 4 произойдет во время t^*, где t₂ < t^*< t₃.)

Шаг 5. Обновить накопленную статистику и счетчики.

Отображение нового состояния системы во время t₁.

Время	Состояние системы	…	Список будущих событий	…
			(1, t2) – происходит событие типа 1 во время t2 (4, t^*) – происходит событие типа 4 во время t^* (1, t3) – происходит событие типа 1 во время t3 … … (2, tn) – происходит событие типа 2 во время tn

Рис 3.2 Моделирование продвижения времени и обновление отображения состояния системы

Длина и содержимое СБС постоянно изменяются, поскольку имитация продолжается и, таким образом, ее эффективное управление в компьютеризированном моделировании будет иметь главное воздействие на эффективность компьютерной программы, представляющей модель. Управление списком названо обработкой списка. Операции по обработке главного списка выполняются в СБС: удаление неизбежного события, добавление нового события к списку и, иногда, удаление некоторого события (вызываемое отменой события). Поскольку предстоящее событие находится обычно наверху списка, его удаление настолько эффективно насколько возможно. Добавление нового события (и отмена старого события) требует поиска в списке. Эффективность этого поиска зависит от логической организации списка и от того, как проводится поиск. В дополнение к СБС, все наборы в модели поддерживаются в некотором логическом порядке и операции добавления и удаления объектов из набора также требуют эффективных обрабатывающих методов для списка. Краткое введение для обработки списков имитации дано в разделе 3.2.

Удаление и добавление событий из СБС проиллюстрировано на рис. 3.2. Событие 3 со временем события t₁ представляет, скажем, событие завершения обслуживания в обслуживающем приборе 3. Так как это предстоящее событие во время t, то оно удалено из СБС на шаге 1 (рис. 3.2) намечающемся событием или алгоритмом продвижения времени. Когда событие 4 (говорят, событие прибытия) со временем t^* произошло на шаге 4, то есть один возможный способ решить, где его правильная позиция в СБС, это – провести нисходящий поиск:

Если t^* < t₂, то разместить событие 4 вверху СБС.

Если t₂  t^* < t₃, то разместить событие 4 вторым в списке.

Если t₃  t^* < t₄, то разместить событие 4 третьим в списке.

…

Если t_n  t^* , то разместить событие 4 последним в списке.

На рис. 3.2 было принято, что t^*, было между t₂ и t₃. Другой путь состоит в том, чтобы провести поиск снизу вверх. Наименее эффективный способ обслуживания СБС состоит в том, чтобы оставить его как неупорядоченный список, размещая добавляемые элементы произвольно в вершину или в основание, как это требовалось бы на шаге 1 (рис. 3.2), и заканчивая поиск в списке для предстоящего события перед каждым продвижением часов. (Предстоящее событие в СБС – событие с самым малым временем.)

Состояние системы во время 0 определяется начальными условиями и порождением так называемых внесистемных событий. Указанные исходные данные определяют состояние системы во время 0. Например, на рисунке 3.2, если t = 0, то состояние (5, 1, 6) могло бы представлять начальный номер клиента в трех различных точках в системе. Внесистемное событие – случай "вне системы", вторжения в систему. Важный пример – прибытие в систему массового обслуживания. Во время 0, первое событие прибытия сгенерировано и намечено в СБС (значение этого намеченного события помещено в СБС). Время между прибытием – пример действия. Когда часы, в конечном счете, продвинуты ко времени этого первого прибытия, второе событие прибытия сгенерировано. Сначала сгенерировано время между прибытием a^*; оно добавлено к текущему времени, ЧАСЫ = t; событие время окончания (будущее), t + a^* = t^*, используется для установления нового намеченного события прибытия в СБС. Этот метод генерации внешнего потока прибытия, называемый начальной загрузкой, предоставляет один пример того, как будущие события, созданные на шаге 4 из намеченного события или алгоритма продвижения времени. Начальная загрузка проиллюстрирована на рисунке 3.3. Три первичных входа времени сгенерированные между поступлениями – 3.7, 0.4, и 3.3 единиц. Конец интервала между поступлениями - пример начального события.

Во время моделирования t, принято, что моментом n-го поступления может быть время между поступлениями a^*, вычисляемое как t* = t + a^*, и намечается будущее поступление в СБС, которое произойдет в будущее время t *

Между последовательными событиями поступления могут происходить другие типы событий, по причине изменения состояния системы

Рис. 3.3 Генерация внешнего потока поступления требований при начальной загрузке

Второй пример того, как будущие события генерируются (шаг 4 на рис. 3.2) предоставлен событием завершения обслуживания при моделировании системы массового обслуживания. Если один клиент завершает время обслуживание в текущее время (ЧАСЫ = t) и присутствует следующий клиент, то новое время обслуживания s ^*, будет запланировано для следующего клиента. Следующее событие окончания обслуживания будет намечено, чтобы произойти в будущем времени t^* = t + s^*, и помещено в СБС новое намеченное событие окончания обслуживания со временем события t^*. Кроме того, событие окончания обслуживания будет запланировано и намечено во время события прибытия при условии, что по прибытию имеется, по крайней мере, один свободный обслуживающий прибор в группе обслуживающих приборов. Время обслуживания – пример действия. Начало обслуживание является условным событием, потому что наступление этого события начинается только при условии, что клиент присутствует и обслуживающий прибор свободен. Завершение обслуживания – пример первичного события. Обратите внимание, что условное событие, как, например, начало обслуживания, запущено первичным событием появления и некоторыми условиями, преобладающими в системе. Только первичные события появляются в СБС.

Третий важный пример – дополнительное порождение рабочих циклов и простоев для машины, предрасположенной к поломкам. Во время 0, первое время рабочего цикла будет сгенерировано и запланировано событие конца времени рабочего цикла. Всякий раз, когда событие конца времени рабочего цикла происходит, время простоя будет сгенерировано и событие конца времени простоя будет запланировано в СБС. Когда ЧАСЫ, в конечном счете, продвинуты ко времени этого события – конца времени простоя, то время рабочего цикла сгенерируется, и событие конец рабочего цикла будет запланировано в СБС. Таким образом, рабочие циклы и простои непрерывно чередуются в течение имитации. Время рабочего цикла и время простоя – примеры действий. Конец времени рабочего цикла и конец времени простоя – первичные события.

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

1. Во время 0, наметить событие останова моделирования в определенное будущее время T_E.

Таким образом, перед моделированием, известно, что имитация выполнится за временной интервал [0, T_E]. Пример: Моделирование работы цеха для T_E = 40 часов.

2. Выполняемая продолжительность T_E определяется непосредственно имитацией. Вообще, T_E – время наступления некоторого определенного события E. Примеры: T_E – время окончания 100-го обслуживания в некотором центре обслуживания. T_E – время поломки сложной системы. T_E – время выхода из боя или общее количество уничтожений (какое бы событие ни происходило первым) в имитации боя. T_E – время, за которое дистрибутивный центр отправляет окончательные картонные упаковки по заказам за день.

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