Теория массового обслуживания

массового обслуживания считается датский ученый Агнер Краруп Эрланг.

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

выдающийся советский математик Александр Яковлевич Хинчин (1984 – 1959).

Он предложил сам термин теория массового обслуживания и систематизировал основные положения теории системы массового обслуживания в монографии «Работы по математической теории массового обслуживания»

установлении зависимостей эффективности функционирования СМО от ее организации (параметров):

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

используют понятия теории случайных величин, а также теории случайных процессов.

Случайным процессом, или случайной функцией S(t), называется функция, которая каждому моменту времени t; из некоторого временного промежутка ставит в соответствие единственную случайную величину S(t).

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

По множеству состояний системы S протекающий в ней случайный процесс может быть дискретным или непрерывным.

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

в случайные моменты времени.

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

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

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

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

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

Простейшим (пуассоновским) называется поток событий, который обладает свойствами стационарности, отсутствия последействия и ординарности.

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

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

Эта теорема является основополагающей для теории систем массового обслуживания.
Формула (8.1) отражает все свойства простейшего потока.

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

λ =1,2 вызовов в минуту.
Найти вероятность того, что за две минуты:
а) не придет ни одного вызова;
б) придет ровно один вызов;
в) придет хотя бы один вызов.

Решение.
а) Случайная величина X – число вызовов за две минуты – распределена
по закону Пуассона с параметром λτ =1,2 ∙ 2 = 2,4 . Вероятность того, что вызовов не будет (m = 0 ), по формуле (8.1):
.
б) Вероятность одного вызова (m = 1) по формуле (8.1):
в) Вероятность хотя бы одного вызова:

.

.

.

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

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

Схема СМО изображена на рисунке.

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

показателей:

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

из

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

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

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

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

на пребывание заявки в очереди накладываются некоторые ограничения.

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

эту CMO при следующих предположениях:
1. Входной поток является пуассоновским с параметром l.
2. Время обслуживания подчиняется экспоненциальному закону с параметром m:
3. Время обслуживания требования не зависит от количества требований, поступивших в систему.

времени t может находиться в одном из двух состояний: – в системе 0 требований (система свободна) или – в системе 1 требование (система занята).

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

задачи: нахождению вероятностей и пребывания системы в каждом из возможных состояний.

поступлениями требований, так и длительностей обслуживания. При этом плотность распределения длительностей интервалов между поступлениями требований имеет вид

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

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

λ и μ, т.е.
Вычислим вероятности нахождения п заявок в системе:
P1=ρ∙P0=0,893∙0,248=0,221;
P2=ρ 2∙P0=0,8932∙0,248=0,198;
P3=ρ 3∙P0=0,8933∙0,248=0,177;
P4=ρ 4∙P0=0,8934∙0,248=0,158.
Вероятность отказа в обслуживании автомобиля:
Pотк=Р4= ρ 4∙P0≈0,158.
Относительная пропускная способность окна оформления:
q=1–Pотк=1-0,158=0,842.
Абсолютная пропускная способность окна оформления
А=λ∙q=0,85∙0,842=0,716 (автомобиля в час).

В зону таможенного контроля в пункте пропуска автомобили въезжают по системе электронной очереди. Каждое окно оформления прибытия/убытия представляет собой одноканальную СМО. Число стоянок для автомобилей, ожидающих оформления , ограниченно и равно 3, то есть (N-1)=3. Если все стоянки заняты, т. е. в очереди уже находится три автомобиля, то очередной автомобиль в зону таможенного контроля не пропускается, т.е. в очередь на обслуживание не становится. Поток автомобилей, прибывающих на оформление имеет интенсивность λ=0,85 (автомобиля в час). Время оформления автомобиля распределено по показательному закону и в среднем равно =1,05 час. Требуется определить вероятностные характеристики окна оформления прибытия/убытия пункта пропуска, работающего в стационарном режиме.

Решение

системе массового обслуживания):
Среднее время пребывания автомобиля в системе:
часа.
Средняя продолжительность пребывания заявки в очереди на обслуживание:
Wq=Ws-1/μ=2,473-1/0,952=1,423 часа.
Среднее число заявок в очереди (длина очереди):
Lq=λ∙(1-PN)∙Wq=0,85∙(1-0,158)∙1,423=1,02.

Работу рассмотренного окна оформления можно считать удовлетворительной, так как не обслуживается в среднем 15,8% случаев (Ротк=0,158).

СМО с ожиданием без ограничения на вместимость блока ожидания (т.е. Ν → ∞). Остальные условия функционирования СМО остаются без изменений.
Устойчивое решение в такой системе существует только тогда, когда λ<μ, то есть заявки должны обслуживаться с большей скоростью, чем поступают, в противном случае очередь может разрастись до бесконечности.
Вероятность того, что в системе находится п заявок, вычисляется по формуле

,n=0,1,2,…,

число находящихся в системе клиентов (заявок) на обслуживание:

средняя продолжительность пребывания клиента в системе:

среднее число клиентов в очереди на обслуживание:

средняя продолжительность пребывания клиента в очереди:

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

примере: μ=0,952; ρ=0,893.
Вычислим предельные вероятности системы по формулам
P0=1- ρ =1-0,893=0,107;
P1=(1- ρ)· ρ =(1-0,893)·0,893=0,096;
P2=(1- ρ)· ρ 2=(1-0,893)·0,8932=0,085;
P3=(1- ρ)· ρ 3=(1-0,893)·0,8933=0,076;
P4=(1- ρ)· ρ 4=(1-0,893)·0,8934=0,068;
P5=(1- ρ)· ρ 5=(1-0,893)·0,8935=0,061 и т.д.
Следует отметить, что Р0 определяет долю времени, в течение которого окно оформления вынужденно бездействует (простаивает). В нашем примере она составляет 10, 7%, так как Р0=0,107. Среднее число автомобилей, находящихся в системе (на обслуживании и в очереди):

ед.

рано или поздно будут обслужены: q=1.

Абсолютная пропускная способность:

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

Допустим, в первоначальном варианте количество мест для стоянки прибывших автомобилей как в предыдущем примере было равно трем.

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

оформления в среднем за смену (день) будет терять 12∙0,134=1,6 автомобиля.

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

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

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

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

Эрланга.

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

вероятность отказа:

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

характеризует степень загрузки СМО.

(n=3) взаимозаменяемыми ПЭВМ для решения поступающих задач. Поток задач, поступающих на ВЦ, имеет интенсивность λ=1 задача в час. Средняя продолжительность обслуживания tоб=1,8 час.
Требуется вычислить значения:
- вероятности числа занятых каналов ВЦ;
- вероятности отказа в обслуживании заявки;
- относительной пропускной способности ВЦ;
- абсолютной пропускной способности ВЦ;
- среднего числа занятых ПЭВМ на ВЦ.
Определите, сколько дополнительно надо приобрести ПЭВМ, чтобы увеличить пропускную способность ВЦ в 2 раза.
Решение.
Определим параметр μ потока обслуживаний:

Приведенная интенсивность потока заявок

пропускная способность ВЦ

Абсолютная пропускная способность ВЦ:

Среднее число занятых каналов – ПЭВМ

1,5 компьютера из трех – остальные полтора будут простаивать. Работу рассмотренного ВЦ вряд ли можно считать удовлетворительной, так как центр не обслуживает заявки в среднем в 18% случаев (Р3= 0,180). Очевидно, что пропускную способность ВЦ при данных λ и μ можно увеличить только за счет увеличения числа ПЭВМ.
Определим, сколько нужно использовать ПЭВМ, чтобы сократить число не обслуженных заявок, поступающих на ВЦ, в 10 раз, т.е. чтобы вероятность отказа в решении задач не превосходила 0,0180. Для этого используем формулу вероятности отказа:

Составим следующую таблицу:

Анализируя данные таблицы, следует отметить, что расширение числа каналов ВЦ при данных значениях λ и μ до 6 единиц ПЭВМ позволит обеспечить удовлетворение заявок на решение задач на 99,22%, так как при n = 6 вероятность отказа в обслуживании (Ротк) составляет 0,0078.

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

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

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

где

Решение будет действительным, если выполняется следующее условие: 

и неограниченной очередью определяется по следующим формулам:

среднее число клиентов в очереди на обслуживание

среднее число находящихся в системе клиентов (заявок на обслуживание и в очереди)

LS=Lq+ρ;

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

средняя продолжительность пребывания клиента в системе

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

Пример 9.5. Таможня с тремя таможенными постами (каналами) выполняет пропуск товаров. Поток неправильно заполненных деклараций, для товаров прибывающих на таможню,  - пуассоновский и имеет интенсивность λ=2,5 у.е. в сутки, среднее время оформления одной заявки распределено по показательному закону и равно tоб=0,5 часа. Предположим, что другой таможни в округе нет, и, значит, очередь деклараций может расти практически неограниченно.

заявок в очереди на обслуживание;

среднее число находящихся в системе заявок;

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

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

Решение.

Определим параметр потока обслуживаний

Приведенная интенсивность потока заявок

ρ=λ/μ=2,5/2,0=1,25,

при этом λ/μ ∙с=2,5/2∙3=0,41<1.

Поскольку λ/μ∙с<1, то очередь не растет безгранично и в системе наступает предельный стационарный режим работы.
Вычислим вероятности состояний системы: