Содержание
Введение. 3
Базовые понятия и определения GPSS. 8
Постановка задачи. 12
Решение задачи. 13
Выводы.. 20
Литература. 21
Введение
Имитационное моделирование – это разновидность аналогового моделирования, реализуемого с помощью математического набора инструментальных средств, специальных моделирующих компьютерных программ и технологий программирования, позволяющих с помощью процессов-аналогов провести целенаправленное исследование структуры и функции реально существующего процесса в памяти компьютера в режиме «имитации», выполнить оптимизацию некоторых их параметров. Существует достаточно широкий круг систем, для решение которых применяются методы теории массового обслуживания. Основным методом изучения таких систем является математическое моделирование, которое приводит к построению и анализу систем массового обслуживания(СМО). В математических моделях сложных объектов, представленных в виде систем массового обслуживания , фигурируют средства обслуживания, называемые обслуживающими аппаратами (ОА), и обслуживаемые заявки, называемые транзактами. Но не менее актуальной является и задачи построения имитационных моделей СМО. Имитационная модель СМО представляет собой алгоритм, отражающий поведение СМО, т. е. отражающий изменения состояния СМО во времени при заданных потоках заявок, поступающих на входы системы. Параметры входных потоков заявок - внешние параметры СМО. Выходными параметрами являются величины, характеризующие свойства системы - качество ее функционирования. Примеры выходных параметров: производительность СМО - среднее число заявок, обслуживаемых в единицу времени; коэффициенты загрузки оборудования - отношение времен обслуживания к общему времени в каждом АО; среднее время обслуживания одной заявки. Основное свойство ОА, учитываемое в модели СМО, - это затраты времени на обслуживание, поэтому внутренними параметрами в модели СМО являются величины, характеризующие это свойство ОА. Обычно время обслуживания рассматривается как случайная величина и в качестве внутренних параметров фигурируют параметры законов распределения этой величины. Состояние СМО характеризуется состояниями ОА, транзактов и очередей к ОА. Состояние ОА описывается двоичной переменной, которая может принимать значения "занят" или "свободен". Переменная, характеризующая состояние транзакта, может иметь значения "обслуживания" или "ожидания". Состояние очереди характеризуется количеством находящихся в ней транзактов. Имитационное моделирование позволяет исследовать СМО при различных типах входных потоков и интенсивностях поступления заявок на входы, при вариациях параметров ОА, при различных дисциплинах обслуживания заявок. Дисциплина обслуживания - правило, по которому заявки поступают из очередей на обслуживание. Величина, характеризующее право на первоочередное обслуживание, называется приоритетом. В моделях СМО заявки, приходящие на вход занятого ОА, образуют очереди, отдельные для заявок каждого приоритета. При освобождении ОА на обслуживание принимается заявка из непустой очереди с наиболее высоким приоритетом. Основной тип ОА - устройства, именно в них происходит обработка транзактов с затратами времени. К ОА относятся также накопители (памяти), отображающие средства хранения обрабатываемых деталей в производственных линиях или обрабатываемых данных в вычислительных системах. Накопители характеризуются не временами обслуживания заявок, а емкостью - максимально возможным количеством одновременно находящихся в накопителе заявок. К элементам имитационных моделей СМО кроме ОА относят также узлы и источники заявок. Связи ОА между собой реализуют узлы, т. е. характеризуют правила, по которым заявки направляются к тому или иному ОА. Имитационное моделирование являются основным источником для дальнейших исследований, в случае, когда получить точное решение для СМО не представляется возможным. Для создания имитационных моделей СМО и их изучения могут быть использованы специальные системы имитационного моделирования. На сегодняшний день одна из самых распространенных систем является GPSS. Но она была создана в 60-х годах, поэтому желательна разработка новой системы имитационного моделирования на основе новых технологий программирования.
GPSS World – мощная, универсальна среда моделирования дискретных и непрерывных процессов, предназначенная для профессионального моделирования разнообразных процессов и систем.
В состав GPSS World входит язык программирования PLUS – язык программирования для моделирования, который позволяет автоматически записывать программные эксперименты.
Система обеспечивает возможность проведения экспериментов, встроенных в систему, экспериментов пользователя и оптимальных экспериментов. GPSS World оснащена процедурой мультипликационной визуализации процесса функционирования модели. GPSS World(tm) сохранил все преимущества своего предшественника - GPSS/PC(tm). Кроме этого в эту систему были введены следующие новшества:
1. Объектно-ориентированный интерфейс пользователя, включающий объекты "Модель", "Процесс моделирования", "Отчет" и "Текст".
2. Высокопроизводительный транслятор моделей.
3. Программные эксперименты с автоматическим анализом данных.
4. Многозадачность.
5. Сохранение и продолжение выполнения запущенных процессов моделирования.
6. Ввод/вывод во время выполнения процесса моделирования.
7. Свыше 20 встроенных вероятностных распределений.
8. Интегрированный язык программирования PLUS(tm).
9. Библиотека PLUS-процедур.
10. 17 различных графических окон для наблюдения за выполняющимся процессом моделирования.
11. Новые блоки языка GPSS: ADOPT, DISPLACE, PLUS и INTEGRATION.
12. Блоки OPEN, CLOSE, READ, WRITE и SEEK, обеспечивающие ввод-вывод во время моделирования.
13. Автоматическое интегрирование обыкновенных дифференциальных уравнений любого порядка.
14. Поддержка "горячих" клавиш.
15. Быстрая и удобная отладка с использованием графического интерфейса.
16. Абсолютная совместимость с GPSS/PC(tm).
17. Автоматические генераторы отсеивающих и оптимизирующих экспериментов.
18. Пакетный режим с контролируемой процедурой выхода из приложения.
19. Диалоговые окна ввода блоков.
20. Настраиваемые интервалы табуляции.
21. Возможность динамического вызова функций из внешних файлов.
В нашем случае необходимо описать процессы, протекающие; при функционировании имитационных моделей СМО. Несмотря на значительное разнообразие моделей, которые приходится строить, для их программной реализации практически всегда приходится решать ряд задач, которые являются абсолютно типичными для данного контекста. Проанализируем эти задачи.
Во-первых, имитационная модель обычно содержит некоторый источник поступления требований в систему. Кроме непосредственного моделирования поступления требований в систему, иногда на этом
уровне требуется организовать дополнительную функциональность, связанную с обработкой потока входящих требований. Например, формирование суммарного потока требований из разных источников.
Во-вторых, необходимо обеспечить выполнение обязанностей, связанных с правилами поступления и формирования очереди или очередей требований, ожидающих обслуживания. Хотя для некоторых классов СМО, например для систем с бесконечным: числом обслуживающих приборов, такая функциональность не является обязательной.
В-третьих, в модели должна существовать подсистема обслуживания требований с естественной для нес функциональностью.
И, наконец, на протяжении всей работы системы необходимо обеспечить средства, позволяющие накапливать статистически
материал о ходе работы модели, для его последующего анализа и обработки.
Такой типичный набор проблем, возникающих в типичном контексте, позволяет применять для их решения образцы, механизмы и каркасы.
Базовые понятия и определения GPSS
При построении синтаксически правильных моделей допускается использование следующих символов:
1. буквы латинского алфавита A, B, C, D, ... , Z;
2. символ $;
3. цифры 0, 1, ... , 9;
4. знаки арифметических операций +, -, /, *,@ (деление по модулю);
5. разделители . , () / (пробел).
Модели в GPSS представляют собой совокупность отдельных элементов, называемых объектами. Существуют 7 категорий и 14 типов объектов GPSS.
КАТЕГОРИИ И ТИПЫ ОБЪЕКТОВ ЯЗЫКА GPSS
Наименование категории | Наименование типа объекта |
Операционная | Блоки |
Динамическая | Сообщения |
Аппаратная | Устройства памяти Ключи |
Вычислительная | Арифметические переменные Булевские переменные Функции |
Статистическая | Очереди Таблицы |
Запоминающая | Ячейки |
Группирующая | Группы Списки |
Все объекты GPSS имеют числовые характеристики, доступные пользователю, называемые стандартными числовыми атрибутами (CЧА). На эти атрибуты можно ссылаться в процессе моделирования. Имя СЧА состоит из двух частей.
Первая часть указывает на тип объекта и тип информации о нем, вторая - идентифицирует конкретного члена группы (по номеру или символическому имени). Рассмотрим основные категории объектов системы GPSS:
ОПЕРАЦИОННАЯ. К этой категории относится единственный тип объектов - блоки. Разработчик конструирует модель из блоков, как правило, отображая ее в виде блок-схемы. Для удобства графического представления модели каждый блок GPSS имеет принятое стандартное обозначение. Построенная схема является программой на языке GPSS, а каждый блок - подпрограммой в ней. Для ввода ее в ЭВМ необходимо последовательность блоков представить в виде последовательности операций, добавив к названиям блоков требуемые операнды.
Каждый блок GPSS имеет входы и выходы, с помощью которых осуществляется их связь в модели. Существуют два особых блока: GENERATE, имеющий только выход, и TERMINATE, имеющий только вход.
ДИНАМИЧЕСКАЯ. К этой категории относятся транзакты. Функционирование объекта отображается в модели в виде перемещения транзактов от блока GENERATE в блок TERMINATE через промежуточные блоки. Транзакты (сообщения) являются абстрактными подвижными элементами, которые, перемещаясь между блоками, вызывают и испытывают различные действия. Понятие транзакта устанавливает сам разработчик модели. Например, если мы разрабатываем модель большого универмага, то в понятие транзакта можно вложить "покупатель", который, передвигаясь от отдела к отделу, движется по магазину. Транзакт -"покупатель" движется по модели и может быть поставлен в очередь, задержан, выведен из очереди. Его маршрут может быть изменен и т. д.
АППАРАТНАЯ. К этой категории относятся три типа объектов:
1. Одноканальные приборы (в дальнейшем просто устройства).
2. Многоканальные приборы (в дальнейшем - памяти).
3. Ключи.
Устройства моделируют объекты, в которых может происходить обработка транзактов. Как правило, она связана с затратами времени. Особенность устройств состоит в том, что каждое из них может быть занято лишь одним тран зактом. Памяти же могут обслуживать несколько транзактов одновременно. Ключи могут иметь два состояния: 0 и 1. Транзакты могут устанавливать их в эти состояния или инвертировать их.
СТАТИСТИЧЕСКАЯ. К этой категории относятся следующие объекты:
1. Очереди.
2. Таблицы.
Транзакты в процессе движения могут задерживаться перед блоками, вход в которые в данных условиях невозможен. В этом случае здесь образуются очереди. Система GPSS позволяет собрать статистику о них. Для сбора данных о других отчетах модели и их представлениях в стандартной табличной форме используются таблицы. В них может быть зафиксировано изменение какого-либо СЧА объекта в процессе моделирования.
ЗАПОМИНАЮЩАЯ. Для записи в процессе моделирования текущих записей СЧА используются ячейки, которые имеют различные форматы (слово, полуслово, с плавающей точкой).
ВЫЧИСЛИТЕЛЬНАЯ. В процессе моделирования часто возникает необходимость вычисления какого-либо соотношения между различными СЧА (арифметического или логического). Для этой цели и служат объекты этой категории - переменные (арифметические, булевские). Для отображения зависимостей между двумя СЧА служат функции.
Основные этапы моделирования
1. определение и краткая характеристика;
2. символ обозначения и единица измерения;
3. диапазон изменения (для переменных);
4. место применения в модели.
Постановка задачи
На комплектовочный конвейер сборочного цеха каждые 5 ± 1 мин поступают 5 изделий первого типа и каждые 20 ± 7 мин поступают 20 изделий второго типа. Конвейер состоит из секций, вмещающих по 10 изделий каждого типа. Комплектация начинается только при наличии деталей обоих типов в требуемом количестве и длится 10 мин. При нехватке деталей секция конвейера остается пустой.
Смоделировать работу конвейера сборочного цеха в течение 8 ч. Определить вероятность пропуска секции, средние и максимальные очереди по каждому типу изделий. Определить экономическую целесообразность перехода на секции по 20 изделий с временем комплектации 20 мин.
Решение задачи
Для решения поставленной задачи были использованы следующие операторы GPSS:
· storage – накопитель;
Формат: TERMI[NATE] А
А - величина, вычитаемая из содержимого счетчика завершений(поле А карты START).
· generate – генерация транзактов;
Формат: GENE[RATE] A, B,C, D,E, F,G
А - среднее значение интервала времени;
В - разброс или модификатор среднего значения(по умолчанию ноль);
С - время появления первого транзакта;
D - общее число генерируемых транзактов;
Е - уровень приоритета каждого транзакта;(от 0 до 127,значение по умолчанию 0);
F - число параметров (по умолчанию 12);
G - тип параметра (F - полнословный, Н - полусловный - по умолчанию).
Вводит транзакты в модель, посылая их в следующий по порядку блок. Если в поле В не указана Функция, то интервал между поступлением транзактов определяется случайным числом, равномерно распределенным в диапазоне от (А - В) до (А + В). Если поле В является функцией (FN$), то этот интервал определяется произведением поля А на значение функции, заданной в поле В.
· terminate – удаление обслуженных транзактов;
Формат: TERMI[NATE] А
А - величина, вычитаемая из содержимого счетчика завершений(поле А карты START).
· enter – фиксация транзактов в накопителе;
Формат: ENTE[R] А, В
А - имя памяти символическое или числовое;
В - число занимаемых единиц памятнее умолчанию единица).
Проверяется наличие свободного объема памяти, номер которой определен в поле А. Если имеется свободная память, то транзакт входит в блок ENTER. При этом занятый объем памяти увеличивается на значение поля В. Если транзакт не может войти в блок ENTER, о задерживается в предыдущем блоке.
· split – создание копий транзакта;
Формат SPLIT A, B,C
A – число создаваемых копий;
B – номер блока-адресата;
C - номер параметра, используемого для присвоения номера и хранения значений этого номера.
· test – проверка условия;
Формат TEST<условный оператор>A, B,C
A – испытуемое значение;
B – значение ссылки;
C – номер блока адресата.
· leave – увеличение емкости накопителя;
Формат: LEAV[E] А, В
А - номер памяти;
В - число освобождаемых единиц, памяти (по умолчанию 1).
Транзакт удаляется из памяти, имя (номер) которой указано в поле А. Число освобождаемых при этом единиц памяти определяется полем В.
· advance – задержка транзактов;
Формат: ADVA[NCE] А, В
А - среднее время задержки (константа, если В не задано);
В - разброс относительно среднего значения, должен быть меньше или равен А.
· savevalue – сохраненные величины.
Формат: savevalue a, b
А - номер хранимого значения;
В –значение которое будет добавлено или вычтено.
· QUEUE – очереди
Формат: QUEU[E] А, В
А - номер очереди (числовое или символьное имя очереди);
В - число добавляемых к очереди элементов (по умолчанию 1).
· Variable – объявление вещественной переменной
Формат: <имя переменной> Variable <значение или выражение>
Увеличивает текущее содержимое очереди, указанной в поле А, на значение в поле В. Если поле В не определено, увеличивает содержимое очереди на единицу. Транзакт может находиться в двух различных очередях одновременно.
После анализа поставленной задачи, она бы промоделирована в среде GPSS:
izd1 storage 10 объявление накопителя для изделий 1
izd2 storage 10 объявление накопителя для изделий 2
pust variable 0
poln variable 0
generate 480 задание общего времени моделирования
terminate 1
generate 5,1 генерация деталей 1 первого типа
QUEUE o1
enter izd1 вход деталей в накопитель 1
terminate
generate 20,7 генерация деталей 1 первого типа
QUEUE o1
split 1 создание 1 копии выходящего в блок транзакта
enter izd2,2 вход деталей 2 в накопитель
terminate
generate 10 задание числа секций
test GE s$izd2,1,pst проверка наличия деталей в накопителе 1
test GE s$izd1,2,pst проверка наличия деталей в накопителе 2
leave izd1,2 освобождение накопителя 1
leave izd2,1 освобождение накопителя 2
advance 10 обработка
savevalue poln+,1 подсечет кол-ва полных секций
terminate
pst savevalue pust+,1 кол-во пустых секций
terminate
start 1
Результаты моделирования
GPSS World Simulation Report - 8.49.1
Saturday, January 13, 2007 12:54:12
START TIME END TIME BLOCKS FACILITIES STORAGES
0. 2
NAME VALUE
IZD1 10000.000
IZD2 10001.000
O1 10005.000
O2 10004.000
POLN 10003.000
PST 20.000
PUST 10002.000
LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY
1 GENERATE 1 0 0
2 TERMINATE 1 0 0
3 GENERATE
4 QUEUE
5 ENTER
6 TERMINATE
7 GENERATE
8 SPLIT
9 QUEUE
10 ENTER
11 TERMINATE
12 GENERATE
13 TEST
14 TEST
15 LEAVE
16 LEAVE
17 ADVANCE
18 SAVEVALUE
19 TERMINATE
PST 20 SAVEVALUE 2 0 0
21 TERMINATE 2 0 0
QUEUE MAX CONT. ENTRY ENTRY(0) AVE. CONT. AVE. TIME AVE.(-0)
RETRY
O152 236.
O233 235.
STORAGE CAP. REM. MIN. MAX. ENTRIES AVL. AVE. C. UTIL. RETRY DELAY
IZD1.
IZD28.
SAVEVALUE RETRY VALUE
PUST 0 2.000
POLN 0 45.000
CEC XN PRI M1 ASSEM CURRENT NEXT PARAMETER VALUE
8 0 12
FEC XN PRI BDT ASSEM CURRENT NEXT PARAMETER VALUE
2 0 3
0 0 7
3 0 1
В отчете отображается следующая информация :
· Время моделирования ;
· Число блоков, накопителей и каналов обслуживания в модели ;
· Число требований в блоке в конце моделирования ;
· Число требований ожидающих определенных условий ;
· Сколько раз канал обслуживания был занят или захвачен коэффициент использования канала ;
· Среднее время монопольного использования требованиями канала;
· Очереди, длину очереди(максимальную и на конец моделирования);
В случае с нашей моделью можно выявить следующие результаты:
1. В модель поступило 95 комплектов деталей первого типа (5 шт.) и 27 комплектов деталей второго типа (10 шт.);
2. пройдено 21 блоков моделирования;
3. задействовано 2 накопителя, 2 сохраненные величины и 2 очереди
4. общее время моделирования – 480 минут
5. ожидание в очереди для деталей первого типа достигло 95 и для деталей второго типа достигло 46
6. коэффициент загрузки секций для деталей первого типа 37,3% и для деталей второго типа 85,8%:
STORAGE CAP. REM. MIN. MAX. ENTRIES AVL. AVE. C. UTIL. RETRY DELAY
IZD1.
IZD28.
7. при прогоне модели было пропущено 2 секции и отправлено на компоновку 45
При моделировании работы конвейера с вместимостью секций по 20 изделий каждого типа показатели работы отличаются незначительно:
STORAGE CAP. REM. MIN. MAX. ENTRIES AVL. AVE. C. UTIL. RETRY DELAY
IZD14.
IZD216.
Коэффициент загрузки конвейера в этом случае составляет 21,3% для первого типа деталей и 80,3% для второго типа деталей. Так же пропускается 2 секции и отравляется на комплектацию 45
Выводы
В результате проделанной работы был разработан алгоритм решения экономически актуальной задачи, выполнена его программная реализация в среде имитационного моделирования GPSS World и произведен анализ полученных результатов. На все поставленные задачи и вопросы были найдены решения и ответы.
Литература:
1 , «Основы работы с универсальной средой моделирования GPSS World», Москва: Издательство Ассоциации строительных вузов, 2005.-256с.
2 Интернет: http://www. *****
3 Интернет: http://stud. math. *****/actuar/dima/*****. html#c4
4 « Имитационное моделирование экономических процессов» – Москва: Финансы и статистика, 2004
