Файл: курсовой проект Моделирование систем массового обслуживания.doc

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра Прикладная математика и фундаментальная информатика

Направление Фундаментальная информатика и информационные технологии

Профиль Информатика и компьютерные науки

КУРСОВОЙ ПРОЕКТ

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

по дисциплине: Моделирование информационных процессов

Студент _ группы _

(Ф.И.О. полностью)

Руководитель проекта

____________________________________ (Ф.И.О.)

____________________________

(Подпись, дата)

Студент

____________________________

(Подпись, дата)

Омск 2014

Реферат

Объем 15 страниц, 3 иллюстраций, 3 использованных источника.

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

Цель работы – закрепление и практическое применение знаний, полученных при изучении дисциплины «Моделирование информационных процессов».

Содержание

Введение

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

1 Теоретические сведения

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

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

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

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

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

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

5) дисциплина обслуживания, т. е. совокупность правил, в соответствии с которыми требование выбирается из очереди для обслуживания. Наиболее часто на практике используются следующие правила:

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

- заявки принимаются к обслуживанию по минимальному времени получения отказа;

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

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

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

Моделирование - это исследование какого-либо объекта или системы объектов путем построения и изучения их моделей. А также – это использование моделей для определения или уточнения характеристик и рационализации способов построения вновь конструируемых объектов.

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

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

2)Внутреннее проектирование – проектирование отдельных элементов системы.

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

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

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

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

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

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

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

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

Рисунок 1 - Структура систем массового обслуживания

Основными элементами СМО являются:

1. входной поток заявок;

2. очередь;

3. каналы обслуживания;

4. выходной поток заявок (обслуженные заявки).

Эффективность функционирования СМО определяется ее пропускной способностью — относительным числом обслуженных заявок. По числу каналов n все СМО разделяются на одноканальные (n= 1) и многоканальные (n > 1). Многоканальные СМО могут быть как однородными (по каналам), так и разнородными (по продолжительности обслуживания заявок).
По дисциплине обслуживания различаются три класса СМО.

1. СМО с отказами (нулевое ожидание или явные потери). «Отказная» заявка вновь поступает в систему, чтобы ее обслужили (например, вызов абонента через АТС).

2. СМО с ожиданием (неограниченное ожидание или очередь). При занятости всех каналов заявка поступает в очередь и в конце концов будет выполнена (торговля, сферы бытового и медицинского обслуживания).

3. СМО смешанного типа (ограниченное ожидание). Имеется ограничение на длину очереди (сервис по обслуживанию автомобилей). Другой вид ограниченного ожидания — ограничение на время пребывания заявки в СМО (ПВО, особые условия обслуживания в банке).

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

Также ,помимо одноканальных СМО существуют многоканальные, а также СМО с ожиданием и ограничением длинны очереди. Рассмотрим многоканальную СМО (n ? 1) с ожиданием, т. е. заявка, поступившая в СМО в момент времени, когда все каналы заняты, в отличие от СМО с отказами, не покидает систему необслуженной, а становится в очередь и ожидает обслуживания. Следует отметить, что большинство обслуживающих фирм и учреждений устроены как раз по такому принципу. Пусть максимальное число мест в очереди равно т ? 1, т. е. в очереди могут ожидать своего обслуживания не более т заявок. Поэтому заявка, пришедшая на вход в СМО в момент, когда в очереди уже находятся т заявок, получает отказ и покидает систему. Иными словами, «заполнение» СМО заявками из входного потока идет в два этапа: сначала происходит загрузка каналов обслуживания, затем заполняется очередь. Нумерация состояний системы в этом случае имеет следующий вид: от состояния s0 (в СМО нет заявок и все каналы свободны) до состояния sn (в СМО n заявок и все каналы заняты) очереди нет; от состояния sn+1 (в СМО n + 1 заявка, все каналы заняты и одна заявка находится в очереди) до состояния sn + m(все каналы заняты и все т мест в очереди заняты заявками) происходит заполнение очереди.
Граф состояний СМО показан на (рис. 2.) Переход системы из состояния sk в состояние sk+1 слева направо (k = 0, 1,..., n + т - 1) происходит под воздействием одного и того же входного потока заявок интенсивности , следовательно, плотности вероятности перехода из состояния в состояние слева направо одинаковы и равны .

Рисунок 2 - Граф состояний СМО

2 Постановка задачи

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

Длины временных промежутков между прибытиями посетителей в столовую распределены по равномерному закону на интервале (0 – 20) мин. Время обслуживания на одного посетителя описывается равномерно распределенной величиной на интервале (1 –2) мин.

На обед посетитель затрачивает время, которое распределено равномерно на интервале (15 – 25) мин.

В течение 4 часов оценить:

• сколько в среднем требуется посетителю времени на посещение столовой,

• среднее время, которое посетитель проводит в очереди,

• среднее число одновременно обедающих, их максимальное и минимальное число.

3 Построение модели в GPSS

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

Разработка и отладка имитационной модели СМО на языке GPSS World. Модель имеет следующий вид:

GENERATE 10,10

CMO1 QUEUE 1

SEIZE 1

DEPART 1

ADVANCE 1.5,0.5

RELEASE 1

TERMINATE 0

Блок GENERATE 10,10 создает интервалы поступления заявок в интервале от 0 до 20 минут. СМО1 описывает обработку заявок в очереди. Блок QUEUE задает номер очереди в которой находятся заявки ждущие обработки. Блок SEIZE берет одну заявку из указанной очереди и отправляет её на обработку .Блок DEPART удаляет заявку из очереди и ставит в начало очереди следующую. Блок ADVANCE обрабатывает заявки поступившие из блока SIEZE, и затрачивает время определенное равномерно распределенной величиной на отрезках (1;2) минут. После обработки заявки Блок RELEASE освобождает место для принятия и обработки следующей заявки. Блок TERMINATE удаляет обработанную заявки из очереди. Блоки СМО1 обрабатывают заявки поступающие из блока GENERATE. В данной работе имитируется работа столовой в течении 4 часов.

На рисунке 3 показаны результаты моделирования системы массового обслуживания.

Рисунок 3 – Результаты работы СМО

Как показано на рисунке, СМО приняла и обработала 23 заявки, среднее время обработки одной заявки 1,516 минуты.

Заключение

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

Список использованных источников

1. Сирота, Александр Анатольевич. Компьютерное моделирование и оценка эффективности сложных систем [Текст] : учеб. пособие для вузов по специальности "Прикладная информатика (по обл. )" и др. специальностям / А. А. Сирота, 2006. - 279 с.

2. Рыжиков, Юрий Иванович. Имитационное моделирование: теория и технологии [Текст] / Ю. И. Рыжиков. - СПб. : КОРОНА принт ; М. : Альтекс-А, 2004. - 380 с.

3. Задорожный, Владимир Николаевич. Имитационное и статистическое моделирование [Текст] / В. Н. Задорожный; ОмГТУ. - Омск: Изд-во ОмГТУ, 2007. - 131 с.