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

24.09.2019

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

В соответствии с тем, имеется ли возможность ожидания обслуживания или нет, различают системы:

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

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

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

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

FCFS/FIFO - система, в которой первое в очереди требование удовлетворяется первым;

LCFS/LIFO - СМО, где первым обслуживается последнее в очереди требование;

Модель random - система удовлетворения требований на основе случайного выбора.

Как правило, такая система имеет очень сложное строение.

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

Требование — формирование и предъявление запроса на обслуживание;

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

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

Математическая модель — выраженная в математической форме и с помощью математического аппарата модель данной СМО.

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

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

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

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

Показатели эффективности СМО

абсолютная и относительная пропускная способность системы;
коэффициенты загрузки и простоя;
среднее время полной загрузки системы;
среднее время пребывания заявки в системе.

Показатели, характеризующие систему с точки зрения потребителей :

P обс – вероятность обслуживания заявки,
t сист – время пребывания заявки в системе.

Показатели, характеризующие систему с точки зрения её эксплуатационных свойств :

λ b – абсолютная пропускная способность системы (среднее число обслуженных заявок в единицу времени),
P обс – относительная пропускная способность системы,
k з – коэффициент загрузки системы.

см. также Параметры экономической эффективности СМО

Задача . В вычислительный центр коллективного пользования с тремя ЭВМ поступают заказы от предприятий на вычислительные работы. Если работают все три ЭВМ, то вновь поступающий заказ не принимается, и предприятие вынуждено обратиться в другой вычислительный центр. Среднее время работы с одним заказом составляет 3 ч. Интенсивность потока заявок 0,25 (1/ч). Найти предельные вероятности состояний и показатели эффективности работы вычислительного центра.
Решение. По условию n=3, λ=0,25(1/ч), t об. =3 (ч). Интенсивность потока обслуживаний μ=1/t об. =1/3=0,33. Интенсивность нагрузки ЭВМ по формуле (24) ρ=0,25/0,33=0,75. Найдем предельные вероятности состояний:
по формуле (25) p 0 =(1+0,75+0,75 2 /2!+0,75 3 /3!) -1 =0,476;
по формуле (26) p 1 =0,75∙0,476=0,357; p 2 =(0,75 2 /2!)∙0,476=0,134; p 3 =(0,75 3 /3!)∙0,476=0,033 т.е. в стационарном режиме работы вычислительного центра в среднем 47,6% времени нет ни одной заявки, 35,7% - имеется одна заявка (занята одна ЭВМ), 13,4% - две заявки (две ЭВМ), 3,3% времени - три заявки (заняты три ЭВМ).
Вероятность отказа (когда заняты все три ЭВМ), таким образом, P отк. =p 3 =0,033.
По формуле (28) относительная пропускная способность центра Q = 1-0,033 = 0,967, т.е. в среднем из каждых 100 заявок вычислительный центр обслуживает 96,7 заявок.
По формуле (29) абсолютная пропускная способность центра A= 0,25∙0,967 = 0,242, т.е. в один час в среднем обслуживается 0,242 заявки.
По формуле (30) среднее число занятых ЭВМ k =0,242/0,33 = 0,725, т.е. каждая из трех ЭВМ будет занята обслуживанием заявок в среднем лишь на 72,5/3 =24,2%.
При оценке эффективности работы вычислительного центра необходимо сопоставить доходы от выполнения заявок с потерями от простоя дорогостоящих ЭВМ (с одной стороны, у нас высокая пропускная способность СМО, а с другой стороны - значительный простой каналов обслуживания) и выбрать компромиссное решение.

Задача . В порту имеется один причал для разгрузки судов. Интенсивность потока судов равна 0,4 (судов в сутки). Среднее время разгрузки одного судна составляет 2 суток. Предполагается, что очередь может быть неограниченной длины. Найти показатели эффективности работы причала, а также вероятность того, что ожидают разгрузки не более чем 2 судна.
Решение. Имеем ρ = λ/μ = μt об. =0,4∙2=0,8. Так как ρ = 0,8 < 1, то очередь на разгрузку не может бесконечно возрастать и предельные вероятности существуют. Найдем их.
Вероятность того, что причал свободен, по (33) p 0 = 1 - 0,8 = 0,2, а вероятность того, что он занят, P зан. = 1-0,2 = 0,8. По формуле (34) вероятности того, что у причала находятся 1, 2, 3 судна (т.е. ожидают разгрузки 0, 1, 2 судна), равны p 1 = 0,8(1-0,8) = 0,16; p 2 = 0,8 2 ∙(1-0,8) = 0,128; p 3 = 0,8 3 ∙(1-0,8) = 0,1024.
Вероятность того, что ожидают разгрузку не более чем 2 судна, равна

По формуле (40) среднее число судов, ожидающих разгрузки

а среднее время ожидания разгрузки по формуле (15.42)
(сутки).
По формуле (36) среднее число судов, находящихся у причала, L сист. = 0,8/(1-0,8) = 4 (сутки) (или проще по (37) L сист. = 3,2+0,8 = 4 (сутки), а среднее время пребывания судна у причала по формуле (41) T сист = 4/0,8 = 5 (сутки).
Очевидно, что эффективность разгрузки судов невысокая. Для ее повышения необходимо уменьшение среднего времени разгрузки судна t об либо увеличение числа причалов n .

Задача . В универсаме к узлу расчета поступает поток покупателей с интенсивностью λ = 81 чел. в час. Средняя продолжительность обслуживания контролером-кассиром одного покупателя t об = 2 мин. Определить:
а. Минимальное количество контролеров-кассиров п min , при котором очередь не будет расти до бесконечности, и соответствующие характеристики обслуживания при n=n min .
б. Оптимальное количество n опт. контролеров-кассиров, при котором относительная величина затрат С отн., связанная с издержками на содержание каналов обслуживания и с пребыванием в очереди покупателей, задаваемая, например, как , будет минимальна, и сравнить характеристики обслуживания при n=n min и n=n опт.
в. Вероятность того, что в очереди будет не более трех покупателей.
Решение.
а. По условию l = 81(1/ч) = 81/60 = 1,35 (1/мин.). По формуле (24) r = l/ m = lt об = 1,35×2 = 2,7. Очередь не будет возрастать до бесконечности при условии r/n < 1, т.е. при n > r = 2,7. Таким образом, минимальное количество контролеров-кассиров n min = 3.
Найдем характеристики обслуживания СМО при п = 3.
Вероятность того, что в узле расчета отсутствуют покупатели, по формуле (45) p 0 = (1+2,7+2,7 2 /2!+2,7 3 /3!+2,7 4 /3!(3-2,7)) -1 = 0,025, т.е. в среднем 2,5% времени контролеры-кассиры будут простаивать.
Вероятность того, что в узле расчета будет очередь, по (48) P оч. = (2,7 4 /3!(3-2,7))0,025 = 0,735
Среднее число покупателей, находящихся в очереди, по (50) L оч. = (2,7 4 /3∙3!(1-2,7/3) 2)0,025 = 7,35.
Среднее время ожидания в очереди по (42) T оч. = 7,35/1,35 = 5,44 (мин).
Среднее число покупателей в узле расчета по (51) L сист. = 7,35+2,7 = 10,05.
Среднее время нахождения покупателей в узле расчета по (41) T сист. = 10,05/1,35 = 7,44 (мин).
Таблица 1

Характеристика обслуживания	Число контролеров-кассиров
Характеристика обслуживания	3	4	5	6	7
Вероятность простоя контролеров-кассиров p 0	0,025	0,057	0,065	0,067	0,067
Среднее число покупателей в очереди T оч.	5,44	0,60	0,15	0,03	0,01
Относительная величина затрат С отн.	18,54	4,77	4,14	4,53	5,22

Среднее число контролеров-кассиров, занятых обслуживанием покупателей, по (49) k = 2,7.
Коэффициент (доля) занятых обслуживанием контролеров-кассиров
= ρ/n = 2,7/3 = 0,9.
Абсолютная пропускная способность узла расчета А = 1,35 (1/мин), или 81 (1/ч), т.е. 81 покупатель в час.
Анализ характеристик обслуживания свидетельствует о значительной перегрузке узла расчета при наличии трех контролеров-кассиров.
б. Относительная величина затрат при n = 3
C отн. = = 3/1,35+3∙5,44 = 18,54.
Рассчитаем относительную величину затрат при других значениях п (табл. 1).
Как видно из табл. 2, минимальные затраты получены при n = n опт. = 5 контролерах-кассирах.
Определим характеристики обслуживания узла расчета при n = n опт. =5. Получим P оч. = 0,091; L оч. = 0,198; Т оч. = 0,146 (мин); L сист. = 2,90; T снст. = 2,15 (мин); k = 2,7; k 3 = 0,54.
Как видим, при n = 5 по сравнению с n = 3 существенно уменьшились вероятность возникновения очереди P оч. , длина очереди L оч. и среднее время пребывания в очереди T оч. и соответственно среднее число покупателей L сист. и среднее время нахождения в узле расчета T сист., а также доля занятых обслуживанием контролеров k 3. Но среднее число занятых обслуживанием контролеров-кассиров k и абсолютная пропускная способность узла расчета А естественно не изменились.
в. Вероятность того, что в очереди будет не более 3 покупателей, определится как
= 1- P оч. + p 5+1 + p 5+2 + p 5+3 , где каждое слагаемое найдем по формулам (45) – (48). Получим при n=5:

(Заметим, что в случае n=3 контролеров-кассиров та же вероятность существенно меньше: P(r ≤ 3) =0,464).

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

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

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

показатели, характеризующие систему в целом: число 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. Потоки заявок в СМО

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

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

Основные показатели эффективности работы СМО - понятие и виды. Классификация и особенности категории "Основные показатели эффективности работы СМО" 2017, 2018.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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