3.2. Определение характеристик систем массового обслуживания
Простейшая одноканальная модель. Такой моделью с вероятностными входным потоком и процедурой обслуживания является модель, характеризуемая показательным распределением как длительностей интервалов между поступлениями требований, так и длительностей обслуживания.
При этом плотность распределения длительностей интервалов между поступлениями требований имеет видA(t) = le-Xt, (3.1)
где X — интенсивность поступления заявок в систему.
Плотность распределения длительностей обслуживания:
№ = (3.2)
где [і — интенсивность обслуживания.
Потоки заявок и обслуживаний простейшие.
Пусть система работает с отказами. Необходимо определить абсолютную и относительную пропускную способность системы.
Представим данную систему массового обслуживания в виде графа (рис. 3.1), у которого имеются два состояния: — канал свободен (ожидание);
Si — канал занят (идет обслуживание заявки).
и
Рис. 3.1. Граф состояний одноканальной СМО с отказами
Обозначим вероятности состояний: P0(t) — вероятность состояния «канал свободен»; Px(t) — вероятность состояния «канал занят». По размеченному графу состояний (рис. 3.1) составим систему дифференциальных уравнений Колмогорова для вероятностей состояний:
dP0(t)
dt (3.3)
a t
Система линейных дифференциальных уравнений (3.3) имеет решение с учетом нормировочного условия P0(t) + /^(ґ) = 1. Реше-ние данной системы называется неустановившимся, поскольку оно непосредственно зависит от t и выглядит следующим образом:
= (3.4)
и А+ц А + ц
Px(t) = 1 - P0(t). (3.5)
Нетрудно убедиться, что для одноканальной СМО с отказами вероятность P0(t) есть не что иное, как относительная пропускная способность системы q.
Действительно, Р0 — вероятность того, что в момент t канал свободен и заявка, пришедшая к моменту будет обслужена, а следовательно, для данного момента времени t среднее отношение числа обслуженных заявок к числу поступивших также равно т.
е.q = P0(t)• (3.6)
По истечении большого интервала времени (при t оо) достигается стационарный (установившийся) режим:
Зная относительную пропускную способность, легко найти абсолютную. Абсолютная пропускная способность (А) — среднее число заявок, которое может обслужить система массового обслуживания в единицу времени:
А = Хд = ^~. (3.8)
Л + ц
Вероятность отказа в обслуживании заявки будет равна вероятности состояния «канал занят»:
'«-'М-'Ь-'-х^-зйг <«>
Данная величина Ротк может быть интерпретирована как средняя доля необслуженных заявок среди поданных.
Пример 3.1. Пусть одноканальная СМО с отказами представляет собой один пост ежедневного обслуживания (ЕО) для мойки автомобилей. Заявка - автомобиль, прибывший в момент, когда пост занят, — получает отказ в обслуживании. Интенсивность потока автомобилей Я = 1,0 (автомобиль в час). Средняя продолжительность обслуживания — 1,8 часа. Поток автомобилей и поток обслуживании являются простейшими.
Требуется определить в установившемся режиме предельные значения:
относительной пропускной способности q\
абсолютной пропускной способности А\
вероятности отказа Ротк.
Сравните фактическую пропускную способность СМО с номинальной, которая была бы, если бы каждый автомобиль обслуживался точно 1,8 часа и автомобили следовали один за другим без перерыва.
Решение
Определим интенсивность потока обслуживания:
Вычислим относительную пропускную способность:
ц 0,555
Величина q означает, что в установившемся режиме система будет обслуживать примерно 35% прибывающих на пост ЕО автомобилей.
3. Абсолютную пропускную способность определим по формуле: А = А • q = 1 • 0,356 = 0,356.
Это означает, что система (пост ЕО) способна осуществить в среднем 0,356 обслуживания автомобилей в час.
Вероятность отказа:
Лтс = 1 ~ 9 = 1 - 0,356 = 0,644.
Это означает, что около 65% прибывших автомобилей на пост ЕО получат отказ в обслуживании.
Определим номинальную пропускную способность системы:
Люм =? ~~~ 0,555 (автомобилей в час).
1 = 1 'обсл
°'555~1,5
\
больше, чем фак-
Оказывается, что Аном в 1,5 раза
0,356
тическая пропускная способность, вычисленная с учетом случайного характера потока заявок и времени обслуживания.
Одноканальная СМО с ожиданием.
Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание — простейший поток с интенсивностью А. Интенсивность потока обслуживания равна ц, (т. е. в среднем непрерывно занятый канал будет выдавать ц обслуженных заявок). Длительность обслуживания — случайная величина, подчиненная показательному закону распределения. Поток обслуживаний является простейшим пуассо- новским потоком событий. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.Предположим, что независимо от того, сколько требований поступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более ТУ-требований (заявок), т. е. клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте. Наконец, источник, порождающий за-явки на обслуживание, имеет неограниченную (бесконечно большую) емкость.
Граф состояний СМО в этом случае имеет вид, показанный на рис. 3.2.
X X X X X X
^^zzz^zizlQizi::: ::: 5=2®
и ц її її її її
Рис. 3.2. Граф состояний одноканальной СМО с ожиданием (схема гибели и размножения)
Состояния СМО имеют следующую интерпретацию:
— канал свободен;
— канал занят (очереди нет);
— канал занят (одна заявка стоит в очереди);
Sn - канал занят (п - 1 заявок стоит в очереди);
іSN — канал занят (N — 1 заявок стоит в очереди). Стационарный процесс в данной системе будет описываться следующей системой алгебраических уравнений:
-р*Ь+/1=0, л = 0;
(3.10)
-{1-р)Рп+Рп+\+рРя-\=09 0 п — номер состояния. Решение приведенной выше системы уравнений (3.10) для нашей модели СМО имеет вид (3.11) 1 Р . -р", Р*1, /1 = 0,1,2,..., N Тогда Р0-р" р*1, /1 = 1,2,..., ЛГ, Следует отметить, что выполнение условия стационарности * і р = — < 1 для данной СМО необязательно, поскольку число допу- И скаемых в обслуживающую систему заявок контролируется путем введения ограничения на длину очереди (которая не может превышать N — 1), а не соотношением между интенсивностями входного потока, т. Определим характеристики одноканалъной СМО с ожиданием и ограниченной длиной очереди, равной (N — 1): вероятность отказа в обслуживании заявки: (3.13) относительная пропускная способность системы: (3.14) абсолютная пропускная способность: (3.15) А = q X; среднее число находящихся в системе заявок: N ' Р*1 (3.16) LS=2nP„ = (l-p).(l-p"+1) N/2, р = 1; среднее время пребывания заявки в системе: средняя продолжительность пребывания клиента (заявки) в очереди: Wq=Ws- 1/W (3.18) среднее число заявок (клиентов) в очереди (длина очереди): Lq = Л(1 - PN)Wq. (3.19) Рассмотрим пример одноканальной СМО с ожиданием. Пример 3.2. Специализированный пост диагностики представляет собой одноканальную СМО. Число стоянок для автомобилей, ожидающих проведения диагностики, ограничено и равно 3 [(N — 1) = 3]. Если все стоянки заняты, т. е. в очереди уже нахо-дится три автомобиля, то очередной автомобиль, прибывший на диагностику, в очередь на обслуживание не становится. Поток автомобилей, прибывающих на диагностику, распределен по закону Пуассона и имеет интенсивность X = 0,85 (автомобиля в час). Время диагностики автомобиля распределено по показательному закону и в среднем равно 1,05 час. Требуется определить вероятностные характеристики поста диагностики, работающего в стационарном режиме. Решение Параметр потока обслуживаний автомобилей: „.i.^. 0,952. Приведенная интенсивность потока автомобилей определяется как отношение интенсивностей X и ц, т. е. Я=_0185_ = к ц 0,952 ' Вычислим финальные вероятности системы: Р 1-Р 1-0.893 Л) = Х77Г ~ Г = 0,248, 1-0,893 Р, = рР0 = 0,893 • 0,248 = 0,221 Р2 = р2Р0= 0.8932 • 0,248 = 0,198 Р2 = р3Р0= 0.8933 • 0,248 = 0,177 Р4 = р4Р0= 0,8934 • 0,248 = 0,158. Вероятность отказа в обслуживании автомобиля: = =РЧ = 0,158. Относительная пропускная способность поста диагностики: q = 1 - Ртк = 1 - 0,158 = 0,842. Абсолютная пропускная способность поста диагностики А = X ¦ q = 0,85 • 0,842 = 0,716 (автомобиля в час). Среднее число автомобилей, находящихся на обслуживании и в очереди (т.е. l-(N + l)pN +NpN+l LS = 0,893 (l-p)(l-p"+1) l-(4 + l) 0,8934 +4 0,8935 = 1,77. (1—0,893)-(l — 0,893 ) 8. Среднее время пребывания автомобиля в системе: 1,77 Ws = = 2,473 часа. А? X(l-PN) 0,85(1-0,158) Средняя продолжительность пребывания заявки в очереди на обслуживание: Wq= Ws- 1/ц = 2,473 - 1/0,952 = 1,423 часа. Среднее число заявок в очереди (длина очереди): Lq = X(l - PN) Wq = 0,85 • (1 - 0,158) • 1,423 = 1,02. Работу рассмотренного поста диагностики можно считать удовлетворительной, так как пост диагностики не обслуживает автомобили в среднем в 15,8% случаев (Ротк = 0,158). Одноканальная СМО с ожиданием без ограничения на вместимость блока ожидания (т. е. N —»<*>). Остальные условия функцио-нирования СМО остаются без изменений. Стационарный режим функционирования данной СМО существует при t —» ©о для любого п = О, 1, 2, ... и когда А < ц. Система алгебраических уравнений, описывающих работу СМО при t —» ©о для любого п = 0, 1,2, ..., имеет вид (3.20) -АРо+цР! =0, п = 0 ХРп-\ + іхРп+1 -(А + =0, п > 0. Решение данной системы уравнений имеет вид Рп = (1 - р) р", л = 0, 1, 2, ..., (3.21) где р = А/ц < 1. Характеристики одноканальной СМО с ожиданием, без ограничения на длину очереди, следующие: среднее число находящихся в системе клиентов (заявок) на обслуживание: Ls=ZnPn=-?-; (3.22) п=0 1-р средняя продолжительность пребывания клиента в системе: среднее число клиентов в очереди на обслуживании: средняя продолжительность пребывания клиента в очереди: Пример 3.3. Вспомним о ситуации, рассмотренной в примере 3.2, где речь идет о функционировании поста диагностики. Пусть рассматриваемый пост диагностики располагает неограниченным количеством площадок для стоянки прибывающих на обслуживание автомобилей, т. е. длина очереди не ограничена. Требуется определить финальные значения следующих вероят-ностных характеристик: вероятности состояний системы (поста диагностики); среднее число автомобилей, находящихся в системе (на обслуживании и в очереди); среднюю продолжительность пребывания автомобиля в системе (на обслуживании и в очереди); среднее число автомобилей в очереди на обслуживании; среднюю продолжительность пребывания автомобиля в очереди. Решение Параметр потока обслуживания ц, и приведенная интенсивность потока автомобилей р определены в примере 3.2: їх = 0,952; р = 0,893. Вычислим предельные вероятности системы по формулам
Л) = 1
Л = (1
Рг = (1
Рз = 0
Ра = (1
= (1
- р) р = - р) р2 = Р) Р = -р)р4 = Р) Р5 = 0,893) 0,893) 0,893) 0,893) 0,893) 0,893 = 0,107; 0,893 = 0,096; 0,8932 = 0,085; 0,8933 = 0,076; 0,8934 = 0,068; 0,893 = 0,061 и т. Следует отметить, что Р0 определяет долю времени, в течение которого пост диагностики вынужденно бездействует (простаивает). В нашем примере она составляет 10,7%, так как Р0 = 0,107. 3. Среднее число автомобилей, находящихся в системе (на обслуживании и в очереди): 0,893 = 8,346 ед. 1-р 1-0,893 4. Средняя продолжительность пребывания клиента в системе: = 9,817 час. w -Ls - 1 1 5 X [ц(1-р)] [0,952-(1-0,893)] 0,893 Lq = Ls-- = = 7,453. їх (1-р) (1-0,893) Средняя продолжительность пребывания автомобиля в очереди: ЖдаГ8-766 ™' Относительная пропускная способность системы: <7=1, т. е. каждая заявка, пришедшая в систему, будет обслужена. Абсолютная пропускная способность: А = Xq = 0,85 • 1 = 0,85. Следует отметить, что предприятие, осуществляющее диагностику автомобилей, прежде всего интересует количество клиентов, которое посетит пост диагностики при снятии ограничения на длину очереди. Допустим, в первоначальном варианте количество мест для стоянки прибывающих автомобилей было равно трем (см. пример 3.2). Частота т возникновения ситуаций, когда прибывающий на пост диагностики автомобиль не имеет возможности присоединиться к очереди: т = X PN. В нашем примере при N=3 + 1 = 4 и р = 0,893, т = Х Р0 р4 = 0,85 • 0,248 • 0,8934 = 0,134 автомобиля в час. При 12-часовом режиме работы поста диагностики это эквивалентно тому, что пост диагностики в среднем за смену (день) будет терять 12 • 0,134 = 1,6 автомобиля. Снятие ограничения на длину очереди позволяет увеличить количество обслуженных клиентов в нашем примере в среднем на 1,6 автомобиля за смену (12 ч. работы) поста диагностики. Ясно, что решение относительно расширения площади для стоянки автомоби-лей, прибывающих на пост диагностики, должно основываться на оценке экономического ущерба, который обусловлен потерей клиентов при наличии всего трех мест для стоянки этих автомобилей.