Как найти характеристики смо - Исправление недочетов и поиск решений вместе с Examum.ru

Теория массового обслуживания (СМО)

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

Сервис представлен тремя онлайн-калькуляторами:

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

Для решения задач на тему Теория массового обслуживания необходимо определиться с типом модели СМО: одноканальные (см. примеры задач для одноканальных СМО) или многоканальные (см. примеры задач для многоканальных СМО). В многоканальных СМО количество устройств обслуживания n (количество рабочих, кассиров, бригад, моек и т.п.) больше одного. Обычно интенсивность потока заявок λ задана явно. Интенсивность потока обслуживания μ может задаваться в виде времени обслуживания t_обс.
В сервисе необходимо ввести либо параметр μ, либо t_обс (только одно из двух).

Выбор СМО зависит как от числа каналов n, так и от допустимой длины очереди m. По указанным признакам различается ряд типов СО, перечисленных в таблице.

№ п/п	Параметры СО	Тип СО
n	m
1	1	0	Одноканальная, без очереди
2	n > 1	0	Многоканальная, без очереди
3	1	1 < m <∞	Одноканальная, с ограниченной очередью
4	n > 1	1 < m<∞	Многоканальная, с ограниченной очередью
5	1	m = ∞	Одноканальная, с неограниченной очередью
6	n > 1	m = ∞	Многоканальная, с неограниченной очередью

По числу обслуживающих каналов различают одноканальные и многоканальные СО.

В зависимости от целочисленного значения m используются следующие названия в классификации типов СО:

m = 0 – без очереди;
m > 0 – с очередью.

Если число мест в очереди m является конечным, то в СО могут происходить отказы в предоставлении обслуживания некоторым заявкам. В связи с этим СО указанного типа называются системами с отказами. Отклоняются от обслуживания те заявки, в момент прихода которых все места в очереди случайно оказались занятыми, или, если m =0, все каналы оказались занятыми. Считается, что заявка, получившая отказ в обслуживании, навсегда теряется для СО. Таким образом, пропускная способность СО этого типа всегда меньше 100%.

Если m не ограничено, что иногда условно записывают как m = ∞ , то соответствующая СО называется системой с ожиданием. В СО данного типа пришедшая заявка при отсутствии возможности немедленного обслуживания ожидает обслуживания, какой бы длинной ни были очередь и продолжительность времени ожидания.

Все СМО делятся на СМО с отказами (параметр m не используется), СМО с ограниченной длиной очереди и СМО с неограниченной очередью. Параметр m (длина очереди) используется для последних двух СМО. При этом в СМО с неограниченной очередью можно указывать любое значение m. Например, m = 3. Тогда будут рассчитаны вероятности нахождения в очереди 1,2,3 заявки.

Временные параметры рассчитываются в часах или в минутах, в зависимости от заданного параметра λ.

Полученное решение сохраняется в файле Word. Для редактирования формул можно использовать редактор формул Microsoft Equation.

Перейти к онлайн решению своей задачи

Решение
Видео решение

Интернет-провайдер в небольшом городе имеет 5 выделенных каналов обслуживания. В среднем на обслуживание одного клиента уходит 25 минут. В систему в среднем поступает 6 заказов в час. Если свободных каналов нет, следует отказ. Определить характеристики обслуживания: вероятность отказа, среднее число занятых обслуживанием линий связи, абсолютную и относительную пропускные способности, вероятность обслуживания. Найти число выделенных каналов, при котором относительная пропускная способность системы будет не менее 0,95. Считать, что потоки заявок и обслуживаний простейшие.

Формулы для расчета параметров простейших СМО

, , , a = , b = , γ =

Показатели эффективности системы	Чистая СМО с отказами (n, a)	СМО с ограничением на время пребывания в очереди (n, a,b)	СМО с ограничением на длину очереди (n, a,m)	Чистая СМО с ожиданием (n, a), γ < 1
1	2	3	4	5
Вероятность того, что все каналы свободны	р₀ =	р₀=	p₀=	р₀ =
Вероятность того, что занято k каналов 0 ≤ k≤ n	Р_k = р₀	Р_k= р₀	р_k= р₀	Р_k = р₀
Вероятность того, что заняты все `n` каналов, `s` заявок в очереди	—	р_n+s = р_n,	р_n_+s= γ^s× р_n; 1 ≤ s ≤ `m`.	р_n+_s=γ^s× р_n
Вероятность отказа	р_отк = р_n	р_отк =	р_отк = р_n+m	р_отк = 0
Вероятность полной загрузки системы	р_n.з = р_n	р_n.з =	р_n.з = р_n	р_n_.з =
Вероятность обслуживания, относительная пропускная способность системы	р_обс = = 1- р_n=	р_обс = = 1 — р_отк =	р_обс = = = 1 — р_n+m =	р_обс = = 1
Абсолютная пропускная способность системы	`l_b = l·р_обс`	`l_b = l·р_обс = l — n·r`	l_b = lр_обс = m × n₃	l_b = l
Вероятность занятости канала	р_зк = k_з =	р_зк = k_з =	р_зк = k_з =	р_зк = k_з =
Среднее число свободных каналов	n₀ =	n₀ =	n₀ =	n₀ =
Вероятность простоя канала p_п.к, коэффициент простоя оборудования к_n	р_n.к = k_n =	р_n.к = k_n =	р_n.к = k_n =	р_n.к = k_n =
1	2	3	4	5
Среднее число заявок в очереди	—	r =	r =	r = р_n
Вероятность наличия очереди	—	р_н.о =	р_н.о = р_n	р_н_.о =p_n
Среднее время наличия очереди	—	—	=	=
Среднее время пребывания заявки в очереди	—	=	=	=
Среднее время пребывания заявки в системе	=	= , `l = n₃ + r`	= , `l = n₃ + r`	= , `l = n₃ + r`
Среднее время занятости канала (любого)	=		= +	=
Среднее время простоя канала
Среднее время полной загрузки системы		—
Среднее время неполной загрузки системы		–

Источник

Окончание табл. 8.2

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

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

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

Основные параметры каналов обслуживания – количество каналов (m), среднее время обслуживания заявки в канале ( x ). В расчетах вместо величины x часто используется интенсивность обслуживания заявок μ =1/ x . Эта величина представляет собой среднее количество заявок, которое может быть обслу98

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

Параметром СМО с ограничением на количество заявок в очереди является также максимальное (предельно допустимое) количество заявок в очере-

ди (n).

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

P0 – вероятность простоя СМО. Эта величина показывает, какую часть от общего времени работы СМО все ее каналы свободны, т.е. простаивают из-за отсутствия заявок;

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

Pотк=0;

Pобсл – вероятность обслуживания. Эта величина показывает, какая доля всех поступающих заявок обслуживается системой. Очевидно, что Pобсл=

=1-Pотк. Для СМО без отказов Pобсл=1;

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

q — среднее число заявок в очереди (средняя длина очереди);

S — среднее число заявок на обслуживании (в каналах), или среднее число занятых каналов;

k — среднее число заявок в СМО, т.е. на обслуживании и в очереди;

w — среднее время пребывания заявки в очереди (среднее время ожидания обслуживания);

t — среднее время пребывания заявки в СМО, т.е. в очереди и на обслуживании;

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

вединицу времени).

Величины P0, U и S характеризуют степень загрузки СМО. Эти величины представляют интерес с точки зрения стороны, осуществляющей эксплуатацию СМО. Например, если в качестве СМО рассматривается предприятие, выполняющее некоторые заказы, то эти величины представляют интерес для владельцев предприятия. Обычно желательно, чтобы коэффициент загрузки СМО имел значение на уровне 0,75 – 0,85. Значения U<0,75 указывают, что СМО простаивает значительную часть времени, т.е. используется нерационально. Значения U>0,85 указывают на перегрузку СМО.

Величины Pотк, Pобсл, w и t характеризуют качество обслуживания заявок. Они представляют интерес с точки зрения пользователей СМО. Желатель-

на минимизация значений Pотк, w , t и максимизация Pобсл.

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

Величины q и k обычно используются в качестве вспомогательных для

расчета других характеристик СМО.

При расчете характеристик СМО используется следующая величина, на-

зываемая нагрузкой на СМО:

ρ =	λ	.	(8.3)

	mμ

Величина ρ представляет собой отношение интенсивности потока заявок к интенсивности, с которой СМО может их обслуживать. Любая СМО без ограничений на очередь может нормально работать (т.е. обслуживать все поступающие заявки) только при условии, что ρ<1. Величина ρ>1 означает, что количество заявок, поступающих в СМО в единицу времени (λ), превышает количество заявок, которые СМО может обслужить в единицу времени (mμ). В таких условиях в СМО без ограничений на очередь количество заявок, ожидающих обслуживания, будет постоянно возрастать, так как заявки будут поступать в СМО быстрее, чем она может их обслуживать. Для СМО с ограничениями на очередь и без очереди возможны любые значения ρ, так как в таких СМО часть заявок получает отказ, т.е. не допускается в СМО.

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

Коэффициент загрузки:

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


				= mU .	(8.5)
S
Среднее число заявок в СМО:
		= q +		.	(8.6)
k	S
Пропускная способность СМО:
γ =μ		,	(8.7)
S
или
γ=λ(1-Pотк).	(8.8)

100

Среднее время пребывания заявки в очереди (формула Литтла):
w =	q	.	(8.9)

					γ
Среднее время пребывания заявки в СМО:
		= w + x ,	(8.10)
t
или
			k
t	=			.	(8.11)

			γ

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

Для разомкнутых СМО без ограничений на очередь верны следующие формулы:

•коэффициент загрузки: U=ρ;

•пропускная способность: γ=λ.

Эти формулы представляют собой частные случаи формул (8.4) и (8.8) для Pотк=0.

Вероятность простоя (P0), вероятность отказа (Pотк) и средняя длина очереди ( q ) рассчитываются по-разному в зависимости от типа СМО.

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

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

8.5. Вероятности состояний СМО

Вероятности состояний СМО — это вероятности пребывания в СМО определенного количества заявок. Обычно при вычислении вероятностей состояний

требуется определять величины Pj — вероятности пребывания в СМО ровно j заявок. Например, P2 – вероятность того, что в СМО (т.е. на обслуживании и в

очереди) находятся ровно две заявки. Если, например, P2=0,15, это означает, что в течение 15% времени (от всего времени работы СМО) в ней находятся ровно две заявки. В течение остального времени (85%) количество заявок в СМО составляет менее двух (одну или ни одной) или более двух (три или больше).

101

Соседние файлы в предмете Системный анализ

#
#
#
#
15.06.201428.16 Кб106Лаба 1 Принятие решений в условия риска и неопределённости.xls
#
15.06.201413.78 Кб64Лаба 2 Анализ и оптимизация решений на основе эконометрических моделей.xlsx
#
#

Источник

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

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

Классификация
СМО по способу обработки входного потока заявок.

Классификация
по способу функционирования:

1.
открытыми, т.е. поток заявок не зависит от
внутреннего состояния СМО;

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

Классификация систем массового обслуживания

Первое деление (по
наличию очередей):

1.
СМО с отказами;

2.
СМО с очередью.

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

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

СМО с очередями
подразделяются на разные виды в зависимости от того, как организована
очередь – ограничена или не ограничена. Ограничения могут касаться как
длины очереди, так и времени ожидания, «дисциплины обслуживания».

·
СМО с нетерпеливыми заявками (длина очереди и время обслуживания
ограничено);

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

Кроме этого СМО делятся
на открытые СМО и замкнутые СМО.

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

Одноканальная система массового обслуживания с отказами

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

Рисунок 1 –
Граф состояний одноканальной СМО

Здесь и –
интенсивность потока заявок и выполнения заявок соответственно. Состояние
системы S_o обозначает,
что канал свободен, а S₁ – что канал занят
обслуживанием заявки.

Система дифференциальных уравнений Колмогорова для такой СМО имеет
вид:

где p_o(t) и p₁(t) –
вероятности нахождения СМО в состояниях So и S1 соответственно. Уравнения для финальных вероятностей p_o и p₁ получим, приравнивая нулю производные в первых двух уравнениях
системы. В результате получим:

(1)

(2)

Вероятность p₀ по своему смыслу есть
вероятность обслуживания заявки p_обс, т. к. канал
является свободным, а вероятность р₁ по своему смыслу является
вероятностью отказа в обслуживании поступающей в СМО заявки р_отк,
т. к. канал занят обслуживанием предыдущей заявки.

Многоканальная система
массового обслуживания с отказами

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

Рисунок 2 – Граф состояний многоканальной СМО с отказами

Состояние S₀ означает, что все каналы
свободны, состояние S_k (k = 1, n) означает, что обслуживанием заявок заняты k каналов. Переход из одного
состояния в другое соседнее правое происходит скачкообразно под воздействием
входящего потока заявок интенсивностью независимо
от числа работающих каналов (верхние стрелки). Для перехода системы из одного состояния
в соседнее левое неважно, какой именно канал освободится. Величина характеризует интенсивность обслуживания
заявок при работе в СМО k каналов (нижние стрелки).

(4)

(5)

Формулы (4) и (5) называются формулами Эрланга – основателя теории
массового обслуживания.

Вероятность отказа в обслуживании заявки р_отк равна
вероятности того, что все каналы заняты, т.е. система находится в состоянии S_n. Таким
образом,

(6)

Относительную пропускную способность СМО:

(7)

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

Так как каждый занятый канал в единицу времени обслуживает в
среднем заявок, то можно
найти по формуле:

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

В СМО с ограниченной очередью число мест m в очереди ограничено.
Следовательно, заявка, поступившая в момент времени, когда все места в очереди
заняты, отклоняется и покидает СМО. Граф такой СМО представлен на рисунке 3.

Рисунок 3 –
Граф состояний одноканальной СМО с ограниченной очередью

Состояния СМО представляются следующим образом:

S₀ – канал обслуживания свободен,

S₁ – канал обслуживания занят, но очереди нет,

S₂ – канал обслуживания занят, в очереди одна заявка,

S_k₊₁ – канал обслуживания занят, в очереди k заявок,

S_m₊₁ – канал обслуживания занят, все m мест в очереди заняты.

Для получения необходимых формул можно воспользоваться тем
обстоятельством, что СМО на рисунок 3 является частным случаем системы рождения
и гибели, если принять и

(8)

(9)

(10)

Поступившая в СМО заявка получает отказ в обслуживании, если СМО
находится в состоянии S_m₊₁, т.е. вероятность отказа
в обслуживании заявки равна:

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

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

Среднее число заявок, стоящих в очереди L_оч, находится по формуле

и может быть записано в виде:

(11)

При формула (11) принимает вид:

– среднее число заявок, находящихся в
СМО, находится по формуле:

и может быть записано в виде:

(12)

При , из (12) получим:

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

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

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

Рисунок 4 –
Граф состояний одноканальной СМО с неограниченной очередью

Рассмотрим случай, когда .

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

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

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

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

Среднее число заявок, находящихся в СМО:

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

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

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

Граф такой системы представлен на рисунке 5.

Рисунок 5 – Граф состояний многоканальной СМО с ограниченной очередью

– все
каналы свободны, очереди нет;

–
заняты l каналов (l = 1, n), очереди нет;

—
заняты все n
каналов, в очереди находится i заявок (i = 1, m).

Выражения для финальных вероятностей:

(13)

Образование
очереди происходит, когда в момент поступления в СМО очередной заявки все
каналы заняты, т.е. в системе находятся либо n, либо (n+1),…, либо (n + m – 1) заявок. Т.к. эти события несовместны, то вероятность
образования очереди p_оч равна сумме соответствующих
вероятностей :

(14)

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

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

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

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

(15)

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

Среднее число
заявок, находящихся в СМО:

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

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

Граф такой СМО изображен на рисунке 6 при .

Рисунок 6 – Граф состояний многоканальной СМО с неограниченной
очередью

Формулы для остальных вероятностей имеют тот же вид, что и для СМО
с ограниченной очередью:

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

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

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

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

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

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

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

Рисунок 7 – Граф многоканальной СМО с ограниченной очередью и
ограниченным временем ожидания в очереди

Выражения для финальных вероятностей

где . Вероятность образования
очереди определяется формулой:

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

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

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

Среднее число заявок, находящихся в очереди находится по формуле

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

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

Системы
массового обслуживания с ожиданием

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

Рассмотрим простейшую СМО с ожиданием — одноканальную систему (n —
1), в которую поступает поток заявок с интенсивностью ; интенсивность
обслуживания (т.е. в среднем
непрерывно занятый канал будет выдавать обслуженных заявок в
единицу (времени). Заявка, поступившая в момент, когда канал занят, становится
в очередь и ожидает обслуживания.

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

— канал свободен;

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

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

— канал занят, k-1 заявок стоят в очереди;

— канал занят, т-заявок стоят в очереди.

ГСП показан на рис. 8. Все интенсивности потоков событий,
переводящих в систему по стрелкам слева направо, равны , а справа налево — . Действительно, по
стрелкам слева направо систему переводит поток заявок (как только придет
заявка, система переходит в следующее состояние), справа же налево — поток
«освобождений» занятого канала, имеющий интенсивность (как только будет
обслужена очередная заявка, канал либо освободится, либо уменьшится число
заявок в очереди).

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

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

(21).

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

(22).

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

Средняя длина очереди.

С вероятностьюв очереди стоит одна
заявка, с вероятностью— две заявки, вообще с
вероятностьюв очереди стоят k-1
заявок, и т.д., откуда:

(23).

Поскольку , сумму в (23) можно
трактовать как производную по от суммы геометрической
прогрессии:

Подставляя данное выражение в (23) и используя из (20), окончательно
получаем:

(24).

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

(25).

Среднее время ожидания заявки в очереди.

если подставить сюда выражения для вероятностей (20), получим:

(26).

(27).

Среднее время пребывания заявки в системе. .

Отсюда:

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

Площадка при станции допускает пребывание в очереди на заправку не
более трех машин одновременно (m = 3). Если в очереди уже находятся три машины,
очередная машина, прибывшая к станции, в очередь не становится. Поток машин,
прибывающих для заправки, имеет интенсивность =1 (машина в минуту).
Процесс заправки продолжается в среднем 1,25 мин.

Определить:

вероятность отказа;

относительную и абсолютную пропускную способности АЗС;

среднее число машин, ожидающих заправки;

среднее число машин, находящихся на АЗС (включая обслуживаемую);

среднее время ожидания машины в очереди;

среднее время пребывания машины на АЗС (включая обслуживание).

Иначе говоря, среднее время ожидания равно среднему числу заявок в
очереди, деленному на интенсивность потока заявок.

Системы с неограниченным ожиданием.

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

При отсутствии ограничений по длине очереди каждая заявка,
пришедшая в систему, будет обслужена, поэтому q=1, .

Среднее число заявок в очереди получим из (24) при :

Среднее число заявок в системе по формуле (25) при :

Среднее время ожиданияполучим из формулы (26)
при:

Наконец, среднее время пребывания заявки в СМО есть:

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

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

Состояния системы нумеруются по числу заявок, связанных системой:

нет очереди:

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

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

— заняты -каналов, остальные нет;

— заняты все -каналов, свободных нет;

есть очередь:

— заняты все n-каналов; одна заявка стоит в очереди;

— заняты все n-каналов, r-заявок в очереди;

— заняты все n-каналов, r-заявок в очереди.

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

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

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

(29)

Относительная пропускная способность дополняет вероятность отказа
до единицы:

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

(30)

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

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

(31)

где .

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

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

Среднее время ожидания заявки в очереди.

(32)

Так же, как и в случае одноканальной СМО с ожиданием, отметим, что
это выражение отличается от выражения для средней длины очереди только
множителем , т. е.

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

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

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

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

Среднее число заявок в очереди получим при из (31):

а среднее время ожидания — из (32): .

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

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

Пример 2.
Автозаправочная станция с двумя колонками (n = 2) обслуживает поток машин с
интенсивностью =0,8 (машин в минуту).
Среднее время обслуживания одной машины:

В данном районе нет другой АЗС, так что очередь машин перед АЗС
может расти практически неограниченно. Найти характеристики СМО.

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

Рассмотрим СМО подобного типа, предполагая, что ограничение
времени ожидания является случайной величиной.

Пуассоновский «поток уходов» с интенсивностью:

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

нет очереди:

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

— занят один канал;

— заняты два канала;

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

есть очередь:

— заняты все n-каналов, одна заявка стоит в очереди;

— заняты все n-каналов, r-заявок стоят в очереди и т. д.

Граф состояний и переходов системы показан на рис. 10.

Рис. 10. СМО с ограниченным
временем ожидания

Разметим этот граф, как и раньше; у всех стрелок, ведущих слева
направо, будет стоять интенсивность потока заявок . Для состояний без
очереди у стрелок, ведущих из них справа налево, будет, как и раньше, стоять
суммарная интенсивность потока обслуживании всех занятых каналов. Что касается
состояний с очередью, то у стрелок, ведущих из них справа налево, будет стоять
суммарная интенсивность потока обслуживания всех n-каналов плюс соответствующая
интенсивность потока уходов из очереди. Если в очереди стоят r-заявок, то
суммарная интенсивность потока уходов будет равна .

Среднее число заявок в очереди: (35)

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

Среднее число занятых каналов по-прежнему получаем,
деля абсолютную пропускную способность А на : (36)

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

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

Замкнутые
СМО

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

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

Пусть n — число каналов обслуживания, s — число
потенциальных заявок, n<s, — интенсивность потока
заявок каждого потенциального требования, μ — интенсивность обслуживания:

ρ=.

Вероятность простоя системы определяется формулой

Р₀=.

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

P_k= при k<n,
P_k= при .

Через эти вероятности выражается среднее число занятых каналов

=P₁+2P₂+…+n(P_n+P_n+₁+…+P_s)
или

=P₁+2P₂+…+(n-1)P_n-₁+n(1-P₀-P₁-…-P_n-1).

Через находим абсолютную пропускную способность
системы:

A=,

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

М=s—=s—.

Пример 1. На вход трехканальной СМО с отказами поступает поток заявок с
интенсивностью =4 заявки в минуту, время обслуживания
заявки одним каналом t_обсл=1/μ =0,5 мин. Выгодно ли с точки
зрения пропускной способности СМО заставить все три канала обслуживать заявки
сразу, причем среднее время обслуживания уменьшается втрое? Как это скажется на
среднем времени пребывания заявки в СМО?

Пример 2. На вход трехканальной СМО с неограниченной очередью поступает
поток заявок с интенсивностью =4 заявки в час, среднее время
обслуживания одной заявки t=1/μ=0,5 ч. Найти показатели эффективности
работы системы.

Для рассматриваемой системы n=3, =4,
μ=1/0,5=2, ρ=/μ=2, ρ/n=2/3<1.

Задача 3:

Два рабочих обслуживают
группу из четырех станков. Остановки работающего станка происходят в среднем
через 30 мин. Среднее время наладки составляет 15 мин. Время работы и время
наладки распределено по экспоненциальному закону.

Найдите среднюю долю
свободного времени для каждого рабочего и среднее время работы станка.

Найдите те же
характеристики для системы, в которой:

а) за каждым рабочим
закреплены два станка;

б) два рабочих всегда
обслуживают станок вместе, причем с двойной интенсивностью;

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

Источник

СМО с ожиданием (очередью): определение и формулы

В качестве показателей эффективности СМО с ожиданием, кроме уже известных показателей — абсолютной и относительной пропускной способности, вероятности отказа $P_{text{otk}}$ , среднего числа занятых каналов к (для многоканальной системы) будем рассматривать также следующие:

1) $L_{text{sist.}}$ — среднее число заявок в системе;

2) $T_{text{sist.}}$ — среднее время пребывания заявки в системе;

3) $L_{text{och.}}$ — среднее число заявок в очереди (длина очереди);

4) $T_{text{och.}}$ — среднее время пребывания заявки в очереди;

5) $P_{text{zan.}}$ — вероятность того, что канал занят (степень загрузки канала).

Одноканальная система с неограниченной очередью

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

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

Система может находиться в одном из состояний S_0,S_1,S_2,ldots,S_k , по числу заявок, находящихся в СМО: S_0 — канал свободен; S_1 — канал занят (обслуживает заявку), очереди нет; S_2 — канал занят, одна заявка стоит в очереди; — канал занят, (k-1) заявок стоят в очереди и т.д.

Граф состояний СМО представлен на рис. 8.

Граф состояний одноканальной СМО с неограниченной очередью

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

Прежде чем записать формулы предельных вероятностей, необходимо быть уверенным в их существовании, ведь в случае, когда время ttoinfty , очередь может неограниченно возрастать. Доказано, что если rho<1 , т.е. среднее число приходящих заявок меньше среднего числа обслуженных заявок (в единицу времени), то предельные вероятности существуют. Если rhogeqslant1 , очередь растет до бесконечности.

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

$p_0=left[1+ frac{lambda}{mu}+ left(frac{lambda}{mu}right)^{2}+ldots+ left(frac{lambda}{mu}right)^{k}+ldotsright]^{-1}= left(1+rho+rho^2+ldots+rho^k+ldotsright)^{-1}.$

(32)

Так как предельные вероятности существуют лишь при rho<1 , то геометрический ряд со знаменателем rho<1 , записанный в скобках в формуле (32), сходится к сумме, равной $frac{1}{1-rho}$ . Поэтому

p_0=1-rho,

(33}

и с учетом соотношений (17)

p_1=rhocdot p_0,quad p_2=rho^2cdot p_0,quadldots,quad p_k=rho^kcdot p_0,quadldots

найдем предельные вероятности других состояний

p_1=rho(1-rho),quad p_2=rho^2(1-rho),quadldots,quad p_k=rho^k(1-rho),quad ldots

(34)

Предельные вероятности p_0,p_1,p_2,ldots,p_k,ldots образуют убывающую геометрическую профессию со знаменателем rho<1 , следовательно, вероятность p_0 — наибольшая. Это означает, что если СМО справляется с потоком заявок (при rho<1 ), то наиболее вероятным будет отсутствие заявок в системе.

Среднее число заявок в системе $L_{text{sist.}}$ определим по формуле математического ожидания, которая с учетом (34) примет вид

$L_{text{sist.}}= sum_{k=1}^{infty}kp_k=(1-rho)sum_{k=1}^{infty}krho^k$

(35)

(суммирование от 1 до infty , так как нулевой член 0cdot p_0=0 ).

Можно показать, что формула (35) преобразуется (при rho<1 ) к виду

$L_{text{sist.}}=frac{rho}{1-rho},.$

(36)

Найдем среднее число заявок в очереди $L_{text{och.}}$ . Очевидно, что

$L_{text{och.}}= L_{text{sist.}}- L_{text{ob.}},$

(37)

где $L_{text{ob.}}$ — среднее число заявок, находящихся под обслуживанием.

Среднее число заявок под обслуживанием определим по формуле математического ожидания числа заявок под обслуживанием, принимающего значения 0 (если канал свободен) либо 1 (если канал занят):

$L_{text{ob.}}=0cdot p_0+1cdot (1-p_0),$

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

$L_{text{ob.}}=P_{text{zan.}}=1-p_0.$

(38)

В силу (33)

$L_{text{ob.}}=P_{text{zan.}}=rho.$

(39)

Теперь по формуле (37) с учетом (36) и (39)

$L_{text{och.}}=frac{rho^2}{1-rho},.$

(40)

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

$T_{text{sist.}}=frac{1}{lambda}cdot L_{text{sist.}} ,$

(41)

$T_{text{och.}}=frac{1}{lambda}cdot L_{text{och.}}.$

(42)

формулы (41) и (42) называются формулами Литтла. Они вытекают из того, что в предельном, стационарном режиме среднее число заявок, прибывающих в систему, равно среднему числу заявок, покидающих ее: оба потока заявок имеют одну и ту же интенсивность lambda .

На основании формул (41) и (42) с учетом (36) и (40) среднее время пребывания заявки в системе определится по формуле:

$T_{text{sist.}}=frac{rho}{lambda(1-rho)},,$

(43)

а среднее время пребывания заявки в очереди —

$T_{text{och.}}=frac{rho^2}{lambda(1-rho)},.$

(44)

Пример 8. В порту имеется один причал для разгрузки судов. Интенсивность потока судов равна 0,4 (судов в сутки). Среднее время разгрузки одного судна составляет 2 суток. Предполагается, что очередь может быть неограниченной длины. Найти показатели эффективности работы причала, а также вероятность того, что ожидают разгрузки не более чем 2 судна.

Решение. Имеем $rho=frac{lambda}{mu}=lambdaoverline{t}_{text{ob.}}=0,!4cdot2=0,!8$ . Так как rho=0,!8<1 , то очередь на разгрузку не может бесконечно возрастать и предельные вероятности существуют. Найдем их.

Вероятность того, что причал свободен, по (33) p_0=1-0,!8=0,!2 , а вероятность того, что он занят, $P_{text{zan.}}=1-0,!2=0,!8$ . По формуле (34) вероятности того, что у причала находятся 1, 2, 3 судна (т.е. ожидают разгрузки 0, 1, 2 судна), равны

p_1=0,!8(1-0,!8)=0,!16;quad p_2=0,!8^2(1-0,!8)=0,!128;quad p_3=0,!8^3(1-0,!8)=0,!1024.

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

P=p_1+p_2+p_3=0,!16+0,!128+0,!1024=0,!3904.

По формуле (40) среднее число судов, ожидающих разгрузки, $L_{text{och.}}=frac{0,!8^2}{1-0,!8}=3,!2$ среднее время ожидания разгрузки по формуле (42) $T_{text{och.}}=frac{3,!2}{0,!8}=4$ (сутки).

По формуле (36) среднее число судов, находящихся у причала, $L_{text{sist.}}=frac{0,!8}{1-0,!8}=4$ (сутки) (или проще по (37) $L_{text{sist.}}=3,!2+0,!8=4$ (сутки), а среднее время пребывания судна у причала по формуле (41) $T_{text{sist.}}=frac{4}{0,!8}=5$ (сутки).

Очевидно, что эффективность разгрузки судов невысокая. Для ее повышения необходимо уменьшение среднего времени разгрузки судна $overline{t}_{text{ob.}}$ либо увеличение числа причалов.

Многоканальная СМО с неограниченной очередью

Рассмотрим задачу. Имеется n-канальная СМО с неограниченной очередью. Поток заявок, поступающих в СМО, имеет интенсивность lambda , а поток обслуживании — интенсивность . Необходимо найти предельные вероятности состояний СМО и показатели ее эффективности.

Система может находиться в одном из состояний S_0,S_1,S_2,ldots,S_k,ldots,S_n,ldots нумеруемых по числу заявок, находящихся в СМО: S_0 — в системе нет заявок (все каналы свободны); S_1 — занят один канал, остальные свободны; S_2 — заняты два канала, остальные свободны; ldots,S_k — занято каналов, остальные свободны; ldots,S_n — заняты все каналов (очереди нет); $S_{n+1}$ — заняты все каналов, в очереди одна заявка; $ldots,S_{n+r}$ — заняты все каналов, заявок стоит в очереди, и т.д.

Граф состояний системы показан на рис. 9. Обратим внимание на то, что в отличие от предыдущей СМО, интенсивность потока обслуживании (переводящего систему из одного состояния в другое справа налево) не остается постоянной, а по мере увеличения числа заявок в СМО от 0 до увеличивается от величины до nmu , так как соответственно увеличивается число каналов обслуживания. При числе заявок в СМО большем, чем , интенсивность потока обслуживании сохраняется равной nmu .

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

Можно показать, что при $frac{rho}{n}<1$ предельные вероятности существуют. Если $frac{rho}{n}geqslant1$ , очередь растет до бесконечности. Используя формулы (16) и (17) для процесса гибели и размножения, можно получить следующие формулы для предельных вероятностей состояний n-канальной СМО с неограниченной очередью

$p_0={left(1+ frac{rho^1}{1!}+ frac{rho^2}{2!}+ldots+frac{rho^n}{n!}+ frac{rho^{n+1}}{n!(n-rho)}right)!}^{-1},$

(45)

$p_1=frac{rho^1}{1!}cdot p_0,~ldots,~ p_k=frac{rho^k}{k!}cdot p_0,~ldots,~ p_n=frac{rho^n}{n!}cdot p_0,$

(46)

$p_{n+1}=frac{rho^{n+1}}{ncdot n!}cdot p_0,~ldots,~p_{n+r}=frac{rho^{n+r}}{n^rcdot n!}cdot p_0,~ldots$

(47)

Вероятность того, что заявка окажется в очереди,

$P_{text{och.}}=frac{rho^{n+1}}{n!(n-rho)}cdot p_0.$

(48)

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

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

$overline{k}=frac{lambda}{mu}=rho,$

(49)

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

$L_{text{och.}}=frac{rho^{n+1}cdot p_0}{ncdot n!}cdotleft(1-frac{rho}{n}right)^{-2},,$

(50)

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

$L_{text{sist}}=L_{text{och.}}+rho.$

Среднее время пребывания заявки в очереди и среднее время пребывания заявки в системе, как и ранее, находятся по формулам Литтла (42) и (41).

Замечание. Для СМО с неограниченной очередью при rho<1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа $P_{text{otk.}}=0$ , относительная пропускная способность Q=1 , а абсолютная пропускная способность равна интенсивности входящего потока заявок, т.е. A=lambda .

Пример 9. В универсаме к узлу расчета поступает поток покупателей с интенсивностью lambda=81 чел. в час. Средняя продолжительность обслуживания контролером-кассиром одного покупателя $overline{t}_{text{ob.}}=2$ мин. Определить:

а. Минимальное количество контролеров-кассиров $n_{min}$ , при котором очередь не будет расти до бесконечности, и соответствующие характеристики обслуживания при $n=n_{min}$ .

б. Оптимальное количество $n_{text{opt.}}$ контролеров-кассиров, при котором относительная величина затрат $C_{text{otn.}}$ , связанная с издержками на содержание каналов обслуживания и с пребыванием в очереди покупателей, задаваемая, например, как $C_{text{otn.}}=frac{n}{lambda}+3T_{text{och.}}$ , будет минимальна, и сравнить характеристики обслуживания при $n=n_{min}$ и $n=n_{text{opt.}}$ .

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

Решение. а. По условию lambda=81 (1/ч) $=frac{81}{60}=1,!35$ (1/мин.). По формуле (24) $rho=frac{lambda}{mu}=lambdaoverline{t}_{text{ob.}}=1,!35cdot2=2,!7$ . Очередь не будет возрастать до бесконечности при условии $frac{rho}{n}<1$ , т.е. при n>rho=2,!7 . Таким образом, минимальное количество контролеров-кассиров $n_{min}=3$ .

Найдем характеристики обслуживания СМО при n=3 .

Вероятность того, что в узле расчета отсутствуют покупатели, по формуле (45)

$p_0={left(1+2,!7+ frac{2,!7^2}{2!}+ frac{2,!7^3}{3!}+ frac{2,!7^4}{3!(3-2,!7)}right)!}^{-1}=0,!025$

т.е. в среднем 2,5% времени контролеры-кассиры будут простаивать.

Вероятность того, что в узле расчета будет очередь, по (48)

$P_{text{och.}}=frac{2,!7^4}{3!cdot(3-2,!7)}cdot0,!025=0,!735.$

Среднее число покупателей, находящихся в очереди, по (50)

$L_{text{och.}}=frac{2,!7^4}{3cdot3!cdot(1-2,!7/3)^2}cdot0,!025=7,!35.$

Среднее время ожидания в очереди по (42)

$T_{text{och.}}=frac{7,!35}{1,!35}=5,!44$ (мин).

Среднее число покупателей в узле расчета по (51)

$L_{text{sist.}}= 7,!35+2,!7=10,!05.$

Среднее время нахождения покупателей в узле расчета по (41)

$T_{text{sist.}}=frac{10,!05}{1,!35}approx7,!44$ (мин).

Среднее число контролеров-кассиров, занятых обслуживанием покупателей, по (49) overline{k}=2,!7 .

Коэффициент (доля) занятых обслуживанием контролеров-кассиров $overline{k}_{text{otn.}}=frac{rho}{n}=frac{2,!7}{3}=0,!9$ .

Абсолютная пропускная способность узла расчета A=1,!35 (1/мин), или 81 (1/ч), т.е. 81 покупатель в час.

Анализ характеристик обслуживания свидетельствует о значительной перегрузке узла расчета при наличии трех контролеров-кассиров.

б. Относительная величина затрат при n=3

$C_{text{otn.}}=frac{n}{lambda}+3T_{text{och.}}=frac{3}{1,!35}+3cdot5,!44=5,!44.$

Рассчитаем относительную величину затрат при других значениях (табл. 2).

Расчёт относительных величин затрат

Как видно из табл. 2, минимальные затраты получены при $n=n_{text{opt.}}=5$ контролерах-кассирах.

Определим характеристики обслуживания узла расчета при $n=n_{text{opt.}}=5$ . Получим

$P_{text{och.}}=0,!091;~ L_{text{och.}}= 0,!198;~ T_{text{och.}}=0,!146;~ L_{text{sist.}}=2,!9;~ T_{text{sist.}}=2,!15;~ overline{k}=2,!7;~k_3=0,!54.$

Как видим, при n=5 по сравнению с n=3 существенно уменьшились вероятность возникновения очереди $P_{text{och.}}$ , длина очереди $L_{text{och.}}$ и среднее время пребывания в очереди $T_{text{och.}}$ , и соответственно среднее число покупателей $L_{text{sist.}}$ и среднее время нахождения в узле расчета $T_{text{sist.}}$ , а также доля занятых обслуживанием контролеров k_3 . Но среднее число занятых обслуживанием контролеров-кассиров overline{k} и абсолютная пропускная способность узла расчета естественно не изменились.

в. Вероятность того, что в очереди будет не более 3 покупателей, определится как

$P{rleqslant3}=p_1+p_2+p_3+p_4+p_5+p_{5+1}+p_{5+2}+p_{5+3}=1-P_{text{och.}}+p_{5+1}+p_{5+2}+p_{5+3},$

где каждое слагаемое найдем по формулам (45)–(48). Получим при n=5:

$P{rleqslant3}=1-frac{2,!7^6}{5!(5-2,!3)}cdot 0,!065+frac{2,!7^6}{5cdot5!}cdot0,!065 +frac{2,!7^7}{5^2cdot5!}cdot0,!065 +frac{2,!7^8}{5^3cdot5!}cdot0,!065=0,!986.$

(Заметим, что в случае n=3 контролеров-кассиров та же вероятность существенно меньше: P{rleqslant3}=0,!464 ).

Пример 10. Железнодорожная касса с двумя окошками продает билеты в два пункта и . Интенсивность потока пассажиров, желающих купить билеты, для обоих пунктов одинакова: $lambda_{A}=lambda_{B}=0,!45$ (пассажиров в минуту). На обслуживание пассажиров кассир тратит в среднем 2 мин. Рассматриваются два варианта продажи билетов: первый — билеты продаются в одной кассе с двумя окошками одновременно в оба пункта и , второй — билеты продаются в двух специализированных кассах (по одному окошку в каждой), одна только в пункт , другая — только в пункт . Необходимо:

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

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

Решение.
а. По первому варианту имеем двухканальную СМО, на которую поступает поток заявок интенсивностью lambda=0,!45+0,!45=0,!9 ; интенсивность потока обслуживании $mu=frac{1}{2}=0,!5;$ $rho=frac{lambda}{mu}=1,!8$ . Так как $frac{rho}{n}=frac{1,!8}{2}=0,!9<1$ , то предельные вероятности существуют.

Вероятность простоя двух кассиров по (45)

$p_0={left(1+ frac{1,!8}{1!}+ frac{1,!8^2}{2!}+ frac{1,!8^3}{2!cdot(2-1,!8)}right)!}^{-1}approx0,!0526.$

Среднее число пассажиров в очереди по (50)

$L_{text{och.}}=frac{1,!8^3}{2cdot2!cdot(1-1,!8/2)^2}cdot0,!0526=7,!67.$

Среднее число пассажиров у кассы по (51)

$L_{text{sist.}}= 7,!67+1,!8=9,!47.$

Среднее время на ожидание в очереди и покупку билетов равно соответственно (по формулам (42) и (41)):

$T_{text{och.}}=frac{7,!67}{0,!9}=8,!52$ (мин) и $T_{text{sist.}}=frac{9,!47}{0,!9}=10,!5$ (мин).

По второму варианту имеем две одноканальные СМО (два специализированных окошка); на каждую поступает поток заявок с интенсивностью lambda=0,!45 . По-прежнему mu=0,!5; $rho=frac{lambda}{mu}=0,!9<1$ , предельные вероятности существуют. По формулам (40), (36), (42), (41)

$L_{text{och.}}=frac{0,!9^2}{1-0,!9}=8,!1;~ L_{text{sist.}}=frac{0,!9}{1-0,!9}=9;~ T_{text{och.}}=frac{8,!1}{0,!45}=18;~ T_{text{sist.}}=frac{9}{0,!45}=20.$

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

Можно заметить, что среднее время на покупку билетов по второму варианту увеличилось более чем в 2 раза. Такое значительное увеличение связано с тем, что СМО работает на пределе своих возможностей (rho=0,!9) : достаточно незначительно увеличить среднее время обслуживания $overline{t}_{text{ob.}}$ , т.е. уменьшить , и rho превзойдет 1, т.е. очередь начнет неограниченно возрастать.

б. Выше было получено, что по первому варианту продажи билетов при среднем времени обслуживания одного пассажира $overline{t}_{text{ob.}}=2$ (мин) среднее время на покупку билетов составит $T_{text{sist.1}}=10,!5$ (мин). По условию для второго варианта продажи $T_{text{sist.2}}<T_{text{sist.1}}$ , или с учетом (36) и (41): $frac{1}{lambda}frac{rho}{1-rho}< T_{text{sist.1}}$ .

Полагая $rho=frac{lambda}{mu}=lambdaoverline{t}_{text{ob.}}$ , получим $-frac{overline{t}_{text{ob.}}}{1-lambdaoverline{t}_{text{ob.}}}<T_{text{sist.1}}$ , откуда найдем $overline{t}_{text{ob.}}<frac{T_{text{sist.1}}}{1+lambda T_{text{sist.1}}}$ или $overline{t}_{text{ob.}}<frac{10,!5}{1+0,!45cdot10,!5}=1,!83$ (мин).

Итак, средние затраты времени на покупку билетов по второму варианту продажи уменьшатся, если среднее время обслуживания одного пассажира уменьшится более чем на 0,17 мин, или более чем на 8,5%.

СМО с ограниченной очередью

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

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

Среднее время пребывания заявки в очереди и в системе, как и ранее, определяем по формулам Литтла (44) и (43).

Таблица 3. Показатели одно- и многоканальной СМО с ограниченной очередью

Показатели одно- и многоканальной СМО с ограниченной очередью

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

Решение. По условию m=3 . Используем формулы, приведенные во второй графе табл. 3.

Вероятность того, что причал свободен:

$p_0=frac{1-0,!6}{1-0,!8^{3+2}}=0,!297.$

Вероятность того, что приходящее судно покинет причал без разгрузки:

$P_{text{otk.}}=0,!8^{3+1}cdot 0,!122.$

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

Q=1-0,!122=0,!878.

Абсолютная пропускная способность причала A=0,!4cdot0,!878=0,!351 , т.е. в среднем в сутки разгружается 0,35 судна.

Среднее число судов, ожидающих разгрузку

$L_{text{och.}}=frac{0,!8^2cdot[1-0,!8^3cdot(3+1-3cdot0,!8)]}{(1-0,!8^{3+2})(1-0,!8)}=0,!861,$

а среднее время ожидания разгрузки по (42)

$T_{text{och.}}=frac{0,!861}{0,!8}=1,!076$ (сутки).

Среднее число судов, находящихся у причала $L_{text{sist.}}=0,!861+(1-0,!297)=1,!564$ , а среднее время пребывания судна у причала по (41):

$T_{text{sist.}}=frac{1,!564}{0,!8}=1,!955$ (сутки).

СМО с ограниченным временем ожидания

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

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

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

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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Кнопка "Поделиться"

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

Источник

Теория массового обслуживания (СМО)

Формулы для расчета параметров простейших СМО

8.5. Вероятности состояний СМО

Одноканальная система массового обслуживания с отказами

Многоканальная система массового обслуживания с отказами

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

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

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

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

СМО с ожиданием (очередью): определение и формулы

Одноканальная система с неограниченной очередью

Многоканальная СМО с неограниченной очередью

СМО с ограниченной очередью

СМО с ограниченным временем ожидания

Многоканальная система
массового обслуживания с отказами

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

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

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

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