Пример

Подсчет средних характеристик

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

Такие системы при условии, что нет ограничений на длину очереди, имеют бесчисленное множество состояний:

Е 0 , Е 1 , Е 2 , Е 3 , ...

Е 0 – в системе 0 требований (система свободна);

Е 1 – в системе 1 требование (система занята);

Е 2 – в системе 1 требование, и одно требование ожидает в очереди;

Е 3 – в системе 1 требование, и два требования ожидают в очереди и т. д.

P 0 = 1-φ, φ = λ/μ.

Следовательно,

P k = (1-φ)φ k , k = 1, 2, ….

Условие φ > 0 является необходимым и достаточным для наличия стационарного режима работы системы.

Интересно знать, почему стационарный режим существует только при этом условии?

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

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

n – количество требований, находящихся в системе;

v – длина очереди;

w – время ожидания в очереди.

Ниже их формулы:

v = φ 2 /(1-φ);

w = [φ/(1-φ)]*.

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

Решение

Определяем коэффициент загрузки системы:

n = 0,8/(1-0,8) = 4;

v = 4*0,8 = 3,2;

Сделаем следующие предположения относительно таких систем:

· входной поток пуассоновский;

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

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

· все линии обслуживания работают независимо.

Будем считать, что система содержит некоторое количество линий обслуживания s. Она может находиться в состояниях Е 0 , Е 1 , Е 2 , Е 3 , ... Е S . Расчёт переходных вероятностей показывает, что из каждого из свободных состояний система может переходить в соседнее состояние, либо в такое же, в каком была.

Для нахождения вероятностей используется следующая формула:

P k = φ k /k!*P 0 , φ = λ/μ, где k = 1, 2, ...

Так как сумма всех вероятностей составляет 1, то

Отсюда следуют формулы:

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

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

ρ = s-φ(1-P s).

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

Таким образом, мы имеем дело с двумя противоположными тенденциями. Задача сводится к выбору оптимального варианта. С этой целью будем минимизировать функцию стоимости СМО – С(s). Если через с 1 мы обозначим стоимость одного отказа (организатор системы платит штраф за каждый отказ), а через с 2 – стоимость простоя одной линии за единицу времени, то функция стоимости будет иметь следующий вид:

C(s) = c 1 λP s +c 2 ρ.

Или в развернутом виде:

Сначала с увеличением s она убывает, а затем растёт. Наша задача состоит в том, чтобы найти её минимум.

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

Все каналы свободны,

Занят ровно один канал, остальные свободны,

Заняты ровно k каналов, остальные свободны,

Заняты все каналов.

Граф состояний СМО представлен на рис. 5.3. Разметим граф, т. е. проставим у стрелок интенсивности соответствующих потоков событий.

По стрелкам слева направо систему переводит один и тот же поток - ноток заявок с интенсивностью к. Если система находится в состоянии (занято k каналов) и пришла новая заявка, система переходит (перескакивает) в состояние

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

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

Из рис. 5.3 видно, что процесс, протекающий в СМО, представляет собой частный случай процесса гибели и размножения, рассмотренного нами в § 8 гл. 4.

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

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

(в начальный момент система свободна).

Интегрирование системы уравнений (4.1) в аналитическом виде довольно сложно; на практике такие системы дифференциальных уравнений обычно решаются численно, на АВМ или ЭЦВМ. Такое решение дает нам все вероятности состояний

как функции времени.

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

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

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

С учетом этого обозначения, формулы (4.2) примут вид:

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

Зная все вероятности состояний

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

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

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

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

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

Величину k можно вычислить непосредственно через вероятности по формуле:

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

Рассмотрим многоканальную систему массового обслуживания (всего каналов n), в которую поступают заявки с интенсивностью λ и обслуживаются с интенсивностью μ. Заявка, прибывшая в систему, обслуживается, если хотя бы один канал свободен. Если все каналы заняты, то очередная заявка, поступившая в систему, получает отказ и покидает СМО. Пронумеруем состояния системы по числу занятых каналов:

• S 0 – все каналы свободны;
• S 1 – занят один канал;
• S 2 – занято два канала;
• S k – занято k каналов;
• S n – все каналы заняты.

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

Рис. 7.24
На рисунке 6.24 изображен граф состояний, в котором S i – номер канала; λ – интенсивность поступления заявок; μ – соответственно интенсивность обслуживания заявок. Заявки поступают в систему массового обслуживания с постоянной интенсивностью и постепенно занимают один за другим каналы; когда все каналы будут заняты, то очередная заявка, прибывшая в СМО, получит отказ и покинет систему.
Определим интенсивности потоков событий, которые переводят систему из состояния в состояние при движении как слева направо, так и справа налево по графу состояний.
Например, пусть система находится в состоянии S 1 , т. е. один канал занят, поскольку на его входе стоит заявка. Как только обслуживание заявки закончится, система перейдет в состояние S 0 .
Например, если заняты два канала, то поток обслуживания, переводящий систему из состояния S 2 в состояние S 1 будет вдвое интенсивнее: 2-μ; соответственно, если занято k каналов, интенсивность равна k-μ.

Процесс обслуживания является процессом гибели и размножения. Уравнения Колмогорова для этого частного случая будут иметь следующий вид:

(7.25)
Уравнения (7.25) называются уравнениями Эрланга .
Для того, чтобы найти значения вероятностей состояний Р 0 , Р 1 , …, Р n , необходимо определить начальные условия:
– Р 0 (0) = 1, т. е. на входе системы стоит заявка;
– Р 1 (0) = Р 2 (0) = … = Р n (0) = 0, т. е. в начальный момент времени система свободна.
Проинтегрировав систему дифференциальных уравнений (7.25), получим значения вероятностей состояний Р 0 (t ), Р 1 (t ), … Р n (t ).
Но гораздо больше нас интересуют предельные вероятности состояний. При t → ∞ и по формуле, полученной при рассмотрении процесса гибели и размножения, получим решение системы уравнений (7.25):

(7.26)
В этих формулах отношение интенсивности λ / μ к потоку заявок удобно обозначить ρ .Эту величину называют приведенной интенсивностью потока заявок, то есть среднее число заявок, приходящих в СМО за среднее время обслуживания одной заявки.

С учетом сделанных обозначений система уравнений (7.26) примет следующий вид:

(7.27)
Эти формулы для вычисления предельных вероятностей называются формулами Эрланга .
Зная все вероятности состояний СМО, найдем характеристики эффективности СМО, т. е. абсолютную пропускную способность А , относительную пропускную способность Q и вероятность отказа Р отк.
Заявка, поступившая в систему, получит отказ, если она застанет все каналы занятыми:

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

Q = 1 – Р отк,
где Q – средняя доля поступивших заявок, обслуживаемых системой, или среднее число заявок обслуженных СМО в единицу времени, отнесенное к среднему числу поступивших за это время заявок:

A=λ·Q=λ·(1-P отк)
Кроме того, одной из важнейших характеристик СМО с отказами является среднее число занятых каналов . В n -канальной СМО с отказами это число совпадает со средним числом заявок, находящихся в СМО.
Среднее число заявок k можно вычислить непосредственно через вероятности состояний Р 0 , Р 1 , … , Р n:

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

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

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

Q - относительную пропускную способность, т.е.

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

/’отк. - вероятность отказа, т.е. того, что заявка покинет СМО необслуженной;

к - среднее число занятых каналов (для многоканальной системы). Одноканальная система с отказами. Рассмотрим задачу.

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

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

кро - Ц/>1, V-P\ - kp0,

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

15.5. Известно, что заявки на телефонные переговоры в телевизи­онном ателье поступают с интенсивностью X, равной 90 заявок в час, а средняя продолжительность разговора по телефону / 0б.=2 мин. Определить показатели эффективности работы СМО (телефонной связи) при наличии одного телефонного номера.

Решение. Имеем Х=90 (1/ч), ґ 0б=2 мин. Интенсивность по­тока обслуживании |д.=1/Г об.” 1/2=0,5 (1/мин)=30 (1/ч). По (15.20) относительная пропускная способность СМО 0=ЗО/(9О+ЗО)=О,25, т.е. в среднем только 25% поступающих заявок осуществят пере­говоры по телефону. Соответственно вероятность отказа в обслу­живании составит /отк=0,75 (см. (15.21)). Абсолютная пропускная способность СМО по (15.29) Л=900,25=22,5, т.е. в среднем в час будут обслужены 22,5 заявки на переговоры. Очевидно, что при наличии только одного телефонного номера СМО будет плохо справляться с потоком заявок.

Многоканальная система с отказами. Рассмотрим классическую задачу Эрланга.

Имеется п каналов, на которые поступает поток заявок с ин­тенсивностью X. Поток обслуживании имеет интенсивность ц. Найти предельные вероятности состояний системы и показатели № эффективности.

Система 5 (СМО) имеет следующие состояния (нумеруем их то числу заявок, находящихся в системе): 5о, і’г, -, ... Эп,

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

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

	А _		А. __
*		*5|		*$!
	ц		* 2ц

я.

X ... А.

"зіг

Рис. 15.7 Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсив­ностью X. Интенсивность же потока обслуживании, переводящих систему из любого правого состояния в соседнее левое состояние, постоянно меняется в зависимости ОТ СОСТОЯНИЯ. Действительно*! если СМО находится в состоянии 5г (два канала заняты), то ощ может перейти в состояние 5) (один канал занят), когда закончит обслуживание либо первый, либо второй канал, т.е. суммарная интенсивность их потоков обслуживании будет 2ц. Аналогично суммарный поток обслуживании, переводящий СМО из состоя­ния 5з (три канала заняты) в 52, будет иметь интенсивность Зц, т.е. может освободиться любой из трех каналов и т.д. В формуле (15.16) для схемы гибели и размножения получим для предельной вероятности состояния

Р\=РРо, Р2=^Ро, > Рк=^Ро, Рп~Ро- (15.26)

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

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

0 = 1-Р07К = 1-£Ро.

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

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

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

(15.31)

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

Решение. Интенсивность нагрузки канала по формуле

(15.25) р=90/30=3, т.е. за время среднего (по продолжительности) телефонного разговора I „б=2 мин. поступает в среднем 3 заявки на переговоры.

Будем постепенно увеличивать число каналов (телефонных номеров) л=2, 3, 4, ... и определим по формулам (15.25), (15.28),

(15.29) для получаемой л-канальной СМО характеристики обслу­живания. Например, при п = 2 р0=^1 + 3 + 32/2!) = 0,118 » 0,12;

б = 1 - (з2/2!)- 0,118 = 0.471 * 0,47 ; Л=900,471=42,4 и т.д. Значение характеристик СМО сведем в табл. 15.1.

Таблица 15.1

По условию оптимальности 0 £ 0,9, следовательно, в телевизи­онном ателье необходимо установить 5 телефонных номеров (в этом случае 0 = 0,90 - см. табл. 15.1). При этом в час будут об­служиваться в среднем 80 заявок (А = 80,1), а среднее число заня­тых телефонных номеров (каналов) по формуле (15.30) к = = 80,1/30 = 2,б7>

1> 15.7. В вычислительный центр коллективного пользования с тремя ЭВМ поступают заказы от предприятий на вычислительные работы. Если работают все три ЭВМ, то вновь поступающий заказ

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

Решение. По условию п=3* А,=0,25 (1/ч), Г0б=3 (ч). Интен­сивность потока обслуживаний ц= 1/ 0б.=1 /3=0,33. Интенсив­ность нагрузки ЭВМ по формуле (15.24) р=0,25/0,33=0,75. Найдем предельные вероятности состояний:

по формуле (15.25) р0=(1+0,75+0,752/2!+0,753/3!)"*=0,476;

по формуле (15.26) ^1=0,750,476=0,357; /?2=(0»752/2!) 0,47б= =0,134; рз=(0,753/3!) 0,476=0,033, т.е. в стационарном режиме ра­боты вычислительного центра в среднем 47,6% времени нет ни одной заявки, 35,7% - имеется одна заявка (занята одна ЭВМ), 13,4% - две заявки (две ЭВМ), 3,3% времени - три заявки (заняты три ЭВМ).

Вероятность отказа (когда заняты все три ЭВМ), таким обра­зом, Яотк=рз=0,033.

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

По формуле (15.29) абсолютная пропускная способность цен­тра А = 0,25-0,967 = 0,242, т.е. в один час в среднем обслуживается 0,242 заявки.

По формуле (15.30) среднее число занятых ЭВМ к = = 0,242/0,33 = 0,725, т.е. каждая из трех ЭВМ будет занята обслу­живанием заявок в среднем лишь на 72,5/3 = 24,2%.

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

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

Для СМО с отказами :

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

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

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

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

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

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

Рассмотрим примеры некоторых СМО.

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

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

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

Описание состояний:

Все инспекторы свободны;

Занят один инспектор;

Заняты два инспектора;

Заняты три инспектора.

Граф состояний системы приведен на рис. 2.11 .

Рис. 2.11.

На графе: - интенсивность потока грузовых автомобилей; - интенсивность проверок документов одним автоинспектором.

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

Решение

Искомая часть вероятности - вероятности занятости всех трех инспекторов. Поскольку граф состояний представляет типовую схему "гибели и размножения", то найдем , используя зависимости (2.2).

Пропускную способность этого поста автоинспекторов можно характеризовать относительной пропускной способностью :

Пример 2.6 . Для приема и обработки донесений от разведгруппы в разведотделе объединения назначена группа в составе трех офицеров. Ожидаемая интенсивность потока донесений - 15 донесений в час. Среднее время обработки одного донесения одним офицером - . Каждый офицер может принимать донесения от любой разведгруппы. Освободившийся офицер обрабатывает последнее из поступивших донесений. Поступающие донесения должны обрабатываться с вероятностью не менее 95 %.

Определить, достаточно ли назначенной группы из трех офицеров для выполнения поставленной задачи.

Решение

Группа офицеров работает как СМО с отказами, состоящая из трех каналов.

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

Описание состояний и граф состояний СМО будут аналогичны приведенным в примере 2.5.

Поскольку граф состояний - это схема "гибели и размножения", то для нее имеются готовые выражения для предельных вероятностей состояния:

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

В примере .

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

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

Таким образом, только группа из шести офицеров сможет обрабатывать поступающие донесения с вероятностью 95 %.

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

Пример 2.7 . На участке форсирования реки имеются 15 однотипных переправочных средств. Поток поступления техники на переправу в среднем составляет 1 ед./мин, среднее время переправы одной единицы техники - 10 мин (с учетом возвращения назад переправочного средства).

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

Решение

Абсолютная пропускная способность , т. е. все, что подходит к переправе, тут же практически переправляется.

Среднее число работающих переправочных средств:

Коэффициенты использования и простоя переправы:

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

Коэффициенты использования переправы после 50 прогонов практически совпадают: .

Енвд