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

Содержание

Введение

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

.1 Система M | M | 1 | ∞

.2 Система M | M | 1 | 0

.3 Система M | M | n | N

.4 Моделирование в среде Maple

. Исследование стационарного функционирования однолинейной СМО с ограниченным числом мест для ожидания. Характеристики стационарного функционирования

.1 Аналитическое исследование M | M | 1 | 0. Характеристики стационарного функционирования

.2 Аналитическое исследование M | M | 1 | 3. Характеристики стационарного функционирования

. Моделирование работы однолинейной СМО с ограниченным числом мест для ожидания в среде Maple

.1 Моделирование работы M | M | 1 | 0 в среде Maple

.2 Моделирование работы M | M | 1 | 3 в среде Maple

Заключение

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

Введение

В настоящем курсовом проекте рассматриваются одноканальные марковские СМО (системы массового обслуживания) с ожиданием и с отказами. Аналитическое исследование СМО позволит определить основные характеристики и определить эффективность модели при заданных параметрах. Также рассматривается моделирование работы однолинейной СМО с ограниченным числом мест для ожидания в среде Maple и вычисление характеристик стационарного функционирования систем М|M|1|0 и М|M|1|3.

1. Классификация систем массового обслуживания. Марковские системы массового обслуживания

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

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

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

)число обслуживающих приборов (каналов, линий);

)дисциплина обслуживания, организация очереди и процесса обслуживания.

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

FCFS (first come - first servered) или FIFO (first in - first out) - заявки обслуживаются в порядке поступления;

LCFS (last come - first servered) или LIFO (last in - first out) - инверсионный порядок обслуживания, при котором в первую очередь обслуживается заявка, поступившая последней;

PS (processor sharing) - разделения процессора, которая характеризуется тем, что если в очереди системы находится M заявок, то каждая из них обслуживается за одну секунду в течении времени 1/M секунд (имеются разновидности этой дисциплины, которые неравномерно распределяют время обслуживания между заявками);

SIRO (service in random order) - очередная заявка выбирается из очереди “наудачу”.

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

A | B | n | N.

Здесь первая позиция A характеризует входящий в систему поток заявок:

A = G(general) или A = GI(general independent) - рекуррентный поток; = M(Markov) - пуассоновский (простейший) поток;

A = (Erlang) - поток Эрланга k-го порядка;

A = D - детерминированный или регулярный поток (с постоянными неслучайными интервалами между моментами поступления заявок).

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

B = G или B = GI - рекуррентное обслуживание с одной и той же функцией распределения B(t) длительностей обслуживания заявок на разных приборах;

B = M - экспоненциальное обслуживание с одинаковой интенсивностью обслуживания µ для разных приборов;

B =  - эрланговское обслуживание k-го порядка на всех приборах с одинаковым параметром µ для разных приборов;

B = D - детерминированное или регулярное обслуживание, идентичное для разных приборов (т.е. с одним и тем же неслучайным временем обслуживания заявки b).

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

Третья позиция n - количество обслуживающих приборов.

Четвертая позиция N - число мест для ожидания заявок в очереди.

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

К марковским системам относятся такие системы, поведение которых в момент времени t может быть описано марковским процессом ξ(t) с непрерывным временем и не более чем счетным пространством состояний. В частности, сюда относятся все системы вида M | M | n | N , где , .

1.1 Система M | M | 1 | ∞

Согласно общему описанию система M | M | 1 | ∞ - система, состоящая из единственного экспоненциального прибора (с интенсивностью обслуживания µ), в которую поступает простейший поток заявок (с параметром λ).Число мест для ожидания заявок бесконечно, т.е. система с ожиданием.

Для системы M | M | 1 | ∞ величина  называется коэффициентом загрузки.

Cстационарные вероятности:

Где к изменяется от 0 до бесконечности.

1.2 Система M | M | 1 | 0

Согласно общему описанию система M | M | 1 | 0 - система, состоящая из единственного экспоненциального прибора (с интенсивностью обслуживания µ), в которую поступает простейший поток заявок (с параметром λ).Число мест для ожидания заявок в очереди отсутствует, т.е. система с отказами.

Для системы M | M | 1 | 0 величина  называется коэффициентом загрузки.

Условие эргодичности для этой системы, т. е. необходимое и достаточное условие существования стационарного распределения, является:

Cстационарные вероятности:

Вероятность отказа заявки: р_отк = р₁

Относительная пропускная способность системы: Q = 1 - p₁

Абсолютная пропускная способность системы: А=л·Q

1.3 Система M | M | n | N

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

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

 при ;

 при .

Стационарное распределение имеет вид:

.

1.4 Моделирование в среде Maple

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

Maple - типичная интегрированная система. Она объединяет в себе:

o     мощный язык программирования (он же язык для интерактивного общения с системой);

o     редактор для подготовки и редактирования документов и программ;

o     современный многооконный пользовательский интерфейс с возможностью работы в диалоговом режиме;

o     мощную справочную систему со многими тысячами примеров;

o     численный и символьный процессоры;

o     систему диагностики;

o     библиотеки встроенных и дополнительных функций;

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

Ко всем этим средствам имеется полный доступ прямо из программы. Maple - одна из самых мощных и «разумных» интегрированных систем символьной математики, созданная фирмой Waterloo Maple, Inc. (Канада).

массовый maple ожидание однолинейный

2. Исследование стационарного функционирования однолинейной СМО с ограниченным числом мест для ожидания. Характеристики стационарного функционирования

.1 Аналитическое исследование M | M | 1 | 0. Характеристики стационарного функционирования

Имеется СМО вида M | M | 1 | 0 с интенсивностью обслуживания µ = 0,015, в которую поступает простейший поток заявок с параметром λ = 0,014.

Пусть ξ(t) - число заявок в системе в момент времени t, X = {1, 0} - пространство состояний марковского процесса ξ(t), P_n(t) = P{ξ(t) = n}.

Коэффициент загрузки равен:

Стационарные вероятности:

Вероятность отказа заявки: р_отк = р₁=0,48276

2.2 Аналитическое исследование M | M | 1 | 3. Характеристики стационарного функционирования

Имеется СМО вида M | M | 1 | 3 с интенсивностью обслуживания µ = 0,015, в которую поступает простейший поток заявок с параметром λ = 0,014.

Пусть ξ(t) - число заявок в системе в момент времени t, X = {1, 0} - пространство состояний марковского процесса ξ(t), P_n(t) = P{ξ(t) = n}.

Коэффициент загрузки равен:

Стационарные вероятности:

Где к изменяется от 0 до 4.

p₀=0,395

p₁=0,368

p₂=0,171

p₃=0,033

p₄=0,012

Вероятность отказа заявки: р_отк = р₁=0,012

3. Моделирование работы однолинейной СМО с ограниченным числом мест для ожидания в среде Maple

3.1 Моделирование работы M | M | 1 | 0 в среде Maple

Моделирование работы СМО вида M | M | 1 | 0 проводилось по алгоритму представленному в блок-схеме изображенной на рисунке 3.1.

Рисунок 3.1 - Блок-схема программы для моделирования M | M | 1 | 0.

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

Решение задачи в среде Maple для системы  имеет вид:

> p:=proc(k)smtobs,post,otk,obsl,Otk1,Obsl1:t1,tokon,t,rnpost,och::=0:otk:=0:obsl:=0:smtobs:=0:tokon:=0:och:=0:rnpost:=rand(0..1200):t from 1 by 1 to k do :=rnpost():tokon>0 then tokon:=tokon-1 fi:t1<=17 and tokon<=0 and och=0 then tokon:=stats[random,exponential[1/65,0]](): smtobs:=smtobs+tokon: obsl:=obsl+1: post:=post+1: och:=och+1 fi:t1<=17 and tokon>0 and och=1 then post:=post+1: otk:=otk+1 fi:t1>17 and tokon<=0 and och=1 then tokon:=stats[random,exponential[1/65,0]](): smtobs:=smtobs+tokon: obsl:=obsl+1: post:=post+1: och:=och-1 fi:t1>17 and tokon<=0 and och=0 then tokon:=0 fi od end:

Принятые обозначения:

smtobs - затрачено всего минут на обслуживание;

post - прибыло машин на обслуживание;

otk - количество отказов в обслуживании;

obsl - обслужено машин;

tokon - время, затраченное на обслуживание одной машины;

Результат выполнения программы:

Обслужено (среднее): 51,4

Отказано в обслуживании (среднее): 48,4

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

3.2 Моделирование работы M | M | 1 | 3 в среде Maple

Моделирование работы СМО вида M | M | 1 | 0 проводилось по алгоритму представленному в блок-схеме изображенной на рисунке 3.2.

Рисунок 3.2 - Блок-схема программы для M | M | 1 | 3.

Процедура реализованная по данной блок-схеме была запущена в цикле 10 раз при времени исполнения к=5000 и посчитано средне арифметическое выводимых параметров для получения более точных данных. В результате выполнения программы выводится среднее время пребывания 1-ой заявки, 2-ух заявок и 3-ех заявок ожидающих обслуживания.

Решение задачи в среде Maple для системы  имеет вид:

> p:=proc(k) toch1,toch2,toch3,toch1o,toch2o,toch3o,smtobs,post,otk,obsl:t1,tokon,t,rnpost,och::=0:toch2:=0:toch3:=0:post:=0:otk:=0:obsl:=0:smtobs:=0:tokon:=0:och:=0:rnpost:=rand(0..1200):t from 1 by 1 to k do :=rnpost():och=1 then toch1:=toch1+1 fi:och=2 then toch2:=toch2+1 fi:och=3 then toch3:=toch3+1 fi:tokon>0 then tokon:=tokon-1 fi:t1<=17 and tokon<=0 then tokon:=stats[random,exponential[1/65,0]](): smtobs:=smtobs+tokon: obsl:=obsl+1: post:=post+1 fi:t1<=17 and tokon>0 and och<3 then post:=post+1: och:=och+1 fi:t1<=17 and tokon>0 and och=3 then post:=post+1: otk:=otk+1 fi:t1>17 and tokon<=0 and och>0 then tokon:=stats[random,exponential[1/65,0]](): smtobs:=smtobs+tokon: obsl:=obsl+1: och:=och-1 fi:t1>17 and tokon<=0 and och=0 then tokon:=0 fi od end:

Принятые обозначения:

toch1- количество минут, когда в очереди одна машина;

toch2- количество минут, когда в очереди две машины;

toch3- количество минут, когда в очереди три машины;

smtobs - затрачено всего минут на обслуживание;

post - прибыло машин на обслуживание;

otk - количество отказов в обслуживании;

obsl - обслужено машин;

och - очередь;

tokon - время, затраченное на обслуживание одной машины;

Результат выполнения программы:

,3 минут 1 заявка в очереди

,9 минут 2 заявки в очереди

,2 минут 3 заявки в очереди

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

Заключение

В данном курсовом проекте мы изучили марковские системы массового обслуживания, исследовали характеристики стационарного функционирования. Так же была изучена среда Maple, ее основные функции и язык программирования, на котором мы реализовали программы для исследования работы одноканальных СМО М|M|1|0 и М|M|1|3. Полученные результаты математического исследования и компьютерного моделирования схожи друг с другом с небольшой погрешностью. Проведено математическое и компьютерное моделирование в среде Maple.

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

1.   Буриков А.Д. Теория массового обслуживания: Учебное пособие по спецкурсу/ А.Д. Буриков, Ю.В. Малинковский, М.А. Маталыцкий - Гродно.: ГрГУ, 1984.- 108 с.

3.   Jackson J.R. Networks of waiting lines // Oper. Res./ J.R. Jackson. - 1957. - V.5, №4. - P. 518-521.

4.      Gelenbe E. Product form networks with negative and positive customers. //J. Appl. Prob./ E. Gelenbe - 1991 - V.28. - P.656-663.

5.      Дудин А.Н. Практикум на ЭВМ по теории массового обслуживания/ А.Н. Дудин, Г.А. Медведев, Ю.В. Меленец - Мн.: Электронная книга БГУ, 2003 - 109 с.