В качестве показателей эффективности СМО с отказами будем рассматривать:

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

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

3) P_{\text{otk}} - вероятность отказа , т.е. того, что заявка покинет СМО необслуженной;

4) \overline{k} - среднее число занятых каналов (для многоканальной системы).

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

Рассмотрим задачу. Имеется один канал, на который поступает поток заявок с интенсивностью \lambda . Поток обслуживании имеет интенсивность \mu . Найти предельные вероятности состояний системы и показатели ее эффективности.

Примечание. Здесь и в дальнейшем предполагается, что все потоки событий, переводящие СМО из состояния в состояние, будут простейшими. К ним относится и поток обслуживании - поток заявок, обслуживаемых одним непрерывно занятым каналом. Среднее время обслуживания обратно по величине интенсивности \mu , т.е. \overline{t}_{\text{ob.}}=1/\mu .

Система S (СМО) имеет два состояния: S_0 - канал свободен, S_1 - канал занят. Размеченный граф состояний представлен на рис. 6.

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

\begin{cases}\lambda\cdot p_0=\mu\cdot p_1,\\\mu\cdot p_1=\lambda\cdot p_0,\end{cases}

т.е. система вырождается в одно уравнение. Учитывая нормировочное условие p_0+p_1=1 , найдем из (18) предельные вероятности состояний

P_0=\frac{\mu}{\lambda+\mu},\quad p_1=\frac{\lambda}{\lambda+\mu}\,

которые выражают среднее относительное время пребывания системы в состоянии S_0 (когда канал свободен) и S_1 (когда канал занят), т.е. определяют соответственно относительную пропускную способность Q системы и вероятность отказа P_{\text{otk}}:

Q=\frac{\mu}{\lambda+\mu}\,

P_{\text{otk}}=\frac{\lambda}{\lambda+\mu}\,.

Абсолютную пропускную способность найдем, умножив относительную пропускную способность Q на интенсивность потока отказов

A=\frac{\lambda\mu}{\lambda+\mu}\,.

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

Решение. Имеем \lambda=90 (1/ч), \overline{t}_{\text{ob.}}=2 мин. Интенсивность потока обслуживании \mu=\frac{1}{\overline{t}_{\text{ob.}}}=\frac{1}{2}=0,\!5 (1/мин) =30 (1/ч). По (20) относительная пропускная способность СМО Q=\frac{30}{90+30}=0,\!25 , т.е. в среднем только 25% поступающих заявок осуществят переговоры по телефону. Соответственно вероятность отказа в обслуживании составит P_{\text{otk}}=0,\!75 (см. (21)). Абсолютная пропускная способность СМО по (29) A=90\cdot0.\!25=22,\!5 , т.е. в среднем в час будут обслужены 22,5 заявки на переговоры. Очевидно, что при наличии только одного телефонного номера СМО будет плохо справляться с потоком заявок.

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

Рассмотрим классическую задачу Эрланга . Имеется n каналов, на которые поступает поток заявок с интенсивностью \lambda . Поток обслуживании имеет интенсивность \mu . Найти предельные вероятности состояний системы и показатели ее эффективности.

Система S (СМО) имеет следующие состояния (нумеруем их по числу заявок, находящихся в системе): S_0,S_1,S_2,\ldots,S_k,\ldots,S_n , где S_k - состояние системы, когда в ней находится k заявок, т.е. занято k каналов.

Граф состояний СМО соответствует процессу гибели и размножения и показан на рис. 7.

Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсивностью \lambda . Интенсивность же потока обслуживании, переводящих систему из любого правого состояния в соседнее левое состояние, постоянно меняется в зависимости от состояния. Действительно, если СМО находится в состоянии S_2 (два канала заняты), то она может перейти в состояние S_1 (один канал занят), когда закончит обслуживание либо первый, либо второй канал, т.е. суммарная интенсивность их потоков обслуживании будет 2\mu . Аналогично суммарный поток обслуживании, переводящий СМО из состояния S_3 (три канала заняты) в S_2 , будет иметь интенсивность 3\mu , т.е. может освободиться любой из трех каналов и т.д.

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

P_0={\left(1+ \frac{\lambda}{\mu}+ \frac{\lambda^2}{2!\mu^2}+\ldots+\frac{\lambda^k}{k!\mu^k}+\ldots+ \frac{\lambda^n}{n!\mu^n}\right)\!}^{-1},

где члены разложения \frac{\lambda}{\mu},\,\frac{\lambda^2}{2!\mu^2},\,\ldots,\,\frac{\lambda^k}{k!\mu^k},\,\ldots,\, \frac{\lambda^n}{n!\mu^n} , будут представлять собой коэффициенты при p_0 в выражениях для предельных вероятностей p_1,p_2,\ldots,p_k,\ldots,p_n . Величина

\rho=\frac{\lambda}{\mu}

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

P_0={\left(1+\rho+\frac{\rho^2}{2!}+\ldots+\frac{\rho^k}{k!}+\ldots+\frac{\rho^n}{n!}\right)\!}^{-1},

P_1=\rho\cdot p,\quad p_2=\frac{\rho^2}{2!}\cdot p_0,\quad \ldots,\quad p_k=\frac{\rho^k}{k!}\cdot p_0,\quad \ldots,\quad p_n=\frac{\rho^n}{n!}\cdot p_0.

Формулы (25) и (26) для предельных вероятностей получили названия формул Эрланга в честь основателя теории массового обслуживания.

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

P_{\text{otk}}= \frac{\rho^n}{n!}\cdot p_0.

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

Q=1- P_{\text{otk}}=1-\frac{\rho^n}{n!}\cdot p_0.

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

A=\lambda\cdot Q=\lambda\cdot\left(1-\frac{\rho^n}{n!}\cdot p_0\right)\!.

Среднее число занятых каналов \overline{k} есть математическое ожидание числа занятых каналов:

\overline{k}=\sum_{k=0}^{n}(k\cdot p_k),

где p_k - предельные вероятности состояний, определяемых по формулам (25), (26).

Однако среднее число занятых каналов можно найти проще, если учесть, что абсолютная пропускная способность системы A есть не что иное, как интенсивность потока обслуженных системой заявок (в единицу времени). Так как каждый занятый канал обслуживает в среднем \mu заявок (в единицу времени), то среднее число занятых каналов

\overline{k}=\frac{A}{\mu}

Или, учитывая (29), (24):

\overline{k}=\rho\cdot\left(1-\frac{\rho^n}{n!}\cdot p_0\right)\!.

Пример 6. В условиях примера 5 определить оптимальное число телефонных номеров в телевизионном ателье, если условием оптимальности считать удовлетворение в среднем из каждых 100 заявок не менее 90 заявок на переговоры.

Решение. Интенсивность нагрузки канала по формуле (25) \rho=\frac{90}{30}=3 , т.е. за время среднего (по продолжительности) телефонного разговора \overline{t}_{\text{ob.}}=2 мин. поступает в среднем 3 заявки на переговоры.

Будем постепенно увеличивать число каналов (телефонных номеров) n=2,3,4,\ldots и определим по формулам (25), (28), (29) для получаемой n-канальной СМО характеристики обслуживания. Например, при n=2 имеем

З_0={\left(1+3+ \frac{3^2}{2!}\right)\!}^{-1}=0,\!118\approx0,\!12;\quad Q=1-\frac{3^2}{2!}\cdot0,\!118=0,\!471\approx0,\!47;\quad A=90\cdot0,\!471=42,\!4 и т.д.

Значение характеристик СМО сведем в табл. 1.

По условию оптимальности Q\geqslant0,\!9 , следовательно, в телевизионном ателье необходимо установить 5 телефонных номеров (в этом случае Q=0,\!9 - см. табл. 1). При этом в час будут обслуживаться в среднем 80 заявок (A=80,\!1) , а среднее число занятых телефонных номеров (каналов) по формуле (30) \overline{k}=\frac{80,\!1}{30}=2,\!67 .

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

Решение. По условию n=3,~\lambda=0,\!25 (1/ч), \overline{t}_{\text{ob.}} =3 (ч). Интенсивность потока обслуживании \mu=\frac{1}{\overline{t}_{\text{ob.}}}=\frac{1}{3}=0,\!33 . Интенсивность нагрузки ЭВМ по формуле (24) \rho=\frac{0,\!25}{0,\!33}=0,\!75 . Найдем предельные вероятности состояний:

– по формуле (25) p_0={\left(1+0,\!75+ \frac{0,\!75^2}{2!}+ \frac{0,\!75^3}{3!}\right)\!}^{-1}=0,\!476 ;

– по формуле (26) p_1=0,!75\cdot0,\!476=0,\!357;~p_2=\frac{0,\!75^2}{2!}\cdot0,\!476=0,\!134;~p_3=\frac{0,\!75^3}{3!}\cdot0,\!476=0,\!033 ;

т.е. в стационарном режиме работы вычислительного центра в среднем 47,6% времени нет ни одной заявки, 35,7% - имеется одна заявка (занята одна ЭВМ), 13,4% - две заявки (две ЭВМ), 3,3% времени - три заявки (заняты три ЭВМ).

Вероятность отказа (когда заняты все три ЭВМ), таким образом, P_{\text{otk}}=p_3=0,\!033 .

По формуле (28) относительная пропускная способность центра Q=1-0,\!033=0,\!967 , т.е. в среднем из каждых 100 заявок вычислительный центр обслуживает 96,7 заявок.

По формуле (29) абсолютная пропускная способность центра A=0,\!25\cdot0,\!967=0,\!242 , т.е. в один час в среднем обслуживается. 0,242 заявки.

По формуле (30) среднее число занятых ЭВМ \overline{k}=\frac{0,\!242}{0,\!33}=0,\!725 , т.е. каждая из трех ЭВМ будет занята обслуживанием заявок в среднем лишь на \frac{72,\!5}{3}= 24,\!2%. .

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

В вашем браузере отключен Javascript.
Чтобы произвести расчеты, необходимо разрешить элементы ActiveX!

Система Эрланга
В качестве показателей эффективности СМО с отказами будем рассматривать:
А - абсолютную пропускную способность СМО, т.е. среднее число заявок, обслуживаемых в единицу времени;
Q - относительную пропускную способность, т.е. среднюю долю пришедших заявок, обслуживаемых системой;
P отк. - вероятность отказа, т.е. того, что заявка покинет СМО необслуженной;
- среднее число занятых каналов (для многоканальной системы).
Одноканальная система с отказами . Рассмотрим задачу.
Имеется один канал, на который поступает поток заявок с интенсивностью λ. Поток обслуживаний имеет интенсивность μ 1 . Найти предельные вероятности состояний системы и показатели ее эффективности.
Система S (СМО) имеет два состояния: S 0 - канал свободен, S 1 - канал занят. Размеченный граф состояний представлен на рис. 6.

Рис. 6
В предельном, стационарном режиме система алгебраических уравнений для вероятностей состояний имеет вид.
(18)
т.е. система вырождается в одно уравнение. Учитывая нормировочное условие p 0 +p 1 =1, найдем из (18) предельные вероятности состояний
(19)
которые выражают среднее относительное время пребывания системы в состоянии S 0 (когда канал свободен) и S 1 (когда канал занят), т.е. определяют соответственно относительную пропускную способность Q системы и вероятность отказа P отк:
(20)
(21)
Абсолютную пропускную способность найдем, умножив относительную пропускную способность Q на интенсивность потока отказов
(22)
Задача 5. Известно, что заявки на телефонные переговоры в телевизионном ателье поступают с интенсивностью λ, равной 90 заявок в час, а средняя продолжительность разговора по телефону об. =2 мин. Определить показатели эффективности работы СМО (телефонной связи) при наличии одного телефонного номера.
Решение. Имеем λ=90 (1/ч), об. =2 мин. Интенсивность потока обслуживании μ=1/ об =1/2=0,5 (1/мин)=30 (1/ч). По (20) относительная пропускная способность СМО (Q=30/(90+30)=0,25, т.е. в среднем только 25% поступающих заявок осуществят переговоры по телефону. Соответственно вероятность отказа в обслуживании составит Р отк. =0,75 (см. (21)). Абсолютная пропускная способность СМО по (29) ,A=90∙0,25=22,5, т.е. в среднем в час будут обслужены 22,5 заявки на переговоры. Очевидно, что при наличии только одного телефонного номера СМО будет плохо справляться с потоком заявок.
Многоканальная система с отказами . Рассмотрим классическую задачу Эрланга.
Имеется n каналов, на которые поступает поток заявок с интенсивностью λ. Поток обслуживаний имеет интенсивность μ. Найти предельные вероятности состояний системы и показатели ее эффективности.
Система S (СМО) имеет следующие состояния (нумеруем их по числу заявок, находящихся в системе): S 0 , S 1 , S 2 , …, S k , …, S n , где S k - состояние системы, когда в ней находится k заявок, т.е. занято k каналов.
Граф состояний СМОсоответствует процессу гибели и размножения и показан на рис. 7.

Рис. 7
Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсивностью λ. Интенсивность же потока обслуживаний, переводящих систему из любого правого состояния в соседнее левое состояние, постоянно меняется в зависимости от состояния. Действительно, если СМО находится в состоянии S 2 (два канала заняты), то она может перейти в состояние. S 1 (один канал занят), когда закончит обслуживание либо первый, либо второй канал, т.е. суммарная интенсивность их потоков обслуживании будет 2μ. Аналогично суммарный поток обслуживаний, переводящий СМО из состояния S 3 (три канала заняты) в S 2 . будет иметь интенсивность Зμ, т.е. может освободиться любой из трех каналов и т.д.
В формуле (16) для схемы гибели и размножения получим для предельной вероятности состояния
(23)
где членыразложения будут представлять собой коэффициенты приp 0 в выражениях для предельных вероятностей p 1 , p 2 , …, p k , …, p n . Величина
(24)
называется приведенной интенсивностью потока заявок или интенсивностью нагрузки канала. Она выражает среднее число заявок, приходящее за среднее время обслуживания одной заявки. Теперь
(25) есть не что иное, как интенсивность потока обслуженных системой заявок (в единицу времени). Так как каждый занятый канал обслуживает в среднем μ заявок (в единицу времени), то среднее число занятых каналов
(30)
или, учитывая (29), (24):
(31)

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

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

Система массового обслуживания может находиться в одном из двух состояний: s 0 - канал свободен (простаивает) или s, - канал занят. Из состояния s 0 в состояние s, систему переводит поток входящих заявок, а из состояния s, в состояние s 0 - поток обслуживании. Плотности вероятностей переходов из состояния s 0 в состояние s { и обратно равны соответственно X и р.

Граф состояний СМО показан на рис. 1.5.

Рис.

в состоянии s 0 или s t соответственно. Очевидно, что справедливо нормировочное условие p 0 (t) + Pi (t) = 1.

Учитывая, что случайный процесс, протекающий в СМО, является марковским, вероятности p 0 (t) и pj(t) можно определить из системы уравнений Колмогорова:

Подстановка нормировочного условия в эту систему приводит к обыкновенному дифференциальному уравнению относительно p 0 (t):

Принимая условие, что в начальный момент времени при t = О канал свободен, т. е. р 0 (0) = 1 и pj(0) = 0, можно получить решение уравнения (1.20) в следующем виде:

С использованием нормировочного условия можно также установить выражение для определения pj(t):

В предельном стационарном режиме (при t -» °°) система алгебраических уравнений для вероятностей состояний имеет вид:

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

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

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

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

Вероятность отказа в СМО возникает, когда канал занят, это вероятность Р!

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

Аналогично можно определить среднее время простоя канала:

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

Пример 1.4. На телефонную линию оператора сотовой связи приходит простейший поток вызовов с интенсивностью X = 1,5 заявки в минуту. Производительность линии р = 0,4 вызова в минуту. Вызов, пришедший на линию во время ее занятости, не обслуживается. Определить абсолютную пропускную способность линии, среднее время обслуживания одного вызова, вероятность отказов обслуживаний, а также среднее время пребывания заявки в системе.

Решение. 1. По формулам (1.27)-(1.31), проведя необходимые расчеты, получаем: А = 0,32 выз./мин; р отк = 0,79; t o6cjI = 2,5 мин;

• 1 сист = °> 52 МИН -
• 2. Расчетные данные свидетельствуют о том, что при наличии одного телефонного номера СМО будет плохо справляться с потоком заявок.

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

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

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

Система имеет следующие состояния: где s k -

состояние системы, когда в ней находится к заявок, т. е. занято к каналов.

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

Рис. 1.6.

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

Воспользовавшись формулой (1.18) для процесса гибели и размножения, получим следующее выражение для предельной вероятности состояния р 0

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

Используя выражение (1.19), имеем:

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

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

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

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

Абсолютная пропускная способность СМО (она же интенсивность потока обслуженных заявок):

Для многоканальных СМО важным показателем эффективности их работы является среднее число занятых каналов к (математическое ожидание числа занятых каналов)

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

Пример 1.5. Вычислительный центр электросетевой компании оборудован тремя ЭВМ, на которые поступают заказы по выполнению вычислительных работ. Если работают одновременно все три ЭВМ, то вновь поступающий заказ не принимается. Среднее время работы с одним заказом 2,5 ч. Интенсивность потока заявок 0,2 ч -1 . Определить и проанализировать предельные вероятности состояний и показатели эффективности работы вычислительного центра.

Решение. 1. Определим параметры СМО: п = 2; X = 0,2 ч -1 ;

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

; интенсивность нагрузки ЭВМ р = 0,2/0,4 = 0,5.

2. Найдем вероятности состояний: вероятность того, что в системе отсутствуют заявки:

вероятности других состояний:

вероятность того, что пришедшая заявка получит отказ:

Таким образом, в стационарном режиме работы вычислительного центра в среднем в течение 61 % времени нет ни одной заявки, в 30 % времени имеется одна заявка (занята одна ЭВМ), в 8 % - две заявки (заняты две ЭВМ) и в 1 % - три заявки (заняты три ЭВМ). Вероятность отказа, когда все три ЭВМ заняты - р отк = 0,01.

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

т. е. из каждой сотни заявок вычислительный центр обслуживает 99;

абсолютная пропускная способность вычислительного центра:

т. е. в один час в среднем обслуживается 0,2 заявки; среднее число занятых ЭВМ:

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

Использование теории массового обслуживания при организации сервиса машин

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

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

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

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

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

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

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

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

· среднее число обслуженных заявок и заявок, получивших отказ;

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

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

Виды систем массового обслуживания

Различают два основных вида систем массового обслуживания:

1. Системы с отказами, в которых заявка, поступившая в систему в момент, когда все каналы заняты, получает отказ и покидает систему;

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

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

Одноканальная система с отказами.

Рассмотрим простейший случай, когда СМО имеет в своем распоряжении всего один канал обслуживания (п =1) и работает с отказами. Состояние данной системы можно изобразить графически в виде графа состояний: где х 0 - состояние системы, когда канал не занят; х 1 - состояние системы, когда канал занят; Р - вероятности перехода системы из одного состояния в другое (Р 00 ∆t не поступит ни одной заявки; Р 10 ∆t заявка будет обслужена; P 01 - вероятность того, что за время ∆t поступит заявка; Р 11 - вероятность того, что за время ∆t заявка не обслужится).

Р 01

х 1

х 0

Р 11

Р 00

Р 10

х 0

х 1

Рис. 5.1. Граф состояний одноканальной СМО с отказами

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

где Р(к) - вероятность того, что за время ∆t поступит к заявок (к = 0,1,2,…); λ - плотность или интенсивность заявок, то есть среднее число заявок в единицу времени; ∆t - отрезок времени, за который рассматривается вероятность поступления заявок;

Вероятность того, что за время ∆t не поступит ни одной заявки (к = 0) составит

. (5.2)

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

, (5.3)

где μ - интенсивность обслуживания, то есть среднее число обслуживаний в единицу времени μ = 1/М t об ; М t об - среднее время обслуживания заявки.

Вероятность того, что за время ∆t заявка будет обслужена, составит

При этом вероятность того, что за время ∆t заявка не будет обслужена, составит

Сравнивая выражения (5.2) и (5.5) видим, что время между двумя заявками распределено по показательному закону. Это позволяет моделировать случайные моменты времени поступления заявок на обслуживание.

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

Отбрасывая члены ряда второго порядка и выше для выражений (5.2) и (5.4) запишем

Канал может быть в состоянии х 0 в двух случаях:

1. в момент t х 0 , а за время Δt не пришло ни одной заявки;

2. в момент t система находилась в состоянии х 1 , а за время ∆t канал освободился и система перешла в состояние х 0 .

Вероятность того, что в момент времени (t+ ∆t ) система будет находиться в х 0 состоянии по теореме сложения вероятностей равна сумме вероятности двух указанных выше случаев

Вероятность указанных выше событий (1 и 2) равна произведению вероятностей событий в них входящих.

Раскрывая скобки и группируя переменные, получаем

. (5.10)

Аналогично и для

(5.11)

Уравнения (5.10) и (5.11) называются разностными. Переходя к пределу при ∆t→ 0, получаем систему дифференциальных уравнений Эрланга

, (5.12)

. (5.13)

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

Для установившегося режима (λ = const) производные равны нулю, поэтому система дифференциальных уравнений (5.12) и (5.13) преобразуется в систему алгебраических уравнений, в частности для одноканальной системы с отказами получим

, откуда . (5.14)

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

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

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

Из равенства (5.14) с учетом того, что Р 0 +Р 1 = 1, получаем

, откуда

, (5.15)

при этом , (5.16)

где α= λ/μ - приведенная плотность или загрузка системы.

Пример: Исследуется работа СТОА с отказами. Станция имеет один подъемник (канал, п = 1). На станцию поступает простейший пуассоновский поток заявок с плотностью λ = 5 автомобилей в час. Время обслуживания распределено по показательному закону и характеризуется средней продолжительностью М t об = 0,333 ч на автомобиль. Определить показатели эффективности станции за 10 - часовой рабочий день.

1. Плотность или интенсивность обслуживания μ = 1/ М t об = 1/0,333= 3 автомобиля в ч.

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

= 0,375

Следовательно, 37,5% прибывающих автомобилей будет поставлено на немедленное обслуживание.

3. Находим абсолютную пропускную способность станции

λ∙ Р 0 = 5∙0,375 = 1,875 авт. в ч,

а за десять ч 18,75 автомобиля.

4. Определим вероятность отказа

Р отк = 1- Р 0 = 1 - 0,375 = 0,625.

Следовательно, 62,5% прибывающих автомобилей получают отказ.

5. Находим номинальную или максимально возможную пропускную способность за 10 часовой рабочий день

= 3 · 10 = 30 автомобиля в день.

Как видим, абсолютная пропускная способность примерно в 1,5 раза меньше номинальной. Это расхождение объясняется случайным характером потока заявок и случайным временем обслуживания заявок.

Рассмотрим СМО с одним каналом обслуживания, в которую поступает поток требований с интенсивностью λ . Интенсивность обслуживания одного требования равна μ . Требуется найти предельные вероятности состояний системы и показатели ее эффективности. Система S в данном случае имеет 2 состояния: S 0 - канал свободен и S 1 канал занят. Нарисуем граф состояний системы, т.е. геометрическую схему, на которой состояние системы изображаются прямоугольниками, а переходы из состояния в состояние - стрелками:

S 0 μ S 1

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

Для данного графа система уравнений для вероятностей состояний имеет вид:

l ρ 0 =μ ρ 1

m ρ 1 =λ ρ 0

т.е. имеет одинаковые уравнения. Учитывая, что р 1 +р 0 =1, получаем систему:

l ρ 0 =μ ρ 1

ρ 1 =ρ 0 =1 (6.6)

Обозначим:

a =λ /μ (6.7)

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

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

р 1 - вероятность того, что канал занят, т.е. вероятность отказа.

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

A = λ × p 0 (6.9)

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

N = a × (1– P отк ) (6.10)

Пример: Стол заказов магазина принимает заказы по одному телефону. Заявки поступают с интенсивностью 80 заявок в час, а среднее время оформления одной заявки 3 минуты. Определить показатели эффективности работы стола заказов.

Решение: λ =80заявок/час, t =3мин.

Вычислим интенсивность загрузки канала a . При этом следует обратить внгимание, что при вычислении a , λ и t должны иметь одинаковую временную размерность. Поэтому в нашем примере нужно преобразовать одну из данных величин, например, t .

t =2мин=3/60часа=1/20часа.

Тогда

1. Доля времени простоя канала:

Следовательно, 20% времени канал будет свободен, значит в среднем только 20% заявок может быть обслужено.

2. Доля заявок, получивших отказ в обслуживании, равна:

т.е. 80% времени телефон будет занят обслуживанием.

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

Из вычислений видно, что СМО с одним телефоном будет плохо справляться с потоком заявок, т.к. потери поступающих заявок составляют 80%, а вероятность обслуживания всего 20%. Кроме того, низка абсолютная пропускная способность системы – только 16 завявок из 80 поступивших.