Моделирование систем с дискретными событиями

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Концепции в дискретно-событийном моделировании

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

1.2 Принципы

1.3 Ручное моделирование, использующее планирование событий

2. Обработка списков

3 Использование динамического распределения и связанных списков

Заключение

Список использованных источников

моделирование алгоритм планирование список

Введение

Данная курсовая работа раскрывает общую структуру моделирования сложной системы, с использованием имитации с дискретными событиями. Она охватывает основные блоки формирования всех моделей моделирования с дискретными событиями: объекты и свойства, действия и события. В моделировании с дискретными событиями система моделируется в терминах ее состояний в каждый момент времени: объекты, которые проходят через систему и объекты, которые представляют системные ресурсы; действия и события, которые изменяют состоянию системы. Модели с дискретными событиями соответствуют таким системам, для которых изменения состояний системы происходят только в дискретные моменты времени. Работа представляет и объясняет фундаментальные концепции и подходы, лежащие в основе всех пакетов моделирования с дискретными событиями. Эти концепции и подходы не связаны с конкретным пакетом. Многие из пакетов используют различную терминологию, отличную от принятой здесь. Более того, разрабатывают множество структурных компонентов с более высоким уровнем, чтобы упростить моделирование для конкретной прикладной области. Глава 1 общих принципов (часть 1.1) охватывает общие принципы и концепции моделирования с дискретными событиями, намечающимися событиями или алгоритмами продвижения времени, и три распространенных подхода: планирование событий, взаимодействие процессов и сканирование деятельности.

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

1. Концепции в дискретно-событийном моделировании

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

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

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

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

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

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

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

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

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

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

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

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

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

Различные пакеты имитационного моделирования использует различные термины для этой же самой или подобной концепции. Например, списки иногда названы последовательностями, очередями или цепочками. Последовательности или списки используются для хранения намеченных событий также как объектов. Объекты в списке всегда упорядочиваются в соответствии с некоторым правилом, как, например FIFO или LIFO или по некоторым признаком объекта, как, например приоритет или соответствующий срок. Событие всегда занимает место в списке будущих событий согласно намеченному времени. Раздел1.2 обсуждает множество методов для обработки списков и представляет некоторые из методологий для эффективной обработки упорядоченных последовательностей или списков.

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

1. Детерминировано, например, всегда точно 5 минут.

2. Статистически, например, как случайное извлечение из чисел 2, 5, 7 с равной вероятностью.

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

Продолжительность определяемого действия вычисляется в момент его начала. На его продолжительность не воздействует возникновение других событий (если, как позволяют некоторые пакеты имитационного моделирования, не используется логика для отмены события). Чтобы сохранить последовательность действий и их ожидаемые времена завершения в имитируемый момент, время завершения действия равняется времени, продолжительности действия начиная с момента, когда намечено событие при его создании. Например, если текущая запись ЧАСОВ модельного времени равна 100 минутам и время осмотра (равное точно 5 минутам) только начинается, то намечается событие определенного типа (событие конец проверки) и определяется время события (100 + 5 = 105 минут).

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

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

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

Системы, рассматриваемые здесь - динамические, то есть изменяются через какое-то время. Поэтому, состояние системы, свойства объекта и число активных объектов, содержимое множеств, действий и задержек легко изменяются - все они функции времени и постоянно изменяются через какое-то время. Само время представлено переменной с именем ЧАСЫ.

ПРИМЕР 1 (Эйбл (Able) и Бейке (Baker), повторное рассмотрение)

Этот пример иллюстрирует процедуру имитации, когда имеются больше чем один канал обслуживания. Рассмотрите ресторан "обслуживающий клиентов непосредственно в автомобиле", где официанты придорожного ресторана берут заказы и приносят еду к автомобилю. Автомобили прибывают, как показано в табл. 1.1. Имеются два официанта придорожного ресторана: Эйбл и Бейке. Эйбл способный лучше делать работу и работает немного быстрее, чем Бейке.

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

Таблица 1.1

Время между прибытием, мин	Вероятность	Накопленная вероятность	Распределение случайных чисел
1	0,25	0,25	01-25
2	0,40	0,65	26-65
3	0,20	0,85	66-85
4	0,15	1,0	86-100

Распределение времени обслуживания Эйблем

Таблица 1.2

Время обслуживания, мин	Вероятность	Накопленная вероятность	Распределение случайных чисел
2	0.30	0.30	01-30
3	0.28	0.58	31-58
4	0.25	0.83	59-83
5	0.17	1.00	84-100

Распределение времени обслуживания Бейке

Таблица 1.3

Время обслуживания, мин	Вероятность	Накопленная вероятность	Распределение случайных чисел
3	0.35	0.35	01-35
4	0.25	0.60	36-60
5	0.20	0.80	61-80
6	0.20	1.00	81-100

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

Рассмотрите систему придорожного ресторана с официантами Эйблем и Бейке. Модель с дискретными событиями имеет следующие компоненты:

Системное состояние

LQ(t) - число автомобилей, ожидающих обслуживания во время t.

LA(t) - принимает значение 0 или 1, указывая Эйбл свободный или занятый во время t.

LB(t) - принимает значение 0 или 1, указывая Бейке свободный или занятый во время t.

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

События

Событие прибытия.

Завершение обслуживания Эйблем.

Завершение обслуживания Бейке.

Действия

Время между прибытиями, определено в табл. 1.1

Время обслуживания Эйблем, определено в табл. 1.2

Время обслуживания Бейке, определено в табл. 1.3

Ожидание. Клиент ждет в очереди пока Эйбл или Бейке не станут свободными.

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

1. Как каждое событие затрагивает состояние системы, свойства объекта и устанавливает содержание?

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

3. Какие события начинают и заканчивают каждый тип задержки? При каких условиях начинается или заканчивается задержка?

4. Каково состояние системы в нулевой момент времени? Какие события должны произойти во время 0, то есть "первоначально" запустить режим имитации?

Копия состояния исследуемого объекта показана на рис. 1.1. Не все модели будут содержать элементы, показанные на рис.1.1. Дальнейшие иллюстрации представлены в примерах этой главы.

Таблица

Время	Состояние системы	Объект и свойства	Мно-жество 1	Мно-жество 2	…	Список будущих событий, СБС	Накопленная статистика и счетчики
t	(x,y,z,…)					(3, t1) - происходит событие типа 3 во время t1 (1, t2) - происходит событие типа 1 во время t2 …

Рис.1.1. Копия состояния системы во время t

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

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

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

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

t < t1 t2 t3 … tn.

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

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

Таблица

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

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

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

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

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

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

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

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

Таблица

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

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

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

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

Если t2 t* < t3, то разместить событие 4 вторым в списке.

Если t3 t* < t4, то разместить событие 4 третьим в списке.

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

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

Состояние системы во время 0 определяется начальными условиями и порождением так называемых внесистемных событий. Указанные исходные данные определяют состояние системы во время 0. Например, на рисунке1.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 *

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

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

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

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

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

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

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

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

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

1.2 Принципы

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

Чтобы суммировать предыдущее обсуждение, при использовании подхода намечающего события, аналитик при моделировании концентрируется на событиях и их влиянии на состояние системы. Это принцип будет проиллюстрирован ручными имитациями в разделе 3.1.3 и моделированием на языке C ++ в главе 4.

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

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

Более точный термин для процесса - это список упорядоченных во времени событий, действий и задержек, включая запросы на ресурсы. Он определяет цикл жизни одного объекта при перемещении его через систему. Пример "процесс клиента", показанный на рис. 3.4. На этом рисунке видно взаимодействие между двумя процессами клиентов, поскольку клиент n + 1 отсрочен, пока событие "окончания обслуживания" предыдущего клиента не произойдет. Обычно много процессов одновременно активно в модели и взаимодействие между процессами может быть весьма сложным.

В пакетах моделирования, как правило, в основу выполнения положен подход взаимодействия процессов, но он обычно скрытый от взгляда разработчика моделей. События планируются в списке будущих событий и объекты помещаются в списки всякий раз, когда они стоят перед задержками, причем один процесс временно приостанавливает свое выполнение, в то время как другие процессы продолжаются. Важно, что бы разработчик модели понимал основные концепции для используемого пакета моделирования, и детально понимал встроенные, но скрытые правила операций. Schriber и Brunner [1998] дают пояснения по этому поводу.

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

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

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

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

B действия - происходят обязательные действия; все первичные события и безусловные действия.

C действия - действия или события, которые являются условными для некоторых условий, которые могут быть истинными.

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

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

Стадия B. Выполняет все события B-типа, которые были удалены из СБС. (Она может освобождать множество ресурсов или иначе - изменять состояние системы.)

Стадия C. Сканирует условия, которые запускают каждое действие C-типа и активизируют любое, чьи условия выполнены. Повторное сканирование не может начаться ни для каких дополнительных действий C-типа или событий, которые происходят.

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

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

B действия - происходят ограниченные действия; все первичные события и безусловные действия.

C действия - действия или события, которые являются условными для некоторых условий, которые могут быть истинными.

Действия B-типа и события могут быть намечены раньше срока, так же как в случае подхода с планированием. Это позволяет продвигать переменную времени. СБС содержит только события B-типа. Сканирование, чтобы проверить, могут ли любые действия C-типа начинаться или события C-типа, происходят, происходит только в конце продвижения времени, после того, как все события B-типа завершились. Таким образом, в подходе с тремя стадиями моделирование продолжает повторять выполнение этих трех стадий, пока оно не закончится:

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

Стадия B. Выполняет все события B-типа, которые были удалены из СБС. (Она может освобождать множество ресурсов или иначе изменять состояние системы.)

Стадия C. Сканирует условия, которые запускают каждое действие C-типа и активизируют любое, чьи условия выполнены. Повторное сканирование не может начаться ни для каких дополнительных действий C-типа или событий, которые происходят.

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

ПРИМЕР 1.2 (Снова возвращение к Эйбл (Able) и Бейке (Baker).

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

Таблица

Действия	Условия
время обслуживания Эйблем время обслуживания Бейке	клиент находится в очереди и Эйбл - свободный клиент находится в очереди и Бейке - свободный, а Эйбл - занят

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

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

1.3 Ручное моделирование, использующее планирование событий

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

Рис.1.4. Два взаимодействующих требования обрабатываются в очереди с одним обслуживающим приборам

Пример 1.3 (Один прибор обслуживания с очередью)

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

Состояние системы. LQ (t), LS (t), где LQ (t) - число клиентов в очереди ожидания и LS (t) - обслуживаемое число (0 или 1) во время t.

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

События

Прибытие (A)

Уход (D)

Событие останова (E), запланировано произойти во время 60.

Намеченные события

(A, t) - представляет событие прибытия, которое произойдет в будущее время t.

(D, t) - представляет уход клиента в будущее время t.

( E, 60) - представляет событие останова моделирования в будущее время 60.

Действия

Время между прибытиями определено в табл. 2.6.

Время обслуживания определено в табл. 2.7.

Время задержки требования i, потраченное на ожидание в очереди.

Намеченные события записаны как (тип события, время события). В этой модели СБС будет всегда содержать или два или три намеченных события. Эффект прибытия и ухода событий сначала были показаны на рис. 2.2 и 2.3 и показываются более подробно на рис. 3.5 и 3.6.

Таблица моделирования для контрольного прилавка дана в табл. 3.1. Читатель должен охватить все системные состояния, за исключением одного начального - первого, и попытаться создавать следующее состояние из предыдущего и логики события на рис. 3.5 и 3.6. Времена между прибытием и времена обслуживания будут идентичны, используемым в табл. 2.10, а именно:

Таблица 3.1 моделирования для контрольного прилавка (Пример 3.3)

ЧАСЫ	Состояние системы	Список будущих событий	Комментарий	Накопленная статистика
	LQ(t)	LS(t)
					B	MQ
0	0	1	(D,4) (A,8) (E,60)	Первое А происходит (a* = 8) планировать следующее А (s* = 4) планировать следующее D	0	0
4	0	0	(A,8) (E,60)	Первое D происходит (D,4)	4	0
8	0	1	(D,9) (A,14) (E,60)	Второе А происходит: (А,8) (a* = 6) планировать следующее А (s* = 1) планировать следующее D	4	0
9	0	0	(A,14) (E,60)	Второе	5	0
14	0	1	(A,15) (D,18) (E,60)	Третье А происходит: (А,14)	5	0
15	1	1	(D,18) (A,23) (E,60)	Четвертое А происходит: (А,15) (требование удалено)	6	1
18	0	1	(D,21) (A,23) (E,60)	Третье D происходит: (D,18) (s* = 3) планировать следующее D	9	1
21	0	0	(A,23) (E,60)	Четвертое D происходит: (D,21)	12	1

Как только закончено мгновенное состояние в нулевой момент времени (ЧАСЫ = 0), начинается моделирование. Во время 0, неизбежное событие - (D, 4). ЧАСЫ продвинуты на время 4, и (D, 4) удалено из СБС. Позже LS(t) = 1 для 0 t 4 (то есть, обслуживающий прибор был занят в течение 4 минут), накопленное время занятости увеличено с B = 0 до B = 4. Логика события на рис. 3.6 устанавливает LS(4) = 0 (прибор становится свободным). СБС оставлен только с двумя будущими событиями (A, 8) и (E, 0). ЧАСЫ моделирования затем продвинуты ко времени 8 и выполненному событию прибытия. Интерпретация оставшейся части табл. 3.1 оставлена для читателя.

Моделирование в табл. 3.1 охватывает временной интервал [0; 21]. В имитируемое время 21, система пуста, но следующее поступление произойдет в будущее время 23. Прибор был занят для 12 из этих 21 имитируемых тактов, и максимальная длина очереди была равна единице. Это моделирование, конечно, слишком короткое, чтобы позволить нам сделать любые надежные заключения. Упражнение 1 просит читателя продолжить моделирование и сравнить результаты с теми, что в Примере 2.1. Обратите внимание, что таблица моделирования дает системное состояние всегда, не только для перечисленных времен. Например, с момента времени 15 до времени 18, имеется одно требование в процессе обслуживания и одно в очереди ожидания.

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

ПРИМЕР1.4 (Моделирование контрольного прилавка, продолжение)

Предположим, что при моделировании контрольного прилавка в Примере 3.3 аналитик моделирования желает оценить среднее время ответа и среднее число требований, которые тратят 4 или более количество минут в системе. Время ответа - отрезок времени, которое требование проводит в системе. Чтобы оценивать это среднее число требований, необходимо расширить модель для Примера 3.3, чтобы явно представить индивидуальные требования. Кроме того, чтобы можно было вычислять время ответа индивидуального требования, когда это требование убывает, будет необходимо знать время прибытия требования. Поэтому, объект - требование со временем прибытия как атрибутом будет добавлен к списку компонентов модели в Примере 3.3. Эти объекты - сообщения будут сохранены в списке, который будет назван СПИСОК ОЧЕРЕДНОСТИ, а они будут названы C1, C2, C3,... Наконец, сообщения событий в СБС будут расширены, чтобы указать, какое требование действует. Например, (D, 4, C1) означает, что требование С1 убывает во время 4. Дополнительные модельные компоненты перечислены ниже:

Объекты (Ci, t), представляют требование Сi, которое достигло времени t.

Уведомление о событии.

( A; t; Ci) - прибытие требования Сi в будущее время t.

( D; t; Cj) - убытие требования Cj в будущее время t.

Установка "СПИСКА ОЧЕРЕДНОСТИ" - множество всех требований в настоящее время у контрольного прилавка (обслуживаемых или ожидающих обслуживания), упорядоченных по времени прибытия.

Три новых накопленных статистики будут собраны: S - сумма времен ответа для всех требований, которые убыли к текущему времени; F - общее количество требований, которые провели 4 или более минут у контрольного прилавка; и ND - общее количество убытий требований до текущего времени моделирования. Эти три накопленных вычисляемых статистики будут изменяться всякий раз, когда происходит событие убытия требований; логика для сбора этих статистических вычислений была бы включена в шаг 5 для события убытия требования на рис. 3.6.

Таблица моделирования примера 3.4 показана в табл. 3.2. Те же самые данные для временного интервала между требованиями и времени обслуживания будут использоваться снова, так что табл. 3.2 по существу повторение табл. 3.1, за исключением того, что включены новые компоненты, и столбец комментария был удален. Эти новые компоненты необходимы для вычисления накопленных статистик S, F и ND. Например, во время 4 событие убытия требований происходит для клиента С1. Объект клиент C1 удален из списка, с названием "СПИСОК ОЧЕРЕДНОСТИ", атрибут отмеченного времени прибытия был 0, так что время ответа для этого клиента было 4 мин. Следовательно, S увеличено до 4 минут и F, и ND увеличены на одного клиента. Точно так же во время 21, когда событие убытия требовании (D, 21; C4) выполняется, время ответа для клиента С4 вычислено как

Время ответа = ПОКАЗАНИЯ ЧАСОВ - атрибут "время прибытия"

= 21 15

= 6 минут

Тогда S увеличено до 6 минут, а F и ND на одного клиента.

Для длины прогона модели 21 минута, среднее время ответа было S/ND = 15/4 = 3,75 минуты, и зарегистрированное число клиентов, которые провели 4 или более минут в системе, было F = ND = 0,75. Опять же, это моделирование было слишком коротким для оценивания этих величин с любой степенью точности. Цель Примера 3.4, однако, состояла в том, чтобы иллюстрировать понятия, которые во многих моделях информационных систем желательны при моделировании (как, например статистические вычисления S = ND и F = ND) определяют до некоторой степени структуру модели.

Таблица 3.2 моделирования для примера1.4

ЧАСЫ	Состояние системы	Список «СПИСОК ОЧЕРЕДНОСТИ»	Список будущих событий	Накопленная статистика
	LQ(t)	LS(t)
					S	ND	F
0	0	1	(С1, 0)	(D, 4, С1) (А, 8, С2) (Е, 60)	0	0	0
4	0	0		(А, 8, С2) (Е, 60)	4	1	1
8	0	1	(С2, 8)	(D, 9, С2) (А, 14, С3) (Е, 60)	4	1	1
9	0	0		(А, 14, С3) (Е, 60)	5	2	1
14	0	1	(С3, 14)	(А, 15, С4) (D, 18, С3) (Е, 60)	5	2	1
15	1	1	(С3, 14) (С4, 15)	(D, 18, С3) (А, 23, С5) (Е, 60)	5	2	1
18	0	1	(С4, 15)	(D, 21, С3) (А, 23, С5) (Е, 60)	9	3	2
21	0	0		(А, 23, С5) (Е, 60)	15	4	3

ПРИМЕР 1.5 (Проблема автосамосвала)

Шесть автосамосвалов используются для доставки угля от въезда маленькой шахты на железную дорогу. Рисунок 3.7 представляет схематично операции автосамосвала. Каждый самосвал загружается одним из двух погрузчиков. После загрузки, самосвал немедленно перемещается на весы для взвешивания. Оба погрузчика и весы используют правило "первый пришел - первый обслужился" (или в порядке ожидания в очереди) для самосвалов. Время перемещения от погрузчика до весов считается незначительным. После взвешивания, самосвал начинает перемещение (учитывается только время, в течение которого самосвал разгружается) и затем возвращается в очередь к погрузчику. Распределение времени загрузки, времени взвешивания и времени перемещения даны в табл. 3.3, 3.4 и 3.5, соответственно, вместе с назначением случайных чисел для генерации этих переменных, (используются случайные числа из табл. 1). Цель моделирования состоит в оценке загрузки и коэффициента использования весов (процент времени занятости). Модель имеет следующие компоненты:

Системные состояния:

[LQ (t), L (t), WQ (t)/, W (t)],

где LQ(t) = число самосвалов в очереди загрузки;

L(t) = числу загружаемых самосвалов (0, 1, или 2);

WQ (t) = число самосвалов в очереди к весам;

W (t) = число самосвалов на взвешивании (0 или 1), для всего времени моделирования t.

Намечаемые события:

(ALQ, t, DTi) - самосвал i, поступление в очередь загрузки (ALQ) во время t;

(EL, t, DTi) - самосвал i, конец загрузки (EL) во время t;

(EW, t, DTi) - самосвал i, конец взвешивания (EW) во время t;

Объекты: шесть самосвалов (DT 1, … , DT 6).

Списки:

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

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

Действия:

время загрузки, время взвешивания и время перемещения.

Задержки:

Задержка в очереди загрузки и задержка в весовой.

Распределение времени взвешивания для самосвалов

Таблица 3.4

Время взвешивания	Вероятность	Кумулятивная вероятность	Присвоение случайного числа
12	0,70	0,70	1 - 7
16	0,30	1,00	8 - 0

Распределение времени поездки для самосвалов

Таблица 3.5

Время поездки	Вероятность	Кумулятивная вероятность	Присвоение случайного числа
40	0,40	0,40	1 - 4
60	0,30	0,70	5 - 7
80	0,20	0,90	8 - 9
100	0,10	1,00	0

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

Таблица

Время загрузки	10	5	5	10	15	10	10
Время взвешивания	12	12	12	16	12	16
Время перемещения	60	100	40	40	80

Когда происходит событие конец загрузки (EL), говорят для самосвала j во время t, другие события могут быть запущены. Если весы свободны [W(t) = 0], самосвал j начинает взвешивание и событие конец взвешивания (EW) намечено в СБС; иначе, самосвал j присоединяется к очереди для взвешивания. Если в это время имеется другой самосвал, ожидающий загрузки, то он будет удален из очереди загрузки и начнет загрузку и запланирует событие конца загрузки (EL) в СБС. Эта логика для наступления события конца загрузки, также соответствует логике для других двух событий, и должна быть включена в диаграмму события как на рис. 3.5 и 3.6 из Примера 3.3. Построение этих логических схем событий оставлено как упражнение для читателя (Упражнения 2).

Для помощи читателю в табл. 3.6 всякий раз, когда новое событие намечено, время этого события, записано как «t + (время действия)». Например, во время 0, предстоящее событие EL - событие со временем события 5. Часы переводятся на время t = 5, самосвал 3 присоединяется к очереди на взвешивание (так как весы заняты), и самосвал 4 начинает загружаться. Таким образом, EL - намеченное событие для самосвала 4 в будущее время 10, вычисленное как (настоящее время) + ( время загрузки) = 5 + 5 = 10.

Чтобы оценивать коэффициенты использования погрузчиков и весов используются две накапливаемые статистики:

BL = полное время занятости обоих погрузчиков от времени 0 до времени t;

BS = полное время занятости весов от времени 0 до времени t.

Так как оба погрузчика заняты со времени 0 до времени 20, BL = 40 во время t = 20.

Но со времени 20 до времени 24 занят только один погрузчик; таким образом, BL увеличивается только на 4 минуты за временной интервал [20, 24]. Точно так же со времени 25 до времени 36, оба погрузчика свободны (от L(25) = 0), так что BL не изменяется. Для относительно короткой имитации в табл. 3.6, коэффициенты использования оценены следующим образом:

среднее коэффициент использования погрузчика =

среднее коэффициент использования весов =

Таблица моделирования для операций самосвалов (Пример 3.5)

Таблица 3.6

ЧАСЫ t	Состояние системы	Списки	Список будущих событий	Накопленная статистика
	LQ(t)	L(t)	WQ(t)	W(t)	Очередь на загрузку	Очередь к весам
								BL	BS
0	3	2	0	1	DT4 DT5 DT6		(EL, 5, DT 3) (EL, 10, DT 2) (EW, 12, DT 1)	0	0
5	2	2	1	1	DT5 DT6	DT3	(EL, 10, DT 2) (EL, 5 + 5, DT 4) (EW, 12, DT 1)	10	5
10	1	2	2	1	DT6	DT3 DT2	(EL, 10, DT 4) (EW, 12, DT 1) (EL, 10 + 10, DT 5)	20	10
10	0	2	3	1		DT3 DT2 DT4	(EW, 12, DT 1) (EL, 20, DT 5) (EL, 10 + 15, DT 6)	20	10
12	0	2	2	1		DT2 DT4	(EL, 20, DT 5) (EW, 12 + 12, DT 3) (EL, 25, DT 6) (ALQ, 12 + 60, DT 1)	24	12
20	0	1	3	1		DT2 DT4 DT5	(EW, 24, DT 3) (EL, 25, DT 6) (ALQ, 72, DT 1)	40	20
24	0	1	2	1		DT4 DT5	(EL, 25, DT 6) (EW, 24 + 12, DT 2) (ALQ, 72, DT 1) (ALQ, 24 + 100, DT 3)	44	24
25	0	0	3	1		DT 4 DT5 DT6	(EW, 36, DT 2) (ALQ, 72, DT 1) (ALQ, 124, DT 3)	45	25
36	0	0	2	1		DT5 DT6	(EW, 36 + 16, DT 4) (ALQ, 72, DT 1) (ALQ, 36 + 40, DT 2) (ALQ, 124, DT 3)	45	36
52	0	0	1	1		DT6	(EW, 52 + 12, DT 5) (ALQ, 72, DT 1) (ALQ, 76, DT 2) (ALQ, 52 + 40, DT 4) (ALQ, 124, DT 3)	45	52
64	0	0	0	1			(ALQ, 72, DT 1) (ALQ, 76, DT 2) (EW, 64 C 16, DT 6) (ALQ, 92, DT 4) (ALQ, 124, DT 3) (ALQ, 64 + 80, DT 5)	45	64
72	0	1	0	1			(ALQ, 76, DT 2) (EW, 80, DT 6) (EL, 72 C 10, DT 1) (ALQ, 92, DT 4) (ALQ, 124, DT 3) (ALQ, 144, DT 5)	45	72
76	0	2	0	1			(EW, 80, DT 6) (EL, 82, DT 1) (EL, 76 C 10, DT 2) (ALQ, 92, DT 4) (ALQ, 124, DT 3) (ALQ, 144, DT 5)	49	76

Эти оценки не могут считаться точными оценками коэффициентов использования погрузчиков и весов как для длительного установившегося процесса; значительно более длинная имитация была бы необходима для уменьшения эффекта принятых условий во время 0 (пять из этих шести самосвалов на загрузке) и получить точные оценки. С другой стороны, если аналитик интересовался так называемым переходным поведением системы в течение короткого периода времени (обычно 1 или 2 часа) для данных исходных условий, то результаты в табл. 3.6 можно рассматривать как репрезентативные (или образованные одной выборкой) для этого переходного поведения. Дополнительные примеры могут быть получены, проводя дополнительные имитации при тех же самых исходных данных, но с использованием различных потоков случайных чисел для генерации времени действий.