Исследование операций / ИСО Учебник

S12 — первый узел исправен, второй — в ремонте;

S22 — оба узла в ремонте.

Граф состояний в таком случае будет иметь вид, изображенный на рис. 2.10

S11

λ λ

	λ1		λ2
S21				S12
	λ2		λ1
				λ
λ
		S22

Рис. 2.10. Граф состояний системы S

Система уравнений Колмогорова, соответствующая графу на рис. 2.10, имеет вид

p11 = −(λ1 + λ2 )p11 + λ(p21 + p12 ), p21 = −(λ + λ2 )p21 + λ1 p11 + λp22 , p12 = −(λ + λ1 )p12 + λ2 p11 + λp22 , p22 = −2λp22 + λ1 p12 + λ2 p21.

Начальные условия: p11(t=0) = 1, p12(t=0)= p21(t=0)= p22(t=0)= 0.

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

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

1)задачи анализа поведения системы;

2)статистические задачи;

3)операционные задачи.

141

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

Задачи анализа поведения системы

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

—длина очереди в момент времени t, т. е. число требований, находящихся в системе в момент времени t;

—длина очереди на n стадии; при этом предполагается, что стадии реализуются в дискретном режиме и определяются теми или иными событиями (например, поступлением требования в систему или выбытием требования из нее);

—виртуальная продолжительность ожидания относительно момента времени t, т. е. время ожидания обслуживания для требования, которое поступит в систему в момент времени t;

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

—продолжительность периода занятости системы, начало которого соответствует t=0 i, т. е. длина периода занятости системы, начинающегося при наличии в системе i требований.

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

142

ное время (доля времени, в течение которого обслуживающий механизм находится в состоянии загруженности).

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

ρ =	интенсивность поступления требований	=	λ .	(2.30)
	интенсивность обслуживания		μ

Статистические задачи

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

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

143

, где tобсл = M [Tобсл ]. Если все

Операционные задачи

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

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

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

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

ная среднему времени обслуживания: μ = 1

tобсл

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

144

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

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

Среди показателей первой группы можно выделить следующие:

1)среднее число заявок A, обслуживаемое СМО в единицу времени,

или абсолютная пропускная способность СМО;

2)вероятность обслуживания поступившей заявки Q или относитель-

ная пропускная способность СМО, Q = λA ;

3)вероятность отказа Ротк, т. е. вероятность того, что поступившая заявка не будет обслужена, получит отказ, Pотк =1 − Q ;

4)среднее число заявок в СМО (обслуживаемых или ожидающих в очереди) z ;

5)среднее число заявок в очереди r ;

6)среднее время пребывания заявки в СМО (в очереди или под обслу-

живанием) tсист ;

7)среднее время пребывания заявки в очереди tоч ;

8)среднее число занятых каналов k .

Рассмотрим далее основные виды СМО.

145

Лекция 2.2.5. Многоканальные СМО: многоканальные и одноканальные системы массового обслуживания

Многоканальная система массового обслуживания S состоит из n каналов. На вход системы поступают заявки, при этом интенсивность входящего потока равна λ. Заявка, попадающая в систему S, начинает обслуживаться, интенсивность потока обслуживания равна μ. Если все каналы заняты обслуживанием заявок, вновь пришедшая заявка отклоняется. В этом случае СМО имеет n+1 состояние:

S0 — система свободна,

S1 — один канал занят,

S2 — два канала заняты, …,

Sn — все каналы системы заняты обслуживанием заявок, поступивших в систему.

Графически данную СМО можно представить в виде графа состояний

(рис. 2.11).

		λ		λ		λ		λ
	S0		S1		S2		…		Sn
		μ		2μ		3μ		nμ

Рис. 2.11. Размеченный граф состояний многоканальной СМО с отказами

Приведенная интенсивность потока заявок

ρ = λμ .

Финальные вероятности состояний

	n	ρ	i −1				ρ	k
p0	= ∑				, pk	=			p0 , k = 1, 2, …n.
							k!
	i=0	i!

146

Вероятность отказа

	pотк = pn =	ρn	p0 .
		n!

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

q = 1 – pотк = 1 – pn.

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

A = λ q = λ (1 – pn).

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

	~		A		λ	n
	k	=		=		(1 − pn )= ∑i pi .
			μ		μ
						i=1

Среднее число заявок в системе

~ = ~ + ~ = ~ zs r k k .

Среднее время обслуживания

~

~ = k

tобс λ .

Пример. Имеется мини-АТС с тремя телефонами. Если все телефоны (каналы) заняты, то внешний звонок отклоняется. Среднее время обслужи-

вания одной заявки каналом μ равно двум минутам. Поток заявок простей-

ший с интенсивностью λ =1,5 заявмин.. . Составить граф состояний. Найти

финальные вероятности состояний и основные характеристики эффективности СМО.

Решение. Данная СМО будет иметь четыре состояния:

S0 — все три канала связи свободны,

147

S1 — два канала связи свободны, а один — занят,

S2 — один канал связи свободен, а два — заняты, S3 — все три канала связи заняты.

Поскольку среднее время обслуживания одной заявки каналом равно 2 минутам, то

1			1		заяв.
μ =	~	=	2	= 0,5	.
	tобсл.				мин.

Граф состояний изображен на рис. 2.12.

	λ =1,5		λ =1,5		λ =1,5
S0	μ = 0,5	S1	2μ =1	S2		S3
					3μ =1,5

Рис. 2.12

Вычислим основные показатели СМО.

Финальные вероятности системы:

p

= 1

+

ρ

+

ρ2

+

ρ3

−1,

p =

ρi

p

, i =1, 2, 3,

0

0

1!

2!

i

i!

3!

ρ =

λ

~

=1,5 2 = 3 .

μ

= λ tобсл.

р0 =

1

;

р1 =

3

;

р2

=

9

; р3

=

9

.

13

13

26

26

Вероятность отказа pотк.

=

ρ3

p0

=

9

.

26

3!

Вероятность обслуживания q = 1 – pотк

=

17 .

26

Абсолютная пропускная способность A = λ q =1,5

17

≈ 0,981.

26

~

A

Среднее число занятых каналов k = μ =1,96 .

148

~	~		1,96
	k
Среднее время пребывания заявки в системе tсис =	λ	=	1,5	=1,3(мин).

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

Многоканальная система массового обслуживания S имеет n каналов и m мест в очереди. На вход системы поступают заявки, при этом интенсивность входящего потока равна λ. Заявка, попадающая в систему S, начинает обслуживаться, интенсивность потока обслуживания равна μ. Если все каналы заняты обслуживанием заявок, вновь пришедшая заявка ставится в очередь ожидания обслуживания заявок. Если все места в очереди заняты, то вновь пришедшая заявка отклоняется. В этом случае СМО имеет n+m+1 состояние:

S0 — система свободна;

S1 — один канал занят, очереди нет;

S2 — два канала заняты, очереди нет; …;

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

Sn+1 — все каналы системы заняты и занято одно место в очереди; Sn+2 — все каналы системы заняты и заняты два места в очереди

…;

Sn+m — все каналы системы и места в очереди заняты.

Графически СМО можно представить следующим образом (рис. 2.13).

λ

λ

λ

… λ

λ

λ

… λ

S0

S1

S2

Sn

Sn+1

Sn+2

Sn+m

μ

2μ

3μ

nμ

nμ

nμ

nμ

nμ

Рис. 2.13. Размеченный граф состояний многоканальной СМО с ограниченною очередью

149

Приведенная интенсивность потока заявок

ρ = λμ .

Финальные вероятности состояний

	n	i		n+m	i			−1
p0	= ∑	ρ	+	∑	ρ			,
		i!			i	−n
	i=0			i=n+1 n!n

Для случая ω = ρn <1 формула финальной вероятности упрощается:

n

ρ

i

ρ

n+1

1 −ω

m

−1

p0

= ∑

+

,

i!

n!n

1- ω

i=0

ρk

ρn+k

pk =

p0 , k =1,n ,

pn+k =

p0 , 1 ≤ k ≤ m .

k!

n!nk

Вероятность отказа

ρm+n

pотк = pn+m = nm n! p0 .

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

q = 1 – pотк.

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

A = λ q = λ (1 – pn+m).

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

	~		A	= ρ(1	− pn+m ).
	k	=
			μ

Среднее число заявок в очереди (ω = ρn <1)

~		p0 ρn+1 1 − (m +1) ωm + mωm+1
r	=		(1 −ω)2	.
		n n!

150