Главная Валютные операции Система массового обслуживания пример. Модели массового обслуживания

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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Введение

1. Понятие систем массового обслуживания. Сущность смешанных СМО

1.1 Понятие систем массового обслуживания

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

2. Функционирование и критерии эффективности смешанных систем массового обслуживания

2.1 Функционирование смешанных систем массового обслуживания

2.2 Критерии эффективности смешанных систем массового обслуживания и их сравнение с другими СМО

3. Пример практического решения задачи с участием смешанных СМО

Заключение

Список литературы

Введение

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

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

Целью работы является изучение смешанной системы массового обслуживания.

Для достижения поставленной цели необходимо решить ряд задач:

1. Определить понятие систем массового обслуживания и сущность смешанных СМО.

2. Рассмотреть основы функционирования и критерии эффективности смешанных систем массового обслуживания.

3. С помощью примера описать функционирование смешанной СМО.

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

1 . Понятие систем массового обслуживания. Сущность смешанных СМО

1.1 Понятие систем массового обслуживания

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

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

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

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

Системы массового обслуживания или теория массового обслуживания - предмет, берущий начало в теории вероятностей. Но изучение таких систем в приложении к реальному миру (а их множество: магазин или вокзал с кассами, склад с операторами, парикмахерские и больницы, вычислительные сети, станки и наладчики, системы АТС и т.п.), обычно проходит в рамках предметов «Исследование операций» и «Математические методы в экономике» .

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

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

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

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

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

2 - очередь;

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

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

По числу каналов n все СМО разделяются на одноканальные (n= 1) и многоканальные (n > 1).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В смешанных системах массового обслуживания требование, поступившее в систему на обслуживание и заставшее все приборы занятыми, может покинуть систему и не обслуженным.

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

Эти ограничения могут накладываться на длину очереди, т.е. максимально возможное число заявок, которые одновременно могут находиться в очереди.

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

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

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

По итогам первой главы работы можно сделать следующие выводы:

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

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

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

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

2 . Функционирование и критерии эффективности смешанных систем массового обслуживания

2.1 Функционирование смешанных систем массового обслуживания

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

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

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

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

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

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

2.2 Критерии эффективности смешанных систем массового обслуживания и их сравнение с другими СМО

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

Критерии эффективности систем обслуживания с потерями :

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

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

4. Может быть полезен такой критерий, как среднее количество потерянных требований за определенный промежуток времени.

Критерии эффективности систем обслуживания без потерь :

1. Длина очереди является случайной величиной. В качестве характеристики длины очереди можно использовать ее математическое ожидание. Перечень критериев:

2. Математическое ожидание длины очереди.

3. Время ожидания начала обслуживания.

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

5. Средняя длина очереди, полная характеристика которой может быть задана законом распределения длины очереди.

6. Среднее число занятых обслуживающих аппаратов (это число - величина случайная).

7. Вероятность иметь более m единиц в очереди в момент при заданном начальном состоянии системы.

Критерии эффективности системы обслуживания смешанного типа.

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

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

2. Суммарное время, затраченное всеми аппаратами системы.

Частные критерии в зависимости от специфики изучаемых конкретных процессов могут быть получены из этих основных с учетом особенностей каждого процесса.

По итогам второй главы работы можно сделать следующие выводы:

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

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

...

Подобные документы

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

курсовая работа , добавлен 17.11.2009

Элементы теории массового обслуживания. Математическое моделирование систем массового обслуживания, их классификация. Имитационное моделирование систем массового обслуживания. Практическое применение теории, решение задачи математическими методами.

курсовая работа , добавлен 04.05.2011

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

курсовая работа , добавлен 25.09.2014

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

контрольная работа , добавлен 15.03.2016

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

лабораторная работа , добавлен 11.03.2011

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

лабораторная работа , добавлен 20.05.2013

Решение системы дифференциальных уравнений методом Рунге-Кутта. Исследованы возможности применения имитационного моделирования для исследования систем массового обслуживания. Результаты моделирования базового варианта системы массового обслуживания.

лабораторная работа , добавлен 21.07.2012

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

лабораторная работа , добавлен 19.05.2013

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

дипломная работа , добавлен 25.08.2009

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

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

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

Задача анализа СМО заключается в определении ряда показателей ее эффективности, которые можно разделить на следующие группы:

показатели, характеризующие систему в целом: число n занятых каналов обслуживания, число обслуженных (λ b ), ожидающих обслуживание или получивших отказ заявок (λ c ) в единицу времени и т.д.;
вероятностные характеристики : вероятность того, что заявка будет обслужена (P обс) или получит отказ в обслуживании (P отк), что все приборы свободны (p 0) или определенное число их занято (p k ), вероятность наличия очереди и т.д.;
экономические показатели : стоимость потерь, связанных с уходом не обслуженной по тем или иным причинам заявки из системы, экономический эффект, полученный в результате обслуживания заявки, и т.д.

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

Многоканальная система с отказами

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

Смешанные системы

Система с ограничением на длину очереди .
Состоит из накопителя (очереди) и узла обслуживания. Заявка покидает очередь и уходит из системы, если в накопителе к моменту ее появления уже находятся m заявок (m – максимально возможноечисло мест в очереди). Если заявка поступила в систему и застала, хотя бы один канал свободным, она мгновенно начинает обслуживаться. Если в момент поступления заявки в систему все каналы заняты, то заявка не покидает систему, а занимает место в очереди. Заявка покидает систему не обслуженной, если к моменту её поступления в систему заняты все каналы обслуживания и все места в очереди.
Для каждой системы определяется дисциплина очереди. Это система правил, определяющих порядок поступления заявок из очереди в узел обслуживания. Если все заявки и каналы обслуживания равнозначны, то чаще всего действует правило «кто раньше пришел, тот раньше обслуживается».
Система с ограничением на длительность пребывания заявки в очереди .
Состоит из накопителя (очереди) и узла обслуживания. От предыдущей системы она отличается тем, что заявка, поступившая в накопитель (очередь), может ожидать начала обслуживания лишь ограниченное время Т ож (чаще всего это случайная величина). Если её время Т ож истекло, то заявка покидает очередь и уходит из системы не обслуженной.

Математическое описание СМО

СМО рассматриваются как некоторые физические системы с дискретными состояниями х 0 , х 1 , …, х n , функционирующие при непрерывном времени t . Число состояний n может быть конечным или счетным (n → ∞). Система может переходить из одного состояния х i (i= 1, 2, … , n) в другое х j (j= 0, 1, … ,n) в произвольный момент времени t . Чтобы показать правила таких переходов, используют схему, называемую графом состояний . Для типов перечисленных выше систем графы состояний образуют цепь, в которой каждое состояние (кроме крайних) связано прямой и обратной связью с двумя соседними состояниями. Это схема гибели и размножения.
Переходы из состояния в состояние происходят в случайные моменты времени. Удобно считать, что эти переходы происходят в результате действия каких-то потоков (потоков входных заявок, отказов в обслуживании заявок, потока восстановления приборов и т.д.). Если все потоки простейшие, то протекающий в системе случайный процесс с дискретным состоянием и непрерывным временем будет марковским.
Поток событий - это последовательность однотипных событий, протекающих в случайные моменты времени. Его можно рассматривать как последовательность случайных моментов времени t 1 , t 2 , … появления событий.
Простейшим называют поток, обладающий следующими свойствами:

Ординарность . События следуют по одиночке (противоположность потоку, где события следуют группами).
Стационарность . Вероятность попадания заданного числа событий на интервал времени Т зависит только от длины интервала и не зависит от того, где на оси времени находиться этот интервал.
Отсутствие последействия . Для двух непересекающихся интервалов времени τ 1 и τ 2 число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой интервал.

В простейшем потоке интервалы времени Т 1 , Т 2 ,… между моментами t 1 , t 2 , … появления событий случайны, независимы между собой и имеют показательное распределение вероятностей f(t)=λe -λt , t≥0, λ=const, где λ - параметр показательного распределения, являющийся одновременно интенсивностью потока и представляющий собой среднее число событий, происходящих в единицу времени. Таким образом, t =M[T]=1/λ.
Марковские случайные события описываются обыкновенными дифференциальными уравнениями . Переменными в них служат вероятности состояний р 0 (t), p 1 (t),…,p n (t) .
Для очень больших моментов времени функционирования систем (теоретически при t → ∞) в простейших системах (системы, все потоки в которых – простейшие, а граф – схема гибели и размножения) наблюдается установившийся, или стационарный режим работы. В этом режиме система будет изменять свое состояние, но вероятности этих состояний (финальные вероятности ) р к , к= 1, 2 ,…, n, не зависят от времени и могут рассматриваться как среднее относительное время пребывания системы в соответствующем состоянии.

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

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

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

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

	Узлы	Требования

Больница	Санитары	Пациенты
Производство
Аэропорт	Выходы на взлетно-посадочные полосы Пункты регистрации	Пассажиры

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

Рис. 1

Генератор заявок – объект, порождающий заявки: улица, цех с установленными агрегатами. На вход поступает поток заявок (поток покупателей в магазин, поток сломавшихся агрегатов (машин, станков) на ремонт, поток посетителей в гардероб, поток машин на АЗС и т. д.).
Диспетчер – человек или устройство, которое знает, что делать с заявкой. Узел, регулирующий и направляющий заявки к каналам обслуживания. Диспетчер:

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

Очередь – накопитель заявок. Очередь может отсутствовать.
Узел обслуживания состоит из конечного числа каналов обслуживания. Каждый канал имеет 3 состояния: свободен, занят, не работает. Если все каналы заняты, то можно придумать стратегию, кому передавать заявку.
Отказ от обслуживания наступает, если все каналы заняты (некоторые в том числе могут не работать).

Кроме этих основных элементов в СМО в некоторых источниках выделяются также следующие составляющие:

терминатор – уничтожитель трансактов;

склад – накопитель ресурсов и готовой продукции;

счет бухгалтерского учета – для выполнения операций типа «проводка»;

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

Классификация СМО

Первое деление (по наличию очередей):

СМО с отказами;
СМО с очередью.

В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не обслуживается.

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

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

Итак, например, рассматриваются следующие СМО:

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

Типы ограничения очереди могут быть комбинированными.

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

Естественно, поток заявок, порожденный самой системой, будет зависеть от системы и ее состояния.

Кроме этого СМО делятся на открытые СМО и замкнутые СМО.

В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов занято). В замкнутой СМО – зависят. Например, если один рабочий обслуживает группу станков, время от времени требующих наладки, то интенсивность потока «требований» со стороны станков зависит от того, сколько их уже исправно и ждет наладки.

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

По количеству каналов СМО делятся на:

одноканальные;
многоканальные.

Характеристики системы массового обслуживания

Основными характеристиками системы массового обслуживания любого вида являются:

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

Входной поток требований

Для описания входного потока требуется задать вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание, и указать количество таких требований в каждом очередном поступлении. При этом, как правило, оперируют понятием «вероятностное распределение моментов поступления требований». Здесь могут поступать как единичные, так и групповые требования (количество таких требований в каждом очередном поступлении ). В последнем случае обычно речь идет о системе обслуживания с параллельно-групповым обслуживанием.

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

E(A) – среднее (МО) время поступления;

λ=1/E(A) – интенсивность поступления требований;

Характеристики входного потока:

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

Дисциплина очереди

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

Очередь имеет имя.

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

первым пришел – первый обслуживаешься;

first in first out (FIFO)

самый распространенный тип очереди.

Какая структура данных подойдет для описания такой очереди? Массив плох (ограничен). Можно использовать структуру типа СПИСОК.

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

Вы как программисты должны уметь делать списки двусторонние, односторонние.

Действия со списком:

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

Структура, известная как СТЕК. Может быть описан структурой массив или список;

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

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

Характеристики очереди

ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»);
длина очереди.

Механизм обслуживания

Механизм обслуживания определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся:

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

Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований».

S i – время обслуживания i -го требования;

E(S) – среднее время обслуживания;

μ=1/E(S) – скорость обслуживания требований.

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

Коэффициент использования СМО

N ·μ – скорость обслуживания в системе, когда заняты все устройства обслуживания.

ρ=λ/(N μ) – называется коэффициентом использования СМО , показывает, насколько задействованы ресурсы системы.

Структура обслуживающей системы

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

Пример. Кассы в магазине.

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

Пример. Медицинская комиссия.

Комбинированное обслуживание – обслуживание вкладов в сберкассе: сначала контролер, потом кассир. Как правило, 2 контролера на одного кассира.

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

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

Основные критерии эффективности функционирования СМО

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

вероятность немедленного обслуживания поступившей заявки (Р обсл =К обс /К пост);
вероятность отказа в обслуживании поступившей заявки (P отк =К отк /К пост);

Очевидно, что Р обсл + P отк =1.

Потоки, задержки, обслуживание. Формула Поллачека–Хинчина

Задержка – один из критериев обслуживания СМО, время проведенное заявкой в ожидании обслуживания.

D i – задержка в очереди требования i ;

W i =D i +S i – время нахождения в системе требования i .

(с вероятностью 1) – установившаяся средняя задержка требования в очереди;

(с вероятностью 1) – установившееся среднее время нахождения требования в СМО (waiting).

Q(t) – число требований в очереди в момент времени t;

L(t) – число требований в системе в момент времени t (Q(t) плюс число требований, которые находятся на обслуживании в момент времени t.

Тогда показатели (если существуют)

(с вероятностью 1) – установившееся среднее по времени число требований в очереди;

(с вероятностью 1) – установившееся среднее по времени число требований в системе.

Заметим, что ρ<1 – обязательное условие существования d, w, Q и L в системе массового обслуживания.

Если вспомнить, что ρ= λ/(N μ), то видно, что если интенсивность поступления заявок больше, чем N μ, то ρ>1 и естественно, что система не сможет справиться с таким потоком заявок, а следовательно, нельзя говорить о величинах d, w, Q и L.

К наиболее общим и нужным результатам для систем массового обслуживания относятся уравнения сохранения

Следует обратить внимание, что упомянутые выше критерии оценки работы системы могут быть аналитически вычислены для систем массового обслуживания M/M/N (N >1), т. е. систем с Марковскими потоками заявок и обслуживания. Для М/G/ l при любом распределении G и для некоторых других систем. Вообще распределение времени между поступлениями, распределение времени обслуживания или обеих этих величин должно быть экспоненциальным (или разновидностью экспоненциального распределения Эрланга k-го порядка), чтобы аналитическое решение стало возможным.

Кроме этого можно также говорить о таких характеристиках, как:

абсолютная пропускная способность системы – А=Р обсл *λ;
относительная пропускная способность системы –

Еще один интересный (и наглядный) пример аналитического решения – вычисление установившейся средней задержки в очереди для системы массового обслуживания M/G/ 1 по формуле:

В России эта формула известна как формула Поллачека– Хинчина, за рубежом эта формула связывается с именем Росса (Ross).

Таким образом, если E(S) имеет большее значение, тогда перегрузка (в данном случае измеряемая как d ) будет большей; чего и следовало ожидать. По формуле можно обнаружить и менее очевидный факт: перегрузка также увеличивается, когда изменчивость распределения времени обслуживания возрастает, даже если среднее время обслуживания остается прежним. Интуитивно это можно объяснить так: дисперсия случайной величины времени обслуживания может принять большое значение (поскольку она должна быть положительной), т. е. единственное устройство обслуживания будет занято длительное время, что приведет к увеличению очереди.

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

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

Расчет показателей эффективности открытой одноканальной СМО с отказами. Расчет показателей эффективности открытой многоканальной СМО с отказами. Расчет показателей эффективности многоканальной СМО с ограничением на длину очереди. Расчет показателей эффективности многоканальной СМО ожиданием.

1. Потоки заявок в СМО

2. Законы обслуживания

3. Критерии качества работы СМО

5. Параметры моделей очередей. При анализе систем массового

6. I. Модель А – модель одноканальной системы массового обслуживания с Пуассоновским входным потоком заявок и Экспоненциальным временем обслуживания.

7. II. Модель В – многоканальная система обслуживания.

8. III. Модель С – модель с постоянным временем обслуживания.

9. IV. Модель D – модель с ограниченной популяцией.

Потоки заявок в СМО

Потоки заявок бывают входные и выходные.
Входной поток заявок – это временная последовательность событий на входе СМО, для которой появление события (заявки) подчиняется вероятностным (или детерминированным) законам. Если требования на обслуживание приходят в соответствие, с каким – либо графиком (например, автомобили приезжают на АЗС каждые 3 минуты) то такой поток подчиняется детерминированным (определенным) законам. Но, как правило, поступление заявок подчиняется случайным законам.
Для описания случайных законов в теории массового обслуживания вводится в рассмотрение модель потоков событий. Потоком событий называется последовательность событий, следующих одно за другим в случайные моменты времени .
В качестве событий могут фигурировать поступление заявок на вход СМО (на вход блока очереди), появление заявок на входе прибора обслуживания (на выходе блока очереди) и появление обслуженных заявок на выходе СМО.

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

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

Рекуррентный поток соответственно определяется как поток, для которого все функции распределения интервалов между заявками

совпадают, то есть

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

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

Отсутствие последействия означает отсутствие вероятностной зависимости последующего течения процесса от предыдущего. Если имеется одноканальная СМО с временем обслуживания , то при потоке заявок без последействия на входе системы выходной поток будет с последействием, так как заявки на выходе СМО не появляются чаще чем интервал . В регулярном потоке, в котором события следуют друг за другом через определенные промежутки времени, имеется самое жесткое последействие.
Потоком с ограниченным последействием называется такой поток, для которого интервалы между событиями независимы.
Поток называется стационарным, если вероятность появления какого-то числа событий на интервале времени зависит только от длины этого интервала и не зависит от его расположения на оси времени. Для стационарного потока событий среднее число событий в единицу времени постоянно.
Ординарным потоком называется такой поток, для которого вероятность попадания на данный малый отрезок времени dt двух и более требований пренебрежительно мала по сравнению с вероятностью попадания одного требования.
Поток, который обладает свойствами стационарности, отсутствия последействия и ординарности называют пуассоновским (простейшим). Этот поток занимает центральное место среди всего многообразия потоков, так же как случайные величины или процессы с нормальным законом распределения в прикладной теории вероятности.
Пуассоновский поток описывается следующей формулой:
,
где – вероятность появления событий за время , – интенсивность потока.
Интенсивностью потока называют среднее число событий, которые появляются за единицу времени.
Для пуассоновского потока интервалы времени между заявками распределены по экспоненциальному закону

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

Законы обслуживания

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

где – плотность потока заявок
Откуда плотность распределения времени обслуживания

Дальнейшим обобщением экспоненциального закона обслуживания может служить закон распределения Эрланга, когда каждый интервал обслуживания подчиняется закону:

где – интенсивность исходного пуассоновского потока, k – порядок потока Эрланга.

Критерии качества работы СМО

Эффективность работы СМО оценивается различными показателями в зависимости от цепи и типа СМО. Наибольшее распространение получили следующие:

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

Относительная пропускная способность СМО – отношение среднего числа требований, обработанных системой, к среднему числу требований, поступивших на вход СМО.

Средняя длительность простоя системы.

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

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

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

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

Наиболее часто используются следующие Технические характеристики:

1) среднее время, которое клиент проводит в очереди;

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

3) среднее время, которое клиент проводит в системе обслуживания (время ожидания плюс время обслуживания);

4) среднее число клиентов в системе обслуживания;

5) вероятность того, что система обслуживания окажется незанятой;

6) вероятность определенного числа клиентов в системе.

Среди Экономических характеристик наибольший интерес представляют следующие:

1) издержки ожидания в очереди;

2) издержки ожидания в системе;

3) издержки обслуживания.

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

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

А) пуассоновское распределение вероятностей поступления заявок;

Б) стандартное поведение клиентов;

В) правило обслуживания FIFO (первым пришел - первым обслужен);

Г) единственная фаза обслуживания.

I. Модель А - модель одноканальной системы массового обслуживания М/М/1 с Пуассоновским входным потоком заявок и Экспоненциальным временем обслуживания.

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

1. Заявки обслуживаются по принципу «первым пришел - первым обслужен» (FIFO), причем каждый клиент ожидает своей очереди до конца независимо от длины очереди.

2. Появления заявок являются независимыми событиями, однако среднее число заявок, поступающих в единицу времени, неизменно.

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

4. Время обслуживания описывается экспоненциальным распределением вероятностей.

5. Темп обслуживания выше темпа поступления заявок.

Пусть λ – число заявок в единицу времени;

μ – число клиентов, обслуживаемых в единицу времени;

n – число заявок в системе.

Тогда система массового обслуживания описывается уравнениями, приведенными ниже.

Формулы для описания системы М/М/1:

Среднее время обслуживания одного клиента в системе (время ожидания плюс время обслуживания);

Среднее число клиентов в очереди;

Среднее время ожидания клиента в очереди;

Характеристика загруженности системы (доля времени, в течение которого система занята обслуживанием);

Вероятность отсутствия заявок в системе;

Вероятность того, что в системе находится более чем K заявок.

II. Модель В - многоканальная система обслуживания M/M/S. В многоканальной системе для обслуживания открыты два канала или более. Предполагается, что клиенты ожидают в общей очереди и обращаются в первый освободившийся канал обслуживания.

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

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

Время нахождения заявки в очереди;

Время нахождения заявки в системе.

III. Модель С - модель с постоянным временем обслуживания M/D/1.

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

Формулы, описывающие модель С:

Средняя длина очереди;

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

Среднее число клиентов в системе;

Среднее время ожидания в системе.

IV. Модель D - модель с ограниченной популяцией.

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

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

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

Как частный случай модели с ограниченной очередью можно рассматривать Модель с отказами, если количество мест в очереди сократить до нуля.

Введение

Математическое описание метода

1 Общие сведения о системах массового обслуживания

2 Многоканальные СМО с отказами

Обоснование и выбор инструментальной среды для проведения расчетов

Алгоритмическое обеспечение

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

2 Математическая модель

3 Построение моделей СМО с отказами в Simulink

3.1 Для 3-х канальной СМО

3.2 Для 5-канальной СМО

4 Расчет показателей эффективности

4.1 для 3-х канальной СМО

4.2 Для 5-канальной СМО

5 Анализ результатов моделирования

Заключение

Список использованной литературы

ВВЕДЕНИЕ

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

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

Для достижения поставленной цели выделим основные задачи:

-подробное описание многоканальной СМО с отказами;

выбор контрольного примера и постановка задачи;

определение алгоритма решения;

создание имитационной модели в среде MATLAB (Simulink);

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

1. МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ МЕТОДА

.1 Общие сведения о системах массового обслуживания

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

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

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

В простейшем пуассоновском потоке событий случайная величина распределена по показательному закону:

,(1.1)

где λ - интенсивность потока.

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

Основой СМО является определенное число обслуживающих устройств - каналов обслуживания.

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

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

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

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

2.очередь;

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

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

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

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

По дисциплине обслуживания различаются три класса СМО:

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

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

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

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

Эффективность работы систем массового обслуживания характеризуют показатели, которые можно разбить на три групп:

1.Группа показателей эффективности использования СМО:

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

относительная пропускная способность (Q ) - отношение абсолютной пропускной способности к среднему числу заявок, поступивших в систему за единицу времени;

средняя продолжительность периода занятости СМО ();

интенсивность нагрузки (ρ) показывает степень согласованности входного и выходного потоков заявок канала обслуживания и определяет устойчивость СМО;

коэффициент использования СМО - средняя доля времени, в течение которого система занята обслуживанием заявок.

2.Показатели качества обслуживания заявок:

среднее время ожидания заявки в очереди ();

среднее время пребывания (обслуживания) заявки в СМО ();

вероятность отказа заявки в обслуживании без ожидания ();

вероятность немедленного приема заявки ();

закон распределения времени ожидания заявки в очереди в СМО;

среднее число заявок в очереди ();

среднее число заявок, находящихся в СМО ().

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

1.2 Многоканальные СМО с отказами

Система M/M/n/0 представляет собой n- линейную СМО с r местами ожидания (r=0), в которую поступает пуассоновский поток интенсивности , а времена обслуживания заявок независимы и при этом время обслуживания каждой заявки на любом приборе распределено по экспоненциальному закону с параметром . В случае, когда , заявка, поступившая в переполненную систему (т.е. когда заняты все приборы и все места ожидания), теряется и вновь в нее не возвращаются. Система M/M/n/r также относится к экспоненциальным СМО.

Уравнения, описывающие распределение заявок в системе

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

А. iпроцесс не выйдет из состояния i равна произведению вероятности не поступления заявки за время на вероятность того, что за это время не обслужится ни одна из i заявок, т.е. равна . Вероятность перехода за время в состояние i+1 равна - вероятности поступления заявки в систему. Наконец поскольку каждый прибор закончит за время обслуживание находящейся в нем заявки с вероятностью , а таких приборов i, то вероятность перехода в состояние i-1 равна . Остальные переходы имеют вероятность .

Б. n≤i остаться в состоянии i равна , перейти в состояние i-1 за это же время

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

Если же , то, что очевидно последнего выражения не будет, а в предпоследнем индекс i может принимать значения i=n,n+1,… .

Вычитая теперь из обеих частей равенства, деля на и переходя к пределу

при , получаем систему дифференциальных уравнений:

, (1.2)

Стационарное распределение очереди

В случае конечного r, например r=0, процесс является эргодическим. Также он будет эргодическим в случае при выполнении условия, о котором будет сказано ниже. Тогда из (1) при получаем, что стационарные вероятности состояний pi удовлетворяют систему уравнений:

,(1.3)

Поясним теперь вывод системы уравнений (1.3), исходя из принципа глобального баланса. Так, например, согласно диаграмме переходов для фиксированного состояния i, , имеем, что суммарные потоки вероятностей входящий в состояние i и выходящий из него равны, соответственно, и .

Рисунок 1 Диаграмма переходов

Исходя теперь из принципа локального баланса, что баланс потоков вероятностей между состояниями i и i+1 отражается равенствами:

,(1.4)

являющимися уравнениями локального баланса для данной СМО. Проверка справедливости равенств (1.4) производится непосредственным суммированием системы уравнений (1.3) по i при i=0,1,…,n+r-1.

Из соотношения (1.4), выражая рекуррентно вероятности через ,

где , а определяется из условия нормировки , т.е.

.(1.6)

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

Если , то стационарный режим существует при любом .

Выпишем теперь выражения для некоторых характеристик очереди.

Стационарная вероятность немедленного обслуживания заявки (обслуживания без ожидания) совпадает со стационарной вероятностью того, что в системе находится 0,1,…,n-1 заявок, т.е.

Рассмотрим интересующий нас частный случай, когда r=0. тогда в системе отсутствуют места для ожидания (система с потерями M/M/n/0) и такая система носит название системы Эрланга . Система Эрланга описывает процессы, происходящие в простейших телефонных сетях, и названа так в честь А. К. Эрланга, впервые её исследовавшего. Для системы M/M/n/0 стационарные вероятности определяются формулой Эрланга

Следовательно, стационарная вероятность потери заявки определяется формулой:

которую также называют формулой Эрланга.

Наконец, когда , то мы имеем систему , для которой при любом стационарные вероятности существуют и, как следует из формул Эрланга при , имеют вид

Вернемся теперь к соотношениям (1.4). Суммируя эти равенства по i=0,1,…,n+r-1 , получаем

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

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

Стационарное распределение времени пребывания заявки в системе

Стационарное распределение W(x) времени ожидания начала обслуживания принятой в систему M/M/n/r заявки вычисляется практически так же, как и для системы . Заметим, что заявка, заставшая при поступлении i других заявок в системе, немедленно начинает обслуживаться, если i времена.

Путем несложных преобразований находим, учитывая независимость времени обслуживания от времени ожидания начала обслуживания, находим, что стационарное распределение V(x) времени пребывания в системе принятой к обслуживанию заявки имеет ПЛС

Стационарные средние времена ожидания начала обслуживания и пребывания заявки в системе задаются формулами:

Последнее выражение можно также получить из формул Литтла.

Нестационарные характеристики

Нестационарное распределение числа заявок в системе получается интегрированием системы (1) с учетом начального распределения .

Если , то система (1) представляет собой линейную однородную систему обыкновенных дифференциальных уравнений первого порядка с постоянными коэффициентами.

Выходящий поток

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

2. Обоснование и выбор инструментальной среды для проведения расчетов

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

Результаты поведения модели менеджер использует для реального объекта, то есть принимает плановое или прогнозируемое решение, полученное с помощью исследования модели.- это компьютерная программная система для моделирования систем управления. Simulink является составным элементом Matlab и использует для моделирования все возможности. С помощью Matlab Simulink моделируются линейные, нелинейные, дискретные, стохастические и гибридные системы.

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

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

Преимущество Simulink заключается в том, что он позволяет пополнять библиотеки блоков с помощью программ, написанных как на языке Matlab, так и на языках С++, Fortran и Ada.

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

Итак, Matlab Simulink - это система имитационного моделирования, которая позволяет удобно и легко строить и исследовать модели экономических процессов.

3. Алгоритмическое обеспечение

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

В качестве многоканальной СМО с отказами рассмотрим работу вычислительного центра.

В вычислительный центр коллективного пользования с тремя ЭВМ поступают заказы от предприятий на вычислительные работы. Если работают все три ЭВМ, то вновь поступающий заказ не принимается, и предприятие вынуждено обратиться в другой вычислительный центр. Среднее время работы с одним заказом составляет 3 ч. Интенсивность потока заявок 0,25 (1/ч).

Требуется определить основные характеристики эффективности данной СМО, если интенсивность, с которой каждая ЭВМ обслуживает заказ, равна 1/3 заявки в час, а интенсивность, с которой заявки поступают в вычислительный центр, равна 0,25 единиц в час. Рассмотреть случай увеличения количества ЭВМ на 2 единицы в центре и проследить, как изменятся основные характеристики этой системы. По результатам анализа полученных результатов, дать рекомендации относительно оптимального числа каналов обслуживания.

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

Рисунок 2 - График состояний многоканальной СМО с отказами

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

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

(3.1)

При этом для нахождения финальных вероятностей можно воспользоваться формулами (4) и (5). С учётом (16) получим из них:

(3.2)

(3.3)

Формулы (3.2) и (3.3) называются формулами Эрланга - основателя теории массового обслуживания.

Вероятность отказа в обслуживании заявки р_отк равна вероятности того, что все каналы заняты, т.е. система находится в состоянии Sn. Таким образом,

(3.4)

Относительную пропускную способность СМО найдём из (3.4):

(3.5)

Абсолютную пропускную способность найдём из (3,5):

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

3.3 Построение моделей СМО с отказами в Simulink

.3.1 для 3-х канальной СМО

Рисунок 3 Модель СМО с 3-мя каналами обслуживания

Рисунок 3 (продолжение) Модель СМО с 3-мя каналами обслуживания

В моделях, реализованных в Simulink, есть возможность вывести значения показателей эффективности СМО. При изменении входных параметров, значения будут пересчитываться автоматически.

Система массового обслуживания с тремя каналами может находиться в четырех состояних: S0 - все каналы свободны, S1 - 1 канал занят, S2 - 2 канала занято, S3 - все 3 канала заняты. Вероятности этих состояний представлены на рисунке 4.

Рисунок 4 Вероятности состояний для СМО с 3-мя каналами

3.3.2 Для 5-канальной СМО

Рисунок 5 Модель СМО с 5-ю каналами

Рисунок 5 (продолжение) Модель СМО с 5-ю каналами

Как и в случае n=3 для СМО с n=5 реализован вывод значений показателей эффективности в самой модели.

Система массового обслуживания с пятью каналами может находиться в шести состояних: S0 - все каналы свободны, S1 - 1 канал занят, S2 - 2 канала занято, S3 -3 канала заняты, S4 -4 канала заняты, S5 -все 5 каналов заняты. Вероятности этих состояний представлены на рисунке 7

Рисунок 6 Вероятности состояний для СМО с 5-ю каналами

3.4 Расчет показателей эффективности

Расчет показателей эффективности систем массового обслуживания с тремя и пятью каналами был произведен с помощью пакета MS Excel по формулам, описанным в параграфе 3.2

.4.1 для 3-х канальной СМО

Таблица 1 Расчет показателей эффективности трехканальной СМО

n (число каналов обслуживания)3ʎ (интенсивность входящего потока заявок)0,25µ (интенсивность потока обслуженных заявок, выходящих из одного канала)0,33333ρ (приведенная интенсивность потока заявок)0,75вероятности состояний P_00,47584P_10,35688P_20,13383P_30,03346сумма вероятностей1Q (относительная пропускная способность СМО)0,96654A (абсолютная пропускная способность СМО)0,24164P_serv (вероятность того, что заявка будет обслужена)0,96654P_otk (вероятность того, что заявка получит отказ)0,03346n" (среднее число занятых каналов)0,72491

3.4.2 Для 5-канальной СМО

Таблица 2 Расчет показателей эффективности пятиканальной СМО

n (число каналов обслуживания)5ʎ (интенсивность входящего потока заявок)0,25µ (интенсивность потока обслуженных заявок, выходящих из одного канала)0,33333ρ (приведенная интенсивность потока заявок)0,75вероятности состояний P_00,47243P_10,35432P_20,13287P_30,03322P_40,00623P_50,00093сумма вероятностей1Q (относительная пропускная способность СМО)0,99907A (абсолютная пропускная способность СМО)0,24977P_serv (вероятность того, что заявка будет обслужена)0,99907P_otk (вероятность того, что заявка получит отказ)0,00093n" (среднее число занятых каналов)0,7493

3.5 Анализ результатов моделирования

Таблица 3 Сравнение результатов моделирования с теоретическими расчетами для трехканальной СМО

ПараметрТеоретическое значениеЭмпирическое значениеОтклонение (в долях)P_00,475840,4870,023P_otk0,033460,031360,07Q0,966540,96860,002A0,241640,24220,002n"0,724910,72650,002

Таблица 4 Сравнение результатов моделирования с теоретическими расчетами для пятиканальной СМО

ПараметрТеоретическое значениеЭмпирическое значениеОтклонение (в долях)P_00,472428230,48520,026P_otk0,0009342450,00099520,061Q0,966782390,9990,032A0,2416955980,24980,032n"0,7250867930,74930,032

Из таблиц видно, что отклонения эмпирических значений от теоретических не превышает ε=7%. Это означает, что построенные нами модели адекватно описывают поведение системы и они применимы для поиска оптимальных соотношений количества каналов обслуживания.

Таблица 5 Сравнение эмпирических показателей СМО где n=3 и СМО где n=5

ПараметрПоказатели СМО где n=3Показатели СМО где n=5P_00,4870,4852P_otk0,031360,0009952Q0,96860,999A0,24220,2498n"0,72650,7493

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

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

ЗАКЛЮЧЕНИЕ

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

Моделирование было выполнено в системе Matlab Simulink в виде блок-схем, которые в простой и удобной форме показывают сущности экономических процессов. Так же была произведена проверка адекватности построенных моделей путем расчета теоретических показателей эффективности выбранных типов СМО, по результатам которой модели были признаны с большой вероятностью приближенными к реальности. Из этого следует, что при рассмотрении аналогичных процессов и для экономии времени, мы можем воспользоваться моделями, разработанными в ходе этой работы.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

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

2.Варфоломеев В.И. Алгоритмическое моделирование элементов экономических систем: Практикум. Учеб. пособие. - М.: Финансы и статистика, 2000.

.Гмурман В.Е. Теория вероятностей и математическая статистика. Учеб. пособие для вузов. - М.: Высшая школа, 1998

Бухгалтеру о налогах и кадрах. Налоги, бухгалтерия, отчетность, ККМ