МУ ЭММ часть 1

91

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

Различают следующие виды дисциплин обслуживания заявок:

первой пришла – первой обслужена;

последней пришла – первой обслужена;

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

обслуживание с ограниченной длиной очереди;

обслуживание с ограниченным временем пребывания в очереди и

т.д.

Показатели эффективности функционирования систем массового

обслуживания характеризуют ее способность справляться с потоком заявок.

К числу показателей эффективности СМО с отказами относятся:

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

Q – относительная пропускная способность – отношение абсолютной пропускной способности к числу заявок, приходящих в единицу времени;

Ротк – вероятность отказа в обслуживании; Sk – среднее число занятых каналов.

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

Lсист – среднее число заявок в системе; Lm – среднее число заявок в очереди;

Тсист – среднее время ожидания обслуживания.

Понятие марковского случайного процесса. Потоки событий

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

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

92

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

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

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

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

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

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

Название «простейший» объясняется тем, что СМО с простейшими потоками имеет наиболее простое математическое описание.

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

Pm t t m e t m! .

В частности, вероятность того, что за время t не произойдет ни одного события (m = 0), равна P0(t) = e t.

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

Очевидно, что вероятность того, что T будет не меньше t, равна вероятности, что за время t не произойдет ни одного события, т.е.

P(T ≥ t) = P0(t) = e t.

Вероятность Р(Т < t), с одной стороны, представляет собой вероятность противоположного события по отношению к вышеуказанному, а с другой стороны, она – по определению функция распределения F(t) для случайной величины Т.

Таким образом,

F(t) = Р(Т < t) = 1 – P(T ≥ t) = 1 – P0(t) = 1 – e t.

Отсюда следует, что плотность распределения случайной величины Т, равная производной от F(t), определяется по показательному закону

p(t) = F (t) = e t.

93

То есть случайная величина T распределена по показательному

MT 1

закону с параметром и имеет математическое ожидание				и
	DT	1
дисперсию		2
		.

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

в потоке будет меньше, чем t,

P(T < t) = F( t) = 1 – e t t.

Последнее приближенное равенство получаем путем разложения функции e t в ряд Маклорена и отбрасыванием членов второго порядка и выше

e t 1 t t 2 1 t

2! .

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

системой дискретного типа.

Если в такой системе количество возможных состояний счетно, то сумма вероятностей нахождения системы в одном из состояний

pk t 1

k .

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

Случайные процессы со счетным множеством состояний бывают двух типов: с дискретным или непрерывным временем.

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

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

Пример 1. В бюро обслуживания в среднем поступает 12 заявок в час. Считая поток заказов простейшим, определить вероятность того, что:

а) за 1 мин не поступит ни одного заказа; б) за 10 мин поступит не более трех заказов.

94

Решение

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

			12
	Очевидно, эта величина равна		60 = 0,2 заявки в мин.

Далее находим вероятность того, что за время t = 1 мин не поступит ни одной заявки, по формуле

P0( ) = e t = e 0,2 0,819.

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

3		m								0								1
P m 3			e				0,2 10					e 0,2 10					0,2 10		e 0,2 10
		m!
m 0								0!										1!
	0,2 10 2			e 0,2 10					0,2 10 3						e 0,2 10
		2!								3!
e 2 2e 2					4		e 2			8	e 2			19		e 2 0,8571.
										6
				2											3

Пример 2. В ресторан прибывает в среднем 20 посетителей в час.

Считая поток посетителей простейшим и зная, что ресторан открывается в 1100, определить:

а) вероятность того, что в 1112 в ресторане будет 20 посетителей при условии, что в 1107 их было 18;

б) вероятность того, что между 1128 и 1130 в ресторане окажется

новый посетитель, если известно, что предшествующий посетитель прибыл в 1125.

Решение.

а) Для ответа на первый вопрос надо найти вероятность того, что в промежуток от 1107 до 1112 (t = 5 мин) придут два посетителя (m = 20 – 18 = 2).

20 1

При этом известна интенсивность потока посетителей: 60 3 посетителя в минуту. Конечно, данная величина носит условный характер, так как посетители не могут приходить по частям. Искомая вероятность

	1	5	2
					1
	3					5
P 5				e 3
2	2!					0,2623.

95

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

1 P 2 1 e		2
	3			0,4866,
0

где Р0(2) – вероятность того, что в этом промежутке не будет ни одного посетителя.

Уравнения Колмогорова. Предельные вероятности состояний

При анализе случайных процессов с дискретными состояниями используют граф состояний, в котором каждое состояние S0, S1, …, Sn исследуемой системы изображают в виде прямоугольника, а переход из состояния Si в состояние Sj под воздействием простейших потоков событий показывают дугой (стрелкой).

Если около дуг записаны значения интенсивности потоков ij, то граф состояния называют размеченным.

Пусть двухканальная система массового обслуживания может находиться в одном из трех состояний: S0 – оба канала свободны; S1 – один из каналов занят обслуживанием, а другой свободен; S2 – оба канала заняты обслуживанием.

Переходы системы из состояния S0 в состояние S1 и из S1 в S2 происходят под воздействием простейших потоков заявок с интенсивностями 01 и 12 соответственно, а из S1 в S0 и из S2 в S1 – под воздействием потоков обслуживания с интенсивностями 10 и 21.

Тогда размеченный граф состояний СМО имеет вид, изображенный на рис. 30.

01 12

S0

S1

S2

10 21

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

Пребывание СМО в том или ином состоянии носит вероятностный характер.

Обозначим pi(t) вероятность того, что в момент времени t СМО находится в состоянии Si.

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

p0(t) + p1(t) + p2(t) = 1.

Зададим малое приращение времени t и найдем вероятность того,

что СМО в момент времени t + t будет находиться в состоянии S1. Это достигается разными вариантами.

96

1. В момент времени t СМО находилась в состоянии S1. Она могла быть выведена из этого состояния простейшим потоком с суммарной интенсивностью 10 + 12. Как показано выше, вероятность этого приближенно равна

( 10 + 12) t.

Тогда вероятность невыхода из S1 равна

1 – ( 10 + 12) t.

Согласно теореме умножения вероятностей вероятность того, что СМО останется в состоянии S1 в момент t + t, приближенно равна

p1(t)[1 – ( 10 + 12) t].

2. В момент времени t СМО находилась в состоянии S0. Переход СМО из состояния S0 в S1 происходит под воздействием потока с интенсивностью с вероятностью, приближенно равной 01 t.

Тогда вероятность того, что при этом СМО будет находиться в состоянии S1 в момент t + t, в этом варианте приближенно равна

p0(t) 01 t.

3. В момент времени t СМО находилась в состоянии S2. Переход СМО из состояния S2 в S1 происходит под воздействием потока с интенсивностью с вероятностью, приближенно равной 21 t.

Тогда вероятность того, что при этом СМО будет находиться в состоянии S1 в момент t + t, в этом варианте приближенно равна

p2(t) 21 t.

Применяя теорему сложения вероятностей для всех рассмотренных вариантов состояний, можно записать

p1(t + t) p1(t)[1 – ( 10 + 12) t] + p0(t) 01 t + p2(t) 21 t.

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

p1 t t p1 t

t p0(t) 01 + p2(t) 21 – p1(t)( 10 + 12).

При переходе к пределу при t 0 приближенные равенства перейдут в точные и получится дифференциальное уравнение

dp1 t = p0(t) 01 + p2(t) 21 – p1(t)( 10 + 12). dt

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

При записи этих уравнений опустим зависимость вероятностей от времени, которая при этом подразумевается,

97

		dp0		p				p	0				01		,
			dt	1		10
			dp1	p	0		01	p		2				21		p	10	,
			dt													1		12
dp2				p1 12				p2 21.
			dt
																		(1)

Всистеме уравнений (1) для состояния S0 записана первая формула, для S1 – вторая и для S2 – третья.

Вобщем случае система дифференциальных уравнений Колмогорова может быть построена по следующему алгоритму:

в левой части уравнения записывается производная по времени вероятности i-го состояния;

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

Такое дифференциальное уравнение записывается для каждого состояния.

При задании начальных условий можно решить систему дифференциальных уравнений Колмогорова и найти изменение во времени вероятностей состояний pi(t).

Можно показать, что при t эти вероятности независимо от начальных условий стремятся к некоторым предельным значениям,

которые называются предельными или финальными вероятностями

СМО.

В этом случае p1(t) p0, p1(t) p1, p2(t) p2.

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

Так как предельные вероятности не изменяются во времени, то, заменяя в уравнениях Колмогорова (1) производные нулями, получим систему алгебраических уравнений для определения предельных вероятностей. Запишем

p0 01 p1 10,
p				10		12	p			01	p		21	,
	1							0			2
p			21		p			.						(2)
	2				1		12

В системе уравнений (2) обычно при решении второе уравнение заменяют условием нормировки p0 + p1 + p2 = 1.

98

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

Пример 3. Расчетный узел в отделе игрушек детского универмага состоит из двух кассовых аппаратов. Размеченный граф состояний такой СМО имеет вид

01 12

S0

S1

S2

10 21

Найти относительное время пребывания СМО в состояниях: S0 – обе кассы свободны; S1 – одна касса свободна, а другая занята; S2 – обе кассы заняты, если 01 = 60; = 48; 10 = 21 = 36. Здесь размерность интенсивности потоков – покупатели/ч.

Решение. Относительное время пребывания СМО в каждом состоянии равно предельным вероятностям состояний. Составляем систему уравнений

p0 01 p1 10,p2 21 p1 12,

p0 p1 p2 1.

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

	60p						36p ,
						0						1
	36p2						48p1,
	p		0	p						p		2		1,
откуда							1
p		0			36				p			3			p ,
				60						1		5			1
				48								4
p2										p1					p1,
				36								3
	3										4
		p		p									p 1,
	5		1				1				3			1

В итоге находим

					99
p		9	0,204;	p		15	0,341;	p		20	0,455.
		44								44
0				1	44			2

Из полученных результатов можно сделать вывод, что 20,4% рабочего времени обе кассы свободны, 34,1% времени занята одна касса и 45,5% времени заняты обе кассы.

Процесс гибели и размножения

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

Рассматривается многоканальная СМО, которая содержит n каналов и пребывает в состояниях:

S0 – все каналы свободны;

S1 – один канал занят;

S2 – два канала заняты и т.д.

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

	01	12	23		k-1,k	k,k+1		n-1,n
				…			…
	S0	S1	S2		Sk			Sn
	10	21			k,k-1	k+1,k		n,n-1

Рис. 31. Размеченный граф состояний процесса гибели и размножения

Переходы в рассматриваемой системе могут осуществляться из любого состояния только в состояния с соседними номерами, т.е. из состояния Sk возможны переходы только в состояние Sk-1 или в состояние Sk+1.

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

Согласно правилу составления таких уравнений имеем:

для состояния S0: 01p0 = 10p1;

для состояния S1:( 12 + 10)P1 = 01P0 + 21P2;

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

01p0 и 10p1; взаимно уничтожаются, и уравнение для S2 принимает вид

12p1 = 21p2.

Записывая аналогично уравнения для предельных вероятностей других состояний, можно получить следующую систему:

100

01 p0			10 p1						,
		p					p		,
					21			2
	12	1
			p								p		,
				k 1						k,k 1		k
	k 1,k

		p				p
			n 1		n,n 1		n
	n 1,n

к которой добавляется условие нормировки p0 + p1 + … + pn = 1

Решая полученную систему уравнений, можно получить

							01				12 01					n 1,n 12					01	1
	p 1																						;			(3)
	0						10				21 10
																n,n 1 21 10
p		01		p		;	p				12 01			p			; p	n		n 1,n 12 01				p		.
1			10		0			2							0						n,n 1				0
												21 10											21 10

Пример 4. Решить предыдущий пример, используя теорию процесса гибели и размножения.

Решение. В условии предыдущего примера размеченный граф состояний имеет вид

																							S0						01							12		S2
																													10						S1
																																				21
Подставляя данные в формулы (3), получаем
								01						12					01					1									60 48 60				1		5 4 5				1
p	0		1																							1												1
							10																										36 36 36						3 3 3
													21 10
						35 1									44							1						9
			1																												0,204;
																												44
							9								9
p			01			p						60					9								15				0,341;
												36
1						0												44				44
			10
p	2			12 01						p		0				48							60					9				20		0,455.
															36																	44
																						36				44
			21			10

Выводы относительно этого примера аналогичны пердыдущему.