Рассмотрим многоканальную систему массового обслуживания (всего каналов 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 через абсолютную пропускную способность СМО, т.е. А. Величина А – среднее число заявок, которые обслуживаются системой в единицу времени. Один занятый канал обслуживает за единицу времени μ заявок, тогда среднее число занятых каналов

Классификация СМО и их основные характеристики

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

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

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

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

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

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

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

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

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

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

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

"t p 0 (t)+p 1 (t)=1 (9.3).

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

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

(9.4)

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

или (9.5).

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

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

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

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

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

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

СМО с отказами (задача Эрланга)

Рассматривается N-канальная СМО с отказами:

λобслуживания

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

Считаем, что в этой системе имеются следующие потоки событий:

1) поступление заявок на вход СМО из источника заявок G;

2) обслуживание заявок в каналах.

1) интенсивность потока поступающих заявок характеризуется λ

2) интенсивность обслуживания одним каналом:

- мат.ожидание длительности обслуживания

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

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

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

S1 - занят один канал

Sk - заняты k каналов, остальные (n-k) свободны

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

Из состояния Si-1 всегда с интенсивностью входного потока λ система переходит в следующее состояние Si, т.е. в данном случае будет заняе еще один канал и интенсивность перехода в следующее состояние равно интенсивности входного потока λ. Интенсивность обратного перехода возрастает с ростом числа параллельно работающих каналов. Чем больше их работает, тем интенсивнее процесс их освобождения. Для простейших потоков имеем:

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

Пользуясь матрицей Λ запишем уравнения, которые позволяют рассчитать вероятности пребывания системы в каждом из указанных состояний. Распределение вероятностей P0,P1,…,Pn по состояниям S0,…,Sn определяется как решение системы дифференциальных уравнений.

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

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

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

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

Система Эрланга
В качестве показателей эффективности СМО с отказами будем рассматривать:
А - абсолютную пропускную способность СМО, т.е. среднее число заявок, обслуживаемых в единицу времени;
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)