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

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

Многоканальная система массового обслуживания с ограниченной очередью

 

l l … l l l … l l

А₀ А₁ А_k А_k+1 А_k+m-1 А_k+m

m 2m … km km km … km km

 

 

Рис. 6

 

Пусть СМО содержит k каналов, число мест в очереди – m (длина очереди), входящий поток заявок имеет интенсивность l, поток обслуживания заявки одним каналом имеет интенсивность m. Будем нумеровать состояния СМО по числу занятых каналов:

А₀— все каналы свободны; А₁ — один канал занят; ......; A_i - i каналов занято,(k—i) каналов свободны; ......; A_k— все каналы заняты; A_k+1— все каналы заняты, одна заявка в очереди; …; A_k+m— все каналы заняты, m заявок в очереди.

Размеченный граф состояний имеет вид, представленный на рис.6. Сравнивая рисунки 6 и 3, приходим к выводу, что граф на рис. 6 является графом процесса гибели и размножения, для которого:

l_i = l, m_i = m. (18)

Тогда предельное распределение вероятностей состояний можно вычислить по формулам (11). Обозначая через (коэффициент загрузки системы), с учетом соотношений (18) из (11) получим:

p₀ = ;

p₁ = p₀; p₂ = p₀; … ; p_k = p₀; p_k+1 = p₀; … ; p_k+m = p₀. (19)

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

p₀ = (20)

С помощью формул (19), (20) вычисляются показатели эффективности СМО:

А = ( )m = = l(1 – p_k+m); Q = = 1 – p_k+m; P_отк = 1 – Q = p_k+m; (1 – p_k+m); ; (21)

Дляоткрытых СМО справедливы соотношения:

= , = и = . (17)

где l — интенсивность потока заявок, m — интенсивность потока обслуживания. Формулы (17) справедливы только в том случае, когда входящий поток заявок и поток обслужи­вания стационарны.

(Первая и вторая формулы называются формулами Литтла.)

Рассмотрим частные случаи:

1. Многоканальная система массового обслуживания с отказами (задача Эрланга).

Пусть m = 0, т.е. очередь не допускается, если все каналы обслуживания заняты, то заявка покидает СМО. Из формул (20), (21) получим:

p₀ = ;

p₁ = p₀; p₂ = p₀; … ; p_k = p₀. (22)

Формулы (22) называются формуламиЭрланга.

А = l(1 – p_k); Q = 1 – p_k; P_отк = p_k; (1 – p_k); (23)

Задача 4. Диспетчерская служба имеет 5 линий связи. Поток вызовов простейший с интенсивностью l=0,8 вызовов в минуту. Среднее время переговоров с диспетчером состав­ляет t = 3 мин. Время переговоров распределено по показатель­ному закону. Найти 1) абсолютную и относительную пропуск­ные способности диспетчерской службы; 2) вероятность отказа; 3) среднее число занятых каналов. Определить, сколько линий связи должна иметь диспетчерская служба, чтобы вероят­ность отказа не превышала a = 0,01?

Решение. Находим интенсивность потока обслуживания m = 1/ M[T_обсл] = 1/3 разговора в минуту. Коэффициент загрузки СМО составляет r = = = 2,4. Из формул (22) при k = 5 имеем:

p₀= = [10,629]^-1 0,094;

p₅ =
=

Находим по формулам (23):

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

А = l(1—р₅) 0,8 (1—0,062) 0,8.0,938 0,750.

(следовательно, СМО обслуживает в среднем 0,75 заявки в минуту);

б) относительная пропускная способность:

Q = 1 – p₅ = 1 - 062 0,938

 

(следовательно, вероятность обслуживания вновь поступив­шей заявки равна 0,938);

в) вероятность отказа: P_отк=p₅= 0,062;

г) среднее число занятых каналов:

= 2,4.0,938 2,251

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

Поскольку вероятность отказа данной диспетчерской служ­бы p_отк- 0,062 превышает 0,01, то число линий связи следует увеличить. Допустим, что линий связи стало 6. Тогда из фор­мул (22) при k=6

P₀ = [10,629 + 0.265]^-1 0,092;

 

p₆ = 092 = 0,265.0,092 0,024 >0,01.

Следовательно, при k=6 вероятность отказов Р_отк ⁼ Р₆ =0,024 превышает 0,01. Значит, число каналов надо увели­чить. При k=7 получим: p₀ = 0,091; p₇ = 0,008. Следовательно, при k =7 вероятность отказов Р_отк =p₇ = 0,008 не превышает 0,01. Таким образом, для обеспечения требуемой вероятности отказов следует увеличить количество линий связи диспетчерской службы до 7.

Многоканальная система массового обслуживания с неограниченной очередью

Пусть СМО имеет k каналов обслуживания. Все потоки простейшие. Интенсивность потока заявок —l, потока об­служивания одной заявки — m. Коэффициент загрузки СМОr= . Обозначим отношение коэффициента загрузки к числу каналов в системе черезc = . Предельноераспределение вероятностей состояний в описываемой СМО существует толь­ко при c<1. Этот факт можно объяснить, если рас­сматривать данную СМО как предельный случаи многоканаль­ной СМО с ограниченной очередью при стремлении длины очереди к бесконечности. Тогда предельное распределение ве­роятностей состояний можно вычислить как предел при т—>¥ предельных вероятностей (19)- (20). При этом возникает бесконеч­ный числовой ряд, состоящий из членов геометриче­ской прогрессии, который сходится, если знаменатель прогрессии меньше 1, т. е. c<1, и имеет сумму .

Обозначим через p_i предельную вероятность того, что в системе занято i каналов ( 0< i < k+1), а через p_k+r— пре­дельную вероятность того, что в системе заняты все k кана­лов и r заявок стоят в очереди. При c<1 предельное распре­деление вероятностей состояний имеет вид:

p₀ = ;

pi = p₀; (0< i < k+1); p_k+r = p₀; (r > 0). (23)

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

P_отк = 0, Q = 1 – P_отк = 1, A = Q l = l . (24).

Остальные показатели эффективности СМО вычисляются по формулам:

; ; ;

= ; = . (25)

Таблица основных формул для открытых СМО

№	Общий случай (m – число мест в очереди)	Задача Эрланга (m = 0)	Неограниченное число мест в очереди (m = ¥), <1
	p0 = pi = p0;(0< i £k);pk+r= p0;(1£r £m).	p0 = pi = p0;(0< i £ k).	p0 = pi = p0; (0< i £ k); pk+r = p0; (r > 0).
	А = ( )m = = l(1 – pk+m) — среднее число заявок, обслуживаемое СМО в еди­ницу времени. Эту характеристику называютабсолютной пропускной способностью СМО.	А =l(1 – pk)	А =l
	Q = = 1 – pk+m - вероятность обслуживания поступившей заявки или относительная пропускная способность СМО.	Q = 1 – pk	Q = 1
	Pотк = 1 – Q = pk+m — вероятность отказа, т. е. вероятность того, что по­ступившая заявка не будет обслужена	Pотк = pk	Pотк = 0
	(1 – pk+m) — среднее число занятых каналов.	(1 – pk)
	— среднее число заявок в очереди.
	- среднее число заявок в СМО (имеются в виду все заявки, как обслуживаемые, так и ожидающие очереди, ес­ли они есть).	r(1 – pk)	= r +
	= среднее время пребывания заявки в очереди.
	= - среднее время пребывания заявки в СМО, как в очереди, если она есть, так и под обслуживанием.	= (1 – pk)	=

 

Пример. Дисплейный зал имеет k дисплеев. Поток поль­зователей простейший. Среднее число пользователей, посещаю­щих дисплейный зал за сутки, равно п. Время обработки инфор­мации одним пользователем на одном дисплее распределено по показательному закону и составляет в среднем t мин. Определить, существует ли стационарный режим работы зала; вероятность того, что пользователь застанет все дисплеи занятыми ; среднее число пользователей в очереди; среднее время ожидания свобод­ного дисплея ; среднее время пребывания пользователя в дис­плейном зале.

 

Дано: k=2 , n=40, t=34

 

Решение: Рассматриваемая в задаче СМО относится к классу многоканальных систем с неограниченной очередью. Число каналов k=2. Найдем - интенсивность потока заявок: , где - среднее время между двумя последовательными заявками входящего потока пользователей. Тогда . Найдем - интенсивность потока обслуживания: , где - среднее время обслуживания одного пользователя одним дисплеем, тогда . Таким образом, классификатор данной системы имеет вид СМО .

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

Находим это отношение .

Следовательно, стационарный режим существует. Предельное распределение вероятностей состояний вычисляется по формулам:

Поскольку k=2, имеем:

Вычислим - вероятность того, что пользователь застанет все дисплеи занятыми. Очевидно, она равна сумме вероятностей таких событий: все дисплеи заняты, очереди нет (p₂); все дисплеи заняты, один пользователь в очереди (p₃); и так далее. Поскольку для полной группы событий сумма вероятностей этих событий равна единицы, то справедливо равенство .

Найдем эти вероятности:

Используя формулы для вычисления показателей эффективности, найдем:

1) среднее число пользователей в очереди

;

2) среднее число пользователей в дисплейном зале

;

3) среднее время ожидания свободного дисплея

;

4) среднее время пребывания пользователя в дисплейном зале

 

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