Моделирование СМО ОКМ ДМ экономическая информатика визуальные среды - 4GL Теория и практика обработки информации

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

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

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

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

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

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

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

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

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

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

Примечание. Здесь и в дальнейшем предполагается, что все потоки событий, переводящие СМО из состояния в состояние, будут простейшими. К ним относится и поток обслуживании — поток заявок, обслуживаемых одним непрерывно занятым каналом. Среднее время обслуживания $\overline{t}_{\text{ob.}}$ обратно по величине интенсивности $\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}$

(18)

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

$p_0=\frac{\mu}{\lambda+\mu},\quad p_1=\frac{\lambda}{\lambda+\mu}\,,$

(19)

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

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

(20)

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

(21)

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

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

(22)

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

Решение. Имеем $\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},$

(23)

где члены разложения $\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}$

(24)

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

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

(25)

$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.$

(26)

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

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

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

(27)

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

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

(28)

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

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

(29)

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

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

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

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

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

(30)

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

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

(31)

Пример 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%.$ .

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

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

НОВОСТИ ФОРУМА

Рыцари теории эфира