Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Событийный подход к построению алгоритма модели

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

"определение очередного события – моделирование реакции системы на это событие".

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

Рассмотрим возникающие проблемы на примерах двухканальных систем массового обслуживания (СМО). Для конкретности предположим, что это системы вида (M/M/2):(ПерППО/N/ ¥), где N <¥ - максимальное допустимое количество клиентов в системе.

Здесь и далее мы придерживаемся расширенных обозначений Кендалла [4] (a/b/c):(d/e/f), используемых для классификации СМО: а – распределение моментов поступления заявок на обслуживание (в рассматриваемом примере символ М означает пуассоновское распределение); b – распределение времени обслуживания; с – число параллельно обслуживающих узлов; d – дисциплина очереди (в рассматриваемом примере: ПерППО - "первым пришел, первым обслужен"); е – максимальное число допускаемых в систему требований (в рассматриваемом примере это число предполагается конечным); f – емкость источника, генерирующего заявки на обслуживание.

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

Зададим следующие бихевиоральные (поведенческие) характеристики СМО:

· внутри банка клиенты разделяются на две очереди – по кассирам;

· если клиент приходит в банк при условии, что в это время в банке находится N клиентов, то он уходит (не ждет своей очереди вне банка);

· клиент становится в очередь к тому кассиру, у которого меньше очередь; если очереди одинаковые, то кассир выбирается случайно (равновероятно);

· если в данный момент времени один кассир завершил обслуживание очередного клиента и очередь к нему стала на j ³2 клиентов меньше, чем у другого кассира, то последний клиент из очереди другого кассира с вероятностью qj переходит в хвост другой очереди (величины qj при j ³2 считаются заданными), при этом будем полагать, что клиент переходит в другую очередь до того, как освободившийся кассир приступает к обслуживанию следующего клиента.

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

· событие прибытия в банк очередного клиента (соответствующий тип событий будем обозначать символом Спк , а соответствующие моменты времени - tпк);

· событие окончания обслуживания очередного клиента (соответствующий тип событий будем обозначать символом Сiок , а соответствующие моменты времени - tiок, где i – номер кассира);

Центральными в событийном подходе являются три основных алгоритма модели:

· алгоритм задания начального состояния системы и внешней среды;

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

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

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

Рассмотрим третий алгоритм. Состояние системы будем описывать следующими параметрами: п 1, п 2, k 1, k 2, где ki – состояние i -го кассира (0 – не занят; 1 – занят).

Основные блоки алгоритма:

при реализации события типа Спк:

· если п 1 + п 2 = N, то состояние системы не меняется;

· если п 1 + п 2 < N, то в соответствии со сформулированными выше допущениями:

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

- очередной клиент включается в очередь (к i -му кассиру): пi:= пi +1;

- если i -й кассир был свободен, то меняется его состояние ki:= 1.

при реализации события типа Сiок:

· длина i -й очереди уменьшается: пi:= пi -1 (пусть для определенности i =1);

· определяется разность т = п 2 - п 1 и если т ³2, то определяем, переходит или нет последний клиент из другой очереди в данную; если да, то: п 1:= п 1+1, п 2:= п 2 -1;

· если пi =0, то соответствующий кассир переводится в состояние ki:= 0.

Рассмотрим первый алгоритм – задание начального состояния системы (кассиры и ожидающие в очереди и обслуживаемые клиенты) и внешней среды (совокупность потенциальных клиентов)

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

n1:= 0; n2:= 0; k1:= 0; k2:= 0; tnk:= G(t0),

где G – алгоритм определения очередного момента появления клиента в банке с учетом предыдущих моментов и момента t 0 начала работы банка.

Рассмотрим второй алгоритм. Именно этот алгоритм в сложных задачах часто порождает наиболее принципиальные проблемы моделирования.

Ключевым моментом построения алгоритма является упорядочение моментов реализации основных событий. Соответственно, в качестве основных моделируемых характеристик следует принять моменты реализации основных событий различных типов. Для хранения моментов используется массив TOC [1.. Noc, 1..2]: TOC [ i, 1] – момент времени, TOC [ i, 2] – тип события. Важным является вопрос о количестве Noc, особых событий одновременно хранимых в массиве.

Основные особенности анализа хронологии событий мы рассматривали в курсе "Теория игр и исследование операций". Студенты должны повторить соответствующий материал. Здесь же приведем только результат анализа – описание типового шага цикла определения последовательности основных событий.

(1) из массива ТОС выбирается самый ранний момент времени, определяется тип соответствующего события;

(2) если очередное основное событие оказалось событием типа Спк, то:

- если k 1=0 и k 2=0, или k 1=0 и k 2=1, или k 1=1 и k 2=0 (то есть если множество свободных кассиров не пусто), то выбираем свободного кассира (i -го), к которому очередной клиент станет на обслуживание. Система переводится в состояние ki =1, ni = 1. Массив пополняется моментами реализации основных событий типа Спк и Сiок и очищается от информации об обработанном событии типа Спк;

- если k 1=1 и k 2=1 и n < N, то выбираем кассира (i -го), к которому очередной клиент станет в очередь, система переводится в состояние ni = ni + 1; массив ТОС пополняется моментом реализации очередного основного события типа Спк и очищается от информации об обработанном событии типа Спк;

- если k 1=1 и k 2=1 и n = N, то состояние системы не изменяется; массив ТОС пополняется моментом реализации очередного основного события типа Спк и очищается от информации об обработанном событии типа Спк;

(3) если очередное основное событие оказалось событием типа Сiок, то (номер другого кассира обозначим через j):

- если ni =1, то система переводится в состояние ki =0, ni =0; массив ТОС очищается от информации об обработанном событии типа Сiок;

- если ni >1, то система переводится в состояние ki =1, ni = ni -1; массив ТОС пополняется моментом реализации очередного основного события типа Сiок и очищается от информации об обработанном событии типа Сiок;

- (это действие является общим заключительным в п.3) определяется разность т = пj - пi и если т ³2, то определяется, переходит или нет последний клиент из j -й очереди в i -ю; если да, то пi:= пi +1, пj:= пj -1. Если пi:= 1, то массив ТОС пополняется моментом реализации очередного основного события типа Сiок.

В данном случае массив ТОС заполняется не более чем тремя моментами реализации основных событий трех возможных типов.

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

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

В этом случае переменные k, отображающие состояния кассиров, будут принимать три значения: 1 – кассир обслуживает клиента, 0 – кассир свободен и готов обслужить клиента, –1 – кассир отдыхает. В число основных событий необходимо включить событие "переход кассира от отдыха к готовности обслужить клиента" – Сiрк.

Типовой шаг цикла анализа последовательности основных событий будет таким:

(1) из массива ТОС выбирается самый ранний момент времени, определяется тип соответствующего события;

(2) если очередное основное событие оказалось событием типа Спк, то действия подобны предыдущему случаю. Следует только учесть дополнительное состояние кассира – "отдых" и, соответственно, тот факт, что во время отдыха обоих кассиров очередь может накапливаться. Поэтому условие n < N необходимо проверять и в том случае когда оба кассира отдыхают;

(3) если очередное основное событие оказалось событием типа Сiок, то:

- система переводится в состояние ki =–1, ni = ni -1;

- массив ТОС пополняется моментом реализации очередного основного события типа Сiрк и очищается от информации об обработанном событии типа Сiок;

- определяется разность т = пj - пi и если т ³2, то определяется, переходит или нет последний клиент из j -й очереди в i -ю; если да, то: пi:= пi +1, пj:= пj -1. Если пi = 1, то массив ТОС пополняется моментом реализации очередного основного события типа Сiок;

(4) если очередное основное событие оказалось событием типа Сiрк, то:

- если ni =0, то система переводится в состояние ki =0; массив ТОС очищается от информации об обработанном событии типа Сiрк;

- если ni >0, то система переводится в состояние ki =1; массив ТОС пополняется моментом реализации очередного основного события типа Сiок и очищается от информации об обработанном событии типа Сiрк.

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

Замечание: выше мы, фактически, не интересовались состояние отдельных клиентов. Для нас важным был только вопрос: занят ли кассир, то есть, имеется ли среди клиентов обслуживаемый в данный момент времени и сколько всего клиентов в очереди? Чтобы подсчитать более детальные характеристики, например, подсчитать, сколько клиентов было обслужено, следует подсчитать, сколько раз наступало событие Сок.

<== предыдущая лекция | следующая лекция ==>
Общие положения. Організаційна структура митної системи України | Подход сканирования активностей
Поделиться с друзьями:


Дата добавления: 2014-01-11; Просмотров: 383; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.024 сек.