Система массового обслуживания с отказами

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

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

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

Простейшая задача. Пусть СМО состоит только из одного канала (n=1) и на нее поступает пуассоновский поток заявок с интенсивностью l, зависящей в общем случае от времени l=l(t) (5.1). Заявка, заставшая канал занятым, получает отказ и покидает систему. Обслуживание заявки продолжается в течение случайного времени Тоб, распределенного по показательному закону с параметром  m    f(t)= me-mt (t>0) (5.2).

Из этого следует, что «поток обслуживаний» - простейший, с интенсивностью m. Требуется найти: абсолютную (А) и относительную (q) пропускные способности.

Рассмотрим единственный канал обслуживания как физическую систему S, которая может находиться в одном из двух состояний: S0 – свободен, S1 – занят. Обозначим вероятности состояний p0(t) и p1(t). Очевидно:

"t p0(t)+p1(t)=1   (5.3).

Граф состояний системы

По графу состояний системы составим дифференциальные уравнения Колмогорова:

  (5.4)

В соответствии с (5.3) одно уравнение в (5.4) лишнее. Отбросим второе уравнение, а первое перепишем с учетом (5.3):

  или     (5.5).

Это уравнение  естественно решать при начальных условиях p0(0)=1; p1(0)=0. Уравнение (5.5) легко может быть решено не только для простейшего потока заявок (l=const), но и для случая l=l(t). Приведем решение (5.5)  только для случая l=const:   .

Для нашего случая вероятность p0 есть не что  иное, как q.

Действительно, p0 есть вероятность того, что в момент t канал свободен, иначе вероятность того, что заявка, пришедшая в момент t, будет обслужена. А значит, для данного момента времени t среднее число обслуженных заявок к числу поступивших также равно p0: q= p0.

В пределе, при  t®¥, когда процесс обслуживания уже установится, предельное значение q будет равно .

Легко найти и  А, зная  q. Они связаны очевидным соотношением:. В пределе, при  t®¥, А тоже установится и будет равна .

Зная q (вероятность того, что пришедшая в момент t заявка будет обслужена) легко найти вероятность отказа: Pотк =1-q. Pотк есть не что иное, как средняя доля необслуженных заявок среди поданных. В пределе, при t®¥          .

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

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

S0 – все каналы свободны;

S1 – занят ровно один канал, остальные свободны;

……

Sk – заняты ровно k каналов, остальные свободны;

…….

Sn – заняты все n каналов.

Граф состояний имеет следующий вид. Слева направо систему переводит один и тот же поток – поток заявок с интенсивностью l.

Очевидно,  если обслуживанием занято 2 канала, а не один, поток обслуживаний, переводящий систему по стрелке S2®S1,  будет вдвое интенсивнее (2m), если занято k- каналов – в k раз интенсивнее (km). Процесс такого вида представляет собой частный случай процесса гибели и размножения. Составляем уравнения Колмогорова:

  (5.6).  

Уравнения (5.6) называются уравнениями Эрланга. Естественными начальными условиями являются:

p0(0)=1; p1(0)=p2(0)=…=pn(0)=0

Интегрировать (6) в аналитическом виде довольно сложно, на практике решают численно с использованием ЭВМ. Такое решение дает нам все вероятности состояний как функции времени:   p0(t),  p1(t), …, pn(t).

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

    (k=1,2,..n)   (5.7).     

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

(5.8).  Формулы Эрланга.

Теперь можно найти характеристики эффективности  СМО: q, А, Ротк.

Заявка получает отказ, если приходит в момент, когда все n каналов заняты. Вероятность этого равна:

.

              Вероятность того, что заявка будет принята к обслуживанию (она же q) дополняет Ротк до 1: q = 1-pn. И наконец:  А= lq=l(1- pn).

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

как математическое ожидание дискретной случайной величины, принимающей значение 0,1, …n с вероятностями  p0, p1…pn.

              Однако значительно проще выразить через А . А есть не что иное, как среднее число заявок, обслуживаемых в единицу времени; один занятый канал обслуживает в среднем за единицу времени m заявок; следовательно, среднее число занятых каналов

  или .

Одноканальная СМО с ожиданием

              На СМО поступает поток заявок с интенсивностью l, интенсивность обслуживания m (т.е. в среднем непрерывно занятый канал будет выдавать m обслуженных заявок в единицу времени), n=1. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания. Предположим, что количество мест в очереди ограничено числом m (в дальнейшем, при m®¥ можно получить характеристики одноканальной СМО без ограничений по длине очереди). Будем нумеровать состояния СМО по числу заявок, находящихся в системе (как обслуживаемых, так и ожидающих обслуживания):

S0 – канал свободен;  S1 – канал занят, очереди нет; S2 – канал занят, одна заявка стоит в очереди; Sk – канал занят, k -1 стоят в очереди; Sm+1 – канал занят, m заявок стоят в очереди. Граф состояний (размеченный) имеет вид:

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

   или  (5.9).

   В знаменателе выражения для р0 стоит геометрическая прогрессия,                                                  суммируя её находим

          (5.10).                                              

(5.10) справедливо только при (иначе неопределенность вида ). Но сумму геометрической прогрессии со знаменателем найти ещё проще, чем по (5.10); она равна (m+2) и в этом случае p0=1/(m+2) {то  же самое получится, если раскрыть неопределенность по правилу Лапиталя}.

Определим характеристики СМО: Ротк q, А, среднюю длину очереди , среднее число заявок, связанных с системой .

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

                     (5.11).                                    

                 (5.12).                                    

А=lq. Найдем среднее число , находящихся в очереди; определим эту величину как математическое ожидание дискретной случайной величины R – числа заявок , находящихся в очереди:.

.

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

Продифференцируем её  по r и проведя преобразования, найдем 

   (5.13).

Тогда .

Подставляем p0 из (5.10) и получаем

  (5.14).       

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

              По теореме сложения математических ожиданий:

,  где - среднее число заявок в очереди; - среднее число заявок под обслуживанием. Найдем . Т.к. канал у нас один, то случайная величина может принимать только два значения: 0 или 1. Значение 0 она принимает, если канал свободен; вероятность этого равна . Значение 1 она принимает, если канал занят; вероятность этого равна .

Отсюда находим:

.

, где   находим из (5.14).

Выведем выражение еще для одной существенной характеристики СМО с ожиданием: среднего времени ожидания заявки в очереди. Обозначим его . Пусть заявка приходит в систему в какой-то момент времени. С вероятностью p0 канал обслуживания не будет занят и ей не придется стоять в очереди (tож=0). С вероятностью p1 она придет в систему во время обслуживания какой-то заявки, но перед ней не будет очереди, и заявка будет ждать начала своего обслуживания в течение времени 1/m (среднее время обслуживания одной заявки). С вероятностью p2  в очереди перед ней будет стоять еще одна заявка и время ожидания в среднем будет 2/m и т.д. Вообще, с вероятностью pk пришедшая заявка застанет в системе k заявок и будет ждать в среднем k/m единиц времени (1£k£m). При k=m+1 (в очереди m заявок, вероятность этого pm+1) tож=0 (заявка не обслуживается).

.

Подставим сюда выражения для p1,p2,…pm из (5.9).

.

Преобразуем сумму в скобках, используя  (5.13)

Или, выражая p0 через r

.

Сравнивая это выражение с (5.14) , замечаем, что

,   (5.15)                                                  

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

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

Тсист.=Тож +, где Тож - время ожидания заявки в очереди, случайная величина, равная времени обслуживания Тоб, если заявка обслуживается и 0, если она не обслуживается (получает отказ). По теореме сложения математических ожиданий: , но в наших обозначениях , а . Отсюда находим:   или с учетом (5.15)

.

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

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

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

S0 – все каналы свободны;

S1 – занят один канал, остальные свободны;

…  … …

Sk – заняты k каналов, остальные свободны;

… … …

Sn – заняты все n каналов;

Sn+1 – заняты все n каналов, одна заявка стоит в очереди;

… … …

Sn+r – заняты все n каналов, r заявок в очереди;

… … …

Sn+m – заняты все n каналов, m заявок в очереди.

Размеченный граф состояний имеет вид

Написать уравнения Колмогорова. Найти вероятности состояний. В их помощью рассчитать все интересующие величины. Затем опять можно рассмотреть и случай m®¥.

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

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

Решение задачи

АТС имеет 4 линии связи. Поток вызовов простеший с интенсивностью λ вызовов в минуту. Время переговоров распределено по паказательному закону. Среднее время t мин . 

Дано :

λ =0,7- вызовов в минуту.

t=2,4 мин - время на каждую заявку.

Характеристики эффективности работы АТС:

µ - поток обслуживания имеет интенсивность;

p - коэффициент загрузки системы;

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

Q – относительная пропускная способность;

Pотк – вероятность того, что заявка не будет обслужена;

К – среднее число занятых каналов.

1. Обозначим S0, S1, S2, S3, S4 – состояния СМО:

S0 – в системе все каналы свободны,

S1 – один канал занят, три свободны,

S2 – два канала заняты, два свободны,

S3 – три канала заняты, один свободен,

S4 – четыре канала заняты.

Следующая заявка, поступающая в СМО, получает отказ.

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

2. Из условий задачи известно:

λ =0,7 (1/мин);     t=2,4 (мин);     µ =1/t=1/2,4=0,416 (1/мин);

p = λ * t = 0,7*2,4 = 1,68

Найдём нужные вероятности и характеристики:

Р0=(1+1,68+(1,68)2/2!+ (1,68)3/3!+ (1,68)4/4!)-1 = 0,1918

Рi=P0*(Pi/i!)     i=1,2,3,4

P1 = 0, 1918*(1,68/1!) = 0,3222;

P2 = 0,1918*(1,682/2!) = 0,2706;

P3 = 0,1918*(1,683/3!) = 0,1515;

P4 = 0,1918*(1,684/4!) = 0,0636.

Тогда Ротказа=0,0636.

Это значит, что в нашей АТС почти 6 % абонентов получают отказ: Q = 1-Pотк.= 0,9364;   А=Q* λ =0,9364*0,7=0,6554 (1/мин);

Среднее число занятых каналов - К = А / µ = 0,6554 / 0,416 = 1,575

В системе заявка в среднем находиться tсист=К/ λ  = 1,575/ 0,7 = 2,25 (мин).

Результаты расчетов позволяют сделать вывод, что при достаточно высокой вероятности отказа, загруженность АТС составляет около 37%.

3. Т.к. по условию мы можем менять лишь число каналов, то, задав значение n=5,6,7, получим значения для Ротк.