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

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

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

Пример 3.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, а именно:

Время поступления	8 6 1 8 3 8 . . .
Время обслуживания	4 1 4 3 2 4 . . .

Да

Нет

Шаг 4

Рис. 3.5 Выполнение события поступления

Происходит событие убытия ЧАСЫ = t

Шаг 3

Шаг 3

Установить

LS(t) = 0

Уменьшить LQ(t) на 1

Нет

Да

LQ(t)>0 ?

Шаг 4

Сгенерировать время обслужи-вания t + s^* наметьте новое событие ухода на время t + s*

Шаг 5

Собрать статистику

Управление возвратить к про-грамме продвижения времени, продолжить моделирование

Рис. 3.6 Выполнение события ухода

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

Таблица 3.1

ЧАСЫ	Состояние системы		Список будущих событий	Комментарий	Накопленная статистика
	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). Прошлые мгновенные состояния должны игнорироваться при продвижении часов. Текущее мгновенное состояние должен содержать всю информацию, необходимую для продолжения моделирования.

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

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

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

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

( A; t; C_i) – прибытие требования С_i в будущее время t.

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

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

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

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

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

= 21 – 15

= 6 минут

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

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

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

Таблица 3.2

ЧАСЫ	Состояние системы		Список “СПИСОК ОЧЕРЕДНОСТИ”	Список будущих событий	Накопленная статистика
	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

ПРИМЕР 3.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.

Рис. 3.7 Проблема автосамосвала

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

(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.

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

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

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

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

Но со времени 20 до времени 24 занят только один погрузчик; таким образом, B_L увеличивается только на 4 минуты за временной интервал [20, 24]. Точно так же со времени 25 до времени 36, оба погрузчика свободны (от L(25) = 0), так что B_L не изменяется. Для относительно короткой имитации в табл. 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 можно рассматривать как репрезентативные (или образованные одной выборкой) для этого переходного поведения. Дополнительные примеры могут быть получены, проводя дополнительные имитации при тех же самых исходных данных, но с использованием различных потоков случайных чисел для генерации времени действий.

Таблица 3.6 моделирования для операции автосамосвала, могла быть несколько упрощена не явно моделируя автосамосвалы как объекты. То есть уведомления о событии могли быть написаны как (EL, t) и так далее, и событийные переменные отслеживали просто номера самосвалов в каждой части системы, где некоторые самосвалы участвовали. При таком представлении могли быть собраны те же самые статистические вычисления коэффициентов использования. С другой стороны, если оценивалось бы среднее "системное" время пребывания или соотношение самосвалов, проводящих больше чем 30 минут в "системе" (где "система" относится к очереди загрузки и погрузчикам, а так же к очереди на взвешивание и весам), тогда объектам автосамосвалы, были бы необходимы атрибуты (DTi) равные времени прибытия в очередь загрузки. Всякий раз, когда самосвал оставлял бы весы, время пребывания самосвала могло быть вычислено как текущее модельное время (t) минус атрибут времени прибытия. Это новое время пребывания использовалось бы для модификации вычислений для накопленных статистик: S = полное время пребывания всех самосвалов, которые были в "системе" и F = число самосвалов, время пребывания которых было больше чем 30 минут. Этот пример снова иллюстрирует понятие, что до некоторой степени сложность модели зависит от оцениваемых критериев качества работы.

ПРИМЕР 3.6 (Повторно обращение к проблеме самосвала)

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

Действия	Условия
Время загрузки	Самосвал – впереди очереди загрузки и, по крайней мере, один погрузчик свободен.
Время взвешивания	Самосвал – впереди очереди на взвешивания и взвешивающие весы свободны.
Время перемещения	Самосвал только что завершил взвешивание.

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

Рис. 3.8 Процесс автосамосвала