Материал: Создание и исследование имитационной модели системы массового обслуживания

Создание и исследование имитационной модели системы массового обслуживания

Курсовая работа

Создание и исследование имитационной модели системы массового обслуживания

Задание

На станцию технического обслуживания согласно закону Эрланга второго порядка со средним временем прибытия 14 мин прибывают автомобили для технического обслуживания (36% автомобилей) и ремонта (64% автомобилей). На станции есть два бокса для технического обслуживания и три бокса для ремонта. Выполнение простого, средней сложности и сложного ремонтов - равновероятно. Время и стоимость выполнения работ по техническому обслуживанию и ремонту зависит от категории выполняемых работ. После технического обслуживания 12% автомобилей поступают для выполнения ремонта средней сложности.

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

Введение

Система GPSS World - мощная универсальная среда моделирования как дискретных, так и непрерывных процессов, предназначенная для профессионального моделирования самых разнообразных процессов и систем. Эта система явилась следующим шагом развития системы GPSS/PC, ориентированной на DOS.

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

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

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

1. Имитационное моделирование

1.1    Функциональная структура GPSS

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

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

верхний уровень, определяемый комбинацией функциональных основных объектов: устройств, памятей, ключей, очередей;

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

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

Транзакты. Функционирование объекта отображается в модели в виде перемещения транзактов от блока GENERATE в блок TERMINATE через промежуточные блоки. Транзакты, или сообщения являются абстрактными подвижными элементами, которые могут моделировать различные объекты реального мира: сообщения, программы, транспортные средства, людей и т.п. Перемещаясь между блоками модели, транзакты вызывают (и испытывают) различные действия. Возможны их задержки в некоторых точках модели, изменения маршрутов и направлений движения, расщепление транзактов на несколько копий и т.п. С каждым транзактом связан упорядоченный набор данных. Он включает номер транзакта; номер блока, в котором в данный момент находится транзакт; номер следующего блока; время перехода в следующий блок; приоритет, характеризующий очередность обработки транзактов в определенных случаях; а также набор параметров, с помощью которых каждому транзакту можно присвоить числовые значения, выражающие желаемые свойства или характеристики моделируемых объектов: вес, скорость, объем, цвет, время обработки и т.п.

Блоки, влияющие на атрибуты транзактов и на их движение в модели. В GPSS/PC существует ряд блоков, с помощью которых можно изменить значение параметров транзактов. Блок ASSIGN модифицирует значение параметра транзакта, входящего в этот блок. Блок INDEX изменяет значение параметра номер 1. Блок INCREMENT увеличивает значение параметра, блок DECREMENT уменьшает величину параметра.

Блок MARK записывает в указанный им параметр текущее значение таймера абсолютного времени или, если параметр не указан, заменяет значение отметки времени на текущее значение таймера.

С помощью блока USING осуществляется доступ текущего транзакта к параметрам другого транзакта модели. Блок LOCATE определяет и записывает в параметр текущего транзакта номер блока, в который должен войти определенный транзакт. Пересылка транзакта в требуемую точку модели осуществляется блоком TRANSFER. Блок ТЕSТ проверяя выполнение определенного условия, может также направлять транзакты в заданную точку модели, если условие не выполняется. В этом его действия аналогичны блоку GATE. Для организации в модели циклов используют блок LOOP, с помощью которого можно предусмотреть многократное прохождение транзактом заданной цепочки блоков. Изменение приоритета транзакта осуществляет блок PRIORITY. Блок BUFFER возобновляет просмотр списка текущих событий и используется, как правило, в качестве режима блока PRIORITY. С помощью блоков TRACE и UNTRACE осуществляют трассировку движения транзактов в модели.

Памяти. Памяти служат для моделирования объектов, обладающих определенной емкостью. Памяти моделируются блоками ENTER и LEAVE. Входящий в блок ENTER транзакт занимает определенную часть памяти. При входе транзакта в блок LEAVE память освобождается. Емкость памяти задают с помощью оператора STORAGE, который не является блоком GPSS и относится к числу служебных карт.

Очереди. Транзакты в процессе движения могут задерживаться перед блоками, вход в которые в данных условиях невозможен. При поступлении транзактов на вход задерживающих блоков образуются очереди. Для сбора статистики об очередях в местах задержки ставят блоки QUEUE. Эти блоки сами по себе не создают очередь, а лишь являются средством ее регистрации. При входе транзакта в блок QUEUE текущая длина очереди получает приращение. Уход из очереди отображается блоком DEPART.

Таблицы. Для сбора статистических данных о различных отчетах модели и их представления в стандартной табличной форме используют таблицы. Занесение информации в таблицу осуществляется блоком TABULATE в момент входа очередного транзакта в этот блок. описание структуры таблицы и типа заносимых данных (СЧА) осуществляется картой TABLE.

Ячейки. Для записи в процессе моделирования текущих значений СЧА используют ячейки. Занесение информации в ячейку осуществляет блок SAVEVALUE. При входе транзакта в этот блок требуемое значение СЧА фиксируется в ячейке, номер которой определяется операндом блока SAVEVALUE. Ячейки имеют различные форматы (слово, полуслово, с плавающей точкой). Изменение содержимого ячеек может осуществляться блоками SDECREMENT и SINCREMENT. Блок SDECREMENT вычитает заданное значение из величины, содержащейся в ячейке. Блок SINCREMENT добавляет требуемое приращение к содержимому ячейки.

Функции и переменные. Функции служат для отображения зависимостей между двумя СЧА. В GPSS/PC имеется два типа функций: непрерывные (С) и дискретные (D). Функцию задают набором пар точек - координат. Непрерывная функция воспроизводится в виде ломаной кривой, отрезки которой соединяют соседние точечные значения. Дискретная функция имеет вид ступенчатой кривой.

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

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

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

Захват и освобождение устройства моделируются соответственно блоками SEIZE и RELEASE. Для проверки состояния устройств используют GATE. Прерывание моделирует блок PREEMPT, снятие прерывания - блок RETURN.

1.2    Системы массового обслуживания

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

Рис. 1.1. Структура системы массового обслуживания

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

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

Поток заявок рассматривается как случайный процесс, характеризующийся функцией распределения периода поступления заявок (например, простейший поток, поток Эрланга).

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

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

Существуют алгоритмы, по которым заявки принимаются к обслуживанию, например:

-       в порядке очереди (FIFO, очереди с приоритетами и др.),

-       в случайном порядке в соответствии с заданными распределениями, по минимальному времени получения отказа и др.

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

Рис. 1.2. Стохастическая сеть

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

Различают следующие типы систем массового обслуживания:

-       одноканальные и многоканальные (по количеству каналов);

-       с ожиданием и без ожидания (с отказами);

-       с ограничением на длину очереди (или с ограниченным ожиданием) и без ограничения;

-       с упорядоченной очередью и с неупорядоченной очередью;

-       с приоритетами и без приоритетов и др.

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

-       общее количество обслуженных заявок, за какой-либо промежуток времени;

-       пропускная способность - среднее число заявок, обслуженных в единицу времени;

-       доля обслуженных заявок;

-       доля заявок, получивших отказ;

-       время пребывания заявки в системе (от момента поступления заявки в систему до момента завершения ее обслуживания);

-       среднее время обслуживания (функция распределения времени обслуживания);

-       средняя длина очереди;

-       среднее время ожидания;

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

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

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