11.4.2 Моделирование систем массового обслуживания

Одним из средств анализа систем мас­сового обслуживания является имитационное моделирование. Наиболее приспособленной для имитационного моделирования робототехнических систем можно считать общецелевую систему имитационно­го моделирования GPSS (General Purpose Simulating System – систе­ма моделирования общего назначения), являющуюся средством модели­рования на ЭВМ дискретных событий. GPSS-система представляет со­бой совокупность специального понятийного аппарата, машинного языка высокого уровня и соответствующего им системного программ­ного обеспечения.

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

Развитием системы GPSS является система имитационного моделирования дискретных систем Extend. Extend exemplifies новое поколение систем моделирования. Эта система использует графический интерфейс и позволяет анализируемую модель представлять в виде структурной схемы, которая из типовых блоков конструируется на экране дисплея.

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

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

11.4.3 Система моделирования gpss

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

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

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

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

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

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

Очередь представляет собой совокупность заявок, ожидающих обслуживания. Длина очереди характеризует эффективность обслуживания.

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

Работу такой системы можно описать следующим образом. Заявки поступают на обслуживание к прибору в случайные моменты времени. Время обслуживания прибором каждой заявки различно и также явля­ется случайной величиной. После своего появления заявка либо за­нимает прибор, если он свободен, либо ожидает обслуживания, обра­зуя очередь.

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

Функционирование системы массового обслуживания заключается в перемещении заявок. Функционирование описывается с использованием модельного времени. Для отсчёта модельного времени в системе GPSS имеется таймер.

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

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

При составлении блок-схем в качестве отдельных блоков выделяются определенные действия, совершаемые над обслуживаемыми объектами. В простейшем случае процесс обслужи­вания заявки можно представить блок-схемой, приведенной на рис. 246. Блок 1 описывает поступление новой заявки, блок 2 – ее присоединение к очереди, (присоединение к очереди может быть и нулевым). Блоки 3 и 4 фик­сируют момент, когда заявка переходит в состояние обслуживания и, следовательно, покидает очередь. Блок 5 отражает собой обслужива­ющий прибор, в нем заявка задерживается на время, необходимое для ее обслуживания. Блок 6 символизирует конец обслуживания, а блок 7 – выход заявки из модели.

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

• активном, когда он переходит от одного блока модели к другому;

• приостановленном, когда он ожидает момента модельного времени, в который он должен перейти в активное состояние;

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

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

П ри моделировании реального процесса модель может иметь нес­колько блок-схем, подобных представленной на рис. 246. Каждая такая схема оформляется как отдельный сегмент имитационной модели. Обя­зательным сегментом модели является блок-схема, отображающая мо­дельное время. Она состоит из двух блоков (рис. 247), первый из них фиксирует появление транзакта-таймера в установленный момент мо­дельного времени, а второй – его удаление из модели. Последнее является признаком завершения процесса моделирования.

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

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

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

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

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

Для описания имита­ционной модели в GPSS используются специальные операторы. Полный формат операторов языка GPSS состоит из четырех по­лей: поле имени оператора (меток); поле наименования операции; поле операндов (параметров оператора) и поле комментариев.

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

Б лок 1 описывается оператором GENERATE, который является источником тран­зактов и генерирует транзакты. В первом сегменте этот оператор является источни­ком транзактов, связанных с заявками в моделируемой системе, а во втором – транзактов-таймеров.

Для описания блока 2 использован оператор QUEUE, который сов­местно с оператором DEPART (блок 4) обеспечивает сбор статистики об очере­ди на обслуживание. Если пользователь не нуждается в та­кой статистике по данному прибору, то эти блоки можно исключить из блок-схемы.

Блок 3 с оператором SEIZE моделирует занятие транзактом обслуживаю­щего прибора, а блок 6 с оператором RELEASE – освобождение транзактом прибора. Блок 5 с оператором ADVANCE описывает в модели задержку заявки (транзакта) в обслуживающем приборе на время, необходимое для обслуживания. Блок 7 c оператором TERMINATE используется для удаления транзактов из модели после завершения их обслуживания.

Имитационная модель реальной системы массового обслуживания может содержать несколько основных сегментов и обязательно один сегмент для отсчета модельного времени. Сегмент таймера приведен на рис. 248 ниже основного сегмента и состоит всего из двух блоков GENERANE и TERMINATE.

При составлении программы GPSS операторы записываются последовательно в полном формате один под другим. Первая колонка в общем случае не используется. Если в ней помещается символ звездочка (*), то вся строка воспринимается GPSS-програм­мой как комментарий. Затем следует метка оператора не более чем из пяти символов. Метка может отсутствовать. Метка оператору присваивается лишь в том случае, если к нему имеется обращение из других частей программы.

Обязательной частью является название оператора. В качестве названий операций используются английские гла­голы, обозначающие основное действие, выполняемое данным операто­ром: PREEMPT, RETURN, LEAVE, ENTER, STORAGE и др.

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

Все части оператора разделяются пробелами. Ниже рассмотрен пример программы GPSS, который иллюстрирует основные особенности моделирования в этой системе.

Пример. В системе массового обслуживания имеется один обслуживающий прибор и заявки двух видов. Заявки первого вида поступают с интервалом модельного времени 35  5 и длительность их обслуживания составляет 20  4, а заявки второго вида поступают с интервалом 28  3 и обслуживаются в течение времени 10  2. Заявки второго вида должны обслуживаться в первую очередь. Для этих заявок необходима статистика. Общее время моделирования должно составлять 2460 единиц модельного времени (41 час реального времени).

На языке GPSS модель системы опишется следующим образом

* сегмент 1

GENERATE 35,5,,,1

SEIZE PR1

ADVANCE 20,4

RELEASE PR1

TERMINATE

* сегмент 2

GENERATE 28,3,,,2

QUEUE PR1Q

SEIZE PR1

DEPART PR1Q

ADVANCE 10,2

RELEASE PR1

TERMINATE

* сегмент 3

GENERATE 2460

TERMINATE 1

Имя обслуживающего прибора PR1, а имя очереди PR1Q. Сегмент 1 относится к заявкам первого вида, а сегмент 2 – к заявкам второго вида. Сегмент 3 обеспечивает отсчёт модельного времени.

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

FACILITY	AVERAGE UTILISATION	NUMBER ENTRIES	AVERAGE TIME/TRANS	SEIZING TRANS NO	PREEMRT ING TROES NO
1	2	3	4	5	6
5	0.571	12	643.152	17	--
ABC	0.243	15	164.247	--	48

В колонках таблицы приведена следующая информация:

1 – имя (номер) прибора;

2 – доля времени, в течение которого прибор был занят;

3 – число обслуживаний;

4 – средняя продолжительность одного обслуживания;

5 – номер транзакта, находящегося (если он есть) в данный момент на обслуживании в приборе;

6 – номер транзакта (если такой есть), который захватил прибор.

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

Выполнение моделирования в Extend производится в следующей последовательности:

1. Отбор и загрузка соответствующих библиотек с типовыми элементами блок схем.

2. Выбор в библиотеках и перенос в окно модели нужных для построения модели блоков. Задание параметров блоков с помощью вызова диалоговых окон.

3. Соединение блоков в единую структуру.

4. Запуск модели для симуляции процесса и сбор данных для дальнейшего анализа.

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