Как имитировать поведение системы с одной очередью в виде одноканальной системы массового обслуживания ( на языке GPSS/H)
Самым распространенным методом имитационного моделирования остается описание поведения системы на специализированном языке GPSS. В нем поведение системы имитируется движением транзактов через блоки, которое управляется специальными операторами. Транзакты соответствуют заявкам в системе массового обслуживания – заготовкам, полуфабрикатам, средствам транспорта и т. п. Блоки соответствуют операциям, выполняемым обслуживающими приборами. Перемещаясь от одного блока к другому, транзакты имитируют процессы преобразования заявок обслуживающими приборами. В процессе моделирования транзакты взаимодействуют с блоками, которые изменяют их атрибуты.
Блок GENERATE (ГЕНЕРИРОВАТЬ) вырабатывает транзакты, которые будут двигаться через блоки модели. Транзакты появляются через некоторый интервал поступления, представляющий собой сумму случайного числа по заданному закону распределения с текущим значением времени. Функцию распределения интервалов поступления транзактов задает пользователь, обращаясь к встроенным датчикам случайных чисел. После названия блока в скобках указывают 5 операндов ( табл. ).
Операнд | Значение | По умолчанию |
A | Средний интервал времени поступления транзактов( случайное число, целое число) | 0 |
B | Разброс значений времени относительно среднего интервала в одну сторону, целое число | 0 |
C | Момент времени появления первого транзакта (остальные появляются по распределению, заданному A и B) , целое число | нет |
D | Ограничение общего числа транзактов, поступивших из блока за заданное время | нет |
E | Один их 127 уровней приоритета каждого поступившего транзакта | 0 |
Так, запись GENERATE ( 5,1 ) показывает, что транзакты появляются через 5±1 мин.
Блок Terminate ( ЗАВЕРШИТЬ) отображает удаление транзактов из модели. После названия блока в скобках указывают операнд А – счетчик завершения, который задает величину, на которую уменьшается значение счетчика каждый раз, когда транзакт входит в этот блок.
Завершить моделирование в GPSS можно двумя способами:
- заканчивать моделирование после прохождения заданного числа транзактов;
- заканчивать моделирование по истечении заданного времени.
По первому способу операнду А в блоке START присваивают конечное число транзактов, операнду А в блоке Terminate, через который транзакты определенного типа покидают модель, присваивают число, соответствующее типу транзакта, операнду А в других блоках Terminate присваивают А=0. Например, запись:
Terminate 1
START 20
показывает, что моделирование закончится, когда через модель пройдут 20 транзактов.
По второму способу задают единицу модельного времени, например 1 мин., и длительность моделирования, например 60 минут:
- вводят в модель счетчик модельного времени - два блока, ограничивающих время моделирования:
GENERATE 60
Terminate 1
- во всех других блоках Terminate задают А=0;
- в блоке START задают А=1.
Это приведет к тому, что завершение движения транзактов в других блоках Terminate не повлияет на счетчик завершения. Через 60 единиц модельного времени транзакт выйдет из блока GENERATE и перейдет в блок Terminate, что приведет к уменьшению значения счетчика завершения на единицу и прекращению моделирования.
Процесс обслуживания заявки прибором (станком, кассиром и т. п.) отображается блоком задержки транзакта в приборе ADVANCE ( ПРОДВИНУТЬ). Он имеет два операнда:
А - среднее время задержки (при равномерном законе распределения);
В - время отклонения от среднего времени задержки ( в одну строну)
Например, ADVANCE 3.75,1
показывает, что транзакт задержится в приборе на модельное время 2По умолчанию оба операнда имеют нулевое значение. Блок ADVANCE задерживает продвижение транзакта на некоторое время, обычно случайное.
Для имитации обслуживания транзакта некоторым прибором А используют блоки SEIZE ( ЗАНЯТЬ) и RELEASE (ОСВОБОДИТЬ) . Блок SEIZE означает занятие прибора А, указанного в операнде блока, а блок RELEASE - освобождение прибора А от обслуживания транзакта.
Процесс обслуживания описывается одной из трех схем:
1.Прибор как единица
SEIZE UNIT
ADVANCE 10,2
RELEASE UNIT,
что означает «транзакт занял прибор UNIT, задержался в нем на время 8-12 единиц и освободил прибор UNIT».
2.Прибор является субблоком UNIT в блоке SERVER
SEIZE SERVER
ADVANCE 20, 4
SEIZE UNIT
ADVANCE 10.2
RELEASE UNIT
RELEASE SERVER
что означает «транзакт занял блок SERVER стал обслуживаться субблоком UNIT в течение 8-12 единиц времени, затем одновременно освободил субблок UNIT и блок SERVER».
Если программа написана так, что транзакт освобождает прибор, занятый другим транзактом, то интерпретатор GPSS выдаст сигнал ошибки.
3. Прибор используется несколько раз
SEIZE UNIT
ADVANCE 25, 4
RELEASE UNIT
ADVANCE 10,2
SEIZE UNIT
ADVANCE 12,3
RELEASE UNIT
что означает «транзакт дважды занимает и освобождает прибор UNIT».
Оператор START (НАЧАТЬ) имеет 4 операнда ( табл. )
Операнд | Значение | По умолчанию |
А | Начальное значение счетчика завершения | |
B | ||
C | ||
D |
Программа на языке GPSS может быть составлена в виде последовательности блоков, а затем написана в виде последовательности команд, отображающих блоки. В таблице показано соответствие графических и словесных отображений блоков.
БЛОК | ГРАФИЧЕСКОЕ ИЗОБРАЖЕНИЕ |
GENERATE |
|
TERMINATE |
|
ADVANCE |
|
SEIZE |
|
RELEASE |
|
Счетчик модельного времени в операторе START |
|
Кроме блоков, программа на языке GPSS содержит управляющие операторы. К ним относятся: SIMULATE (начать имитацию), START ( установить значение счетчика, после которого имитация заканчивается), STORAGE ( задать число параллельно работающих приборов), FUNCTION (задать закон распределения случайных величин, дискретность или непрерывность случайной величины и число ее значений).
Построим модель в виде последовательности блоков и соответствующей последовательности команд. Пусть для оценки коэффициента использования прибора достаточно 1000 измерений.
Последовательность блоков | Последовательность команд |
| GENERATE A, B, SEIZE UNIT ADVANCE A, B RELEASE UNIT TERMINATE 1 START 1000 |
Моделирование продолжается до тех пор, пока через блок TERMINATE не пройдет 1000 транзактов.
Если прибор занят обслуживанием заявки, то поступающие к нему заявки становятся в очередь. Для оценки максимального и среднего размера очереди, среднего времени ожидания в очереди предназначены блоки QUEUE и DEPART. Блок QUEUE (встать в очередь) указывает на начало сбора информации о заявках, находящихся в очереди. Он имеет операнды А ( имя очереди) и В ( число элементов, на которое должно измениться значение содержимого очереди) .
Блок DEPART (покинуть очередь) указывает на окончание сбора информации о заявках, находящихся в очереди. Он имеет операнды А ( имя очереди) и В ( число элементов, на которое должно измениться значение содержимого очереди) .
Например, программа
GENERATE 100,400
QUEUE D
SEIZE A
DEPART D
ADVANCE 80,50
RELEASE A
TERMINATE 1
START 50
позволяет оценить время пребывания транзактов в очереди D перед блоком A.
Программа
GENERATE 100,40 QUEUE D SEIZE A ADVANCE 80,50 RELEASE A DEPART D TERMINATE 1 START 50 |
позволяет оценить общее время пребывания транзакта в приборе обслуживания A с учетом времени нахождения транзакта в очереди D.
Рассмотренных блоков достаточно для моделирования одноканальной системы массового обслуживания.
6.6. Как работать с интерпретатором GPSS/H
Интерпретатор GPSS/H® разработан ф. Wolverine Software Corporation (США) в виде студенческой (Student GPSS/H ®) и профессиональной (GPSS/H Professional®) версий. Студенческая версия является условно-платной и имеет ограничения: не более 125 блоков, не более 250 состояний, не более 32,72 Кб в памяти.
Для ввода в интерпретатор GPSS/H программу составляют в виде последовательности командных строк, каждая из которых соответствует блоку.
Командная строка содержит ( рис. ):
- имя прибора, нужное для перехода к строке из другого места модели
( не указывается, если такие переходы отсутствуют);
- оператор, показывающий выполнение определенной функции; операнды, показывающие характеристики функции; комментарии, поясняющие выполняемую функцию.
Рис. . Формат командной строки
Части строки разделяют пробелами. Программу записывают в формате ASCII П, используя любой текстовый редактор ( не Word, а WordPad или Блокнот!). Все буквы, кроме комментариев, должны быть заглавными. После написания программу называют именем из латинских букв и присваивают ей расширение. gps, например system 1 .gps. При входе в оболочку GPSS/H надо вызвать созданную программу с таким расширением.
Работа комплекса GPSS/H происходит в три фазы, отображаемые на экране:
1. Pass 1 ( with source listing) ……
Считывание исходного файла, выявление синтаксических ошибок, формирование исходного листинга программы, преобразование числовых значений в символы; если в программе допущены ошибки, интерпретатор выдает сообщение Error…
2. Pass 2 …
Преобразование модели в форму для исполнения, распределение памяти и подготовка к исполнению моделирования. Если на этом этапе нет ошибок, то происходит переход к третьей фазе;
3. Simulation begins.
Запуск модели. Если при этом нет ошибок, то формируется файл отчета с результатами моделирования, имеющий расширение. lis.
В результате работы интерпретатор GPSS/H формирует показатели имитационного эксперимента работы и регистрирует информацию о работе ее элементов: число состояний занятости прибора, коэффициент использования прибора, среднее время обслуживания заявки, время прохождения транзакта через модель.
Приведем пример из «Руководства по работе с GPSS/H» ( ф. Wolverine Software Inc., США).
1. Технологический процесс
Заготовки поступают на участок обработки с интервалом 3-5 минут ( равномерное распределение). В течение 2 минут они движутся к станку.. Обработка заготовки продолжается от 2,75 до 4,75 минут ( равномерное распределение). Сколько времени потребуется для обработки 100 заготовок? Какова средняя загрузка станка в течение обработки 100 заготовок?
2. Представим технологический процесс в виде системы массового обслуживания. Заготовки-это заявки, а станок - это обслуживающий прибор. Надо найти время обслуживания 100 заявок и среднюю загрузку прибора.
2. Программа на языке GPSS/H ( без очереди) выглядит следующим образом:
SIMULATE
GENERATE 4.1
ADVANCE 2
SEIZE SERVER
ADVANCE 3.1
RELEASE SERVER
TERMINATE 1
START 100
END
9. После проверки программы формируется файл предстоящего процесса моделирования:
STUDENT GPSS/H RELEASE 3.0j-C10 (UL2Jan 2006 12:02:06 FILE: C:\MYDOCS~1\My_docs\GPSS\GPSSHSTU\MY15.GPS
LINE# STMT# IF DO BLOCK# *LOC OPERATION A, B,C, D,E, F,G COMMENTS
1 1 SIMULATE
2 2 1 GENERATE 4.1
3 3 2 ADVANCE 2
4 4 3 SEIZE SERVER
5 5 4 ADVANCE 3.1
6 6 5 RELEASE SERVER
7 7 6 TERMINATE 1
8 8 START 100
9 9 END
ENTITY DICTIONARY (IN ASCENDING ORDER BY ENTITY NUMBER; "*" => VALUE CONFLICT.)
Facilities: 1=SERVER
SYMBOL VALUE EQU DEFNS CONTEXT REFERENCES BY STATEMENT NUMBER
SERVER 1 Facility 4 6
STORAGE REQUIREMENTS (BYTES)
COMPILED CODE: 168
COMPILED DATA: 40
MISCELLANEOUS: 0
ENTITIES: 264
COMMON: 10000
-
TOTAL: 10472
Файл разделен на четыре части:
поcледовательность исполнения программы ( начиная со Student GPSS/H);
присвоение свойств серверам (Entity dictionary....;
занятие серверов транзактами ( SYMBOL...);
использование памяти ( STORAGE REQUIREMENTS..).
Выводится размер модели и имитация начинается:
GPSS/H MODEL SIZE:
CONTROL STATEMENTS 3
BLOCKS 6
Simulation begins.
5. По окончании имитационного моделирования выводятся его результаты:
5.1.Модельное и реальное времена моделирования:
RELATIVE CLOCK: 415.1000 ABSOLUTE CLOCK: 415.1000
5.2. Число транзактов, прошедших через каждый блок:
BLOCK CURRENT TOTAL
1 101
3 100
4 100
5 100
6 100
5.3. Использование обслуживающего прибора в ходе имитационного моделирования:
--AVG-UTIL-DURING--
FACILITY TOTAL AVAIL UNAVL ENTRIES AVERAGE CURRENT PERCENT SEIZING PREEMPTING
TIME TIME TIME TIME/XACT STATUS AVAIL XACT XACT
SERVER 0.AVAIL
5.4. Использование памяти при имитационном моделировании:
STATUS OF COMMON STORAGE
9632 BYTES AVAILABLE
368 IN USE
480 USED (MAX)
6. Выводится информация об окончании имитации, использовании компьютера и разработчике GPSS/H:
Simulation terminated. Absolute Clock: 415.1000
Total Block Executions: 602
Blocks / second: 602000
Microseconds / Block: 1.66
Elapsed Time Used (SEC)
PASS1: 0.05
LOAD/CTRL: 0.22
EXECUTION: 0.00
TOTAL: 0.27
GPSS/H IS A PROPRIETARY PRODUCT OF, AND IS USED UNDER A LICENSE GRANTED BY, THE WOLVERINE SOFTWARE CORPORATION,
7617 LITTLE RIVER TURNPIKE, ANNANDALE, VIRGINIA , USA.
7. Результаты моделирования:
- время обслуживания 100 заявок - 415.1 минут обслуживающий прибор при этом будет загружен на 74,7 %.
Интерпретируем результаты моделирования как ответы на вопросы заказчика:
- для обработки 100 заготовок потребуется 415,1 минут; при этом станок будет использоваться на 74,7 %.
Для того, чтобы довести степень использования до 95 %, следует заменить станок на менее производительный ( следовательно, более дешевый). Но такое использование может быть достигнуто с образованием очереди перед станком, когда каждая заготовка ожидает обслуживания.
Если в модель введено определение размера очереди, то следует проводить имитационные эксперименты с увеличением времени обработки заготовки до образования очереди заготовок перед обработкой.
Система с несколькими очередями представляется как многоканальная система массового обслуживания, которая характеризуются емкостью, показывающей число параллельно включенных приборов в устройстве обслуживания. Емкость задается в начале моделирования оператором STORAGE (хранить). Оператор имеет операнд А, указывающий имя многоканального устройства, и операнд В, указывающий число параллельно включенных приборов.
Например, оператор
STORAGE S( E ),3/S( F ),4
показывает, что устройство обслуживания имеет три параллельных прибора S и четыре параллельных прибора F.
Блок ENTER (войти) отображает занятие В приборов из группы А параллельно работающих приборов. Например,
ENTER TOOLS,2
показывает, что транзакт занимает два прибора из группы TOOLS.
Блок LEAVE (выйти) отображает освобождение В приборов из группы А. Например,
LEAVE TOOLS, 2
показывает, что транзакт освобождает два прибора из группы TOOLS.
БЛОК | ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ |
ENTER (войти) |
|
LEAVE (выйти) |
|
QUEUE (встать в очередь) |
|
DEPART (покинуть очередь) |
|
В качестве примера составим программу, имитирующую работу роботизированного технологического комплекса, в котором три параллельно работающих станка могут одновременно обрабатывать заготовки ( разработан к. т.н. ). Блоки SEIZE и RELEASE ранее рассмотренной одноканальной системы заменены на блоки ENTER и LEAVE ( ).
Модель роботизированного технологического комплекса
Блок-схема | Программа |
| STORAGE S(RTK),3 GENERATE 100,40 ENTER RTK ADVANCE 80,50 LEAVE RTK TERMINATE 1 START 100 |
Если транзакт должен перейти не в один, а два блока, то для выбора блока вводят блок TRANSFER ( передать), который может работать в трех режимах:
· безусловная передача – транзакты переходят в следующий блок, если он свободен ( рис. )
Рис. . Блок TRANSFER в режиме безусловной передачи
В операнде А ставится запятая (,). В операнде В записывают имя блока, в который должен перейти транзакт. Например,
TRANSFER, BOX
показывает, что при занятости блока BOX транзакты остаются в блоке ТRANSFER;
· статистическая передача - выбор направления в зависимости от случайного числа ( рис. )
Рис. . Блок TRANSFER в режиме статистической передачи
В операнде А записывают число, показывающее частоту передачи транзактов в блок С. Оно должно быть больше 0 и меньше 1 и начинаться с точки. В операнде В записывают имя блока, в который переходят транзакты с частотой, записанной в операнде А. Выбор направления передачи транзакта производится с помощью датчиков равномерно распределенных случайных величин в интервале (0,1), входящих в GPSS/H. Например,
TRANSFER.25,BOX, PLAY
транзакты, входящие в блок, с вероятностью 0.25 будут переданы в блок PLAY и с вероятностью 0.75 - в блок BOX.
· передача BOTH (оба) – переход в равнозначные блоки (рис. )
Рис. . Блок TRANSFER в режиме ВОТН
В операнде А записывают слово BOTH. В операнде В записывают имя блока, в который должен перейти транзакт. Если этот блок занят, то транзакт попытается перейти в другой блок с именем, записанным в операнде С. Если и этот блок тоже будет занят, то транзакт останется в блоке TRANSFER до освобождения блока сначала с именем в операнде В, затем - с именем в операнде С. Например, запись
TRANSFER BOTH, BOX, PLAY
означает, что сначала транзакт попытается войти в блок ВОХ. Если блок ВОХ занят, то транзакт попытается войти в блок PLAY. Если этот блок тоже занят, то транзакт остается в блоке TRANSFER, пока не освободится блок BOX или блок PLAY.
Кроме того, в процессе имитации собирается информация о максимальном и среднем размерах очереди за время моделирования, общем числе транзактов в очереди, среднем времени пребывания транзакта в очереди и т. п.
В реальном производстве многие данные случайны. Они имитируются случайными интервалами времени между появлением транзактов в блоке GENERATE, случайным временем задержки транзактов в блоке ADVANCE, вероятностным выбором движения транзактов в блоке TRANSFER, вероятностной проверкой условия в блоке ТEST. По умолчанию GPSS/H генерируются псевдо-случайные числа от 0 до 1, распределенные по равномерному закону. Если для имитации требуется генерировать случайные числа по другим законам распределения, то используют встроенные в GPSS/H алгоритмы генерации случайных чисел по любому из 26 законов распределения ( бета, биномиальное, Вейбулла, дискретно-равномерное, гамма, геометрическое, Лапласа, логистическое, логлапласово, логлогистическое, логнормальное, нормальное, обратное Вейбулла, обратное Гаусса, отрицательное биномиальное, Парето, Пирсона типаV, Пирсона типа VI, Пуассона, равномерное, треугольное, Джонсона, М-Эрланга, экспоненциальное, экстремального значения А, экстремального значения В. Чаще всего применяют экспоненциальный, нормальный и треугольный законы распределения.
Дискретную или непрерывную, детерминированной и вероятностной функции. Случайную функцию задают оператором FUNCTION ( ФУНКЦИЯ). В поле имени записывают имя функции, в поле операций - слово FUNCTION. В операнде А записывают один из восьми номеров генераторов случайных чисел RN1...RN8, встроенных в интерпретатор GPSS/H. В операнде В указывают, дискретной (DN) или непрерывной (CN) будет случайная функция. N указывает число значений функции. Далее должны следовать строки определения функции со значениями суммарной частоты и соответствующими им значениями случайной переменной. Например,
GENERATE RVEXPO (1, 100.0)
вызывает случайные числа, генерируемые датчиком 1 и распределенные по экспоненциальному закону с математическим ожиданием 100.0 и дисперсией 0;
GENERATE RVNORM ( 3, 10.0, 2.0)
вызывает случайные числа, генерируемые датчиком 3 и распределенные по нормальному закону со средним 10.0 и среднеквадратичным отклонением 2.0;
ADVANCE RVTRI ( 2, 10.0, 50.0, 75.0)
показывает, что транзакт задерживается в приборе на случайное время, распределенное по треугольному закону с минимальным значением 10.0, средним значением 50.0 и максимальным значением 75.0.Значения этого времени генерируются датчиком RN2.
В языке GPSS заложено множество других возможностей, имитирующих многообразные свойства реальных процессов.
