СМО с ожиданием (очередью)

В качестве показателей эффективности СМО с ожиданием, кроме уже известных показателей — абсолютной А и относитель­ной Q пропускной способности, вероятности отказа Р_тк., средне-

Глава 15

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

 

го числа занятых каналов к (для многоканальной системы) будем рассматривать также следующие: 1_Сист. ^— среднее число заявок t. системе; Т_тс1 — среднее время пребывания заявки в системе; L₀₄ -* среднее число заявок в очереди {длина очереди); Т_оч — среднее время ^ пребывания заявки в очереди; />_зан — вероятность того, что канал занят {степень загрузки канала).

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

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

Система может находиться в одном из состояний 5о> ^ь $2, ■■■■> $ь по числу заявок, находящихся в СМО: Sq — канал свободен; S\ — канал занят (обслуживает заявку), очереди нет; Si — канал занят, одна заявка стоит в очереди;... S_k — канал занят, {к-\) заявок стоят в очереди и т.д.

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

 

 

 

 

 

 

 

•So	X	Ji	X	Si
и	ц

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

-1

1 ^х

+...+

+..

Рог

1ц;

1 + —+

(15.32)

= (l + p + p²+...+p*+---) •

Так как предельные вероятности существуют лишь при р < 1, то геометрический ряд со знаменателем р < 1, записанный в

По- 1-р (15.33)

скобках в формуле (15.32), сходится к сумме, равной

этому

А>=1^-Р. и с учетом соотношений (15.17)

Pl⁼PP0, Р2=Р²Р0, •••> РкГР^кР0, -

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

(15.34)

/»1=р(1-р), Л=Р²0-р), -, />*=Р*(1-р), ••■ •

 

Рис. 15.8

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

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

Предельные вероятности р₀, р_ь р₂,..., Рк,... образуют убываю­щую геометрическую профессию со знаменателем р < 1, следова­тельно, вероятность ро — наибольшая. Это означает, что если СМО справляется с потоком заявок (при р < 1), то наиболее ве­роятным будет отсутствие заявок в системе.

Среднее число заявок в системе Ь_СИ<Л определим по формуле, математического ожидания, которая с учетом (15.34) примет вид

(15.35)

^!5>*=(1-р)1*р*

к=\ к=1

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

ч

Глава 15

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

 

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

4ист = ~- (15.36)

1-р

Найдем среднее число заявок в очереди L₀₄. Очевидно, что

^оч. ^сист. ^об.> \Ij.jI)

где Дэб. — среднее число заявок, находящихся под обслужива­нием.

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

А>б⁼0-/>о+Ц1-/>о),

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

 

А>б.-Аан._1~Л)-	(15.38)
В силу (15.33)
А>б.—* зан.—Р-	(15.39)
Теперь по формуле (15.37) с учетом (15.36) и (15.39)
L =^	(15.40)

1-р

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

'сист.^-Т" ^сист.> 113.41J

'оч.⁼ ~г А>ч.- (15.42)

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

_ р

На основании формул (15.41) и (15.42) с учетом (15.36) и (15.40) среднее время пребывания заявки в системе определится по формуле:

(15.43)

Т =

¹ П1Г.Т

М1-Р)

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

„2

(15.44)

^ Ш-Р)

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

Решение. Имеем р = А,/и ⁼ ^об. ⁼ 0,4-2 = 0,8. Так как р = = 0,8 < 1, то очередь на разгрузку не может бесконечно возрастать и предельные вероятности существуют. Найдем их.

Вероятность того, что причал свободен, по (15.33) р₀ = 1-- 0,8 = 0,2, а вероятность того, что он занят, Р_зш, = 1—0,2 = 0,8. По формуле (15.34) вероятности того, что у причала находятся 1, 2, 3 судна (т.е. ожидают разгрузки 0, 1, 2 судна), равны р\ = 0,8(1-0,8) = 0,16; р₂ = 0,8²-(1-0,8) = 0,128; р₃ = 0,8³(1-0,8) = = 0,1024.

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

Р = pi+p2+P3 = 0,16+0,128+0,1024 = 0,3904.

По формуле (15.40) среднее число судов, ожидающих разгрузки,

4,_ч. = 0,82/(1-0,8) = 3,2,

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

Г_оч. = 3,2/0,8 = 4 (сутки).

Глава 15

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

 

По формуле (15.36) среднее число судов, находящихся у при­чала, /-_сист. = 0,8/(1-0,8) = 4 (сутки) (или проще по (15.37) 2_СИСт. ⁼ = 3,2+0,8 = 4 (сутки), а среднее время пребывания судна у прича­ла по формуле (15.41) 7с_ИСт. ⁼ 4/0,8 = 5 (сутки).

Очевидно, что эффективность разгрузки судов невысокая. Для ее повышения необходимо уменьшение среднего времени раз­грузки судна f ₀б. либо увеличение числа причалов л>

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

Система может находиться в одном из состояний iSo, S\, -5*2,...,
S_k,..., S„,..., нумеруемых по числу заявок, находящихся в СМО:
$о — в системе нет заявок (все каналы свободны); S\ — занят
один канал, остальные свободны; ^ — заняты два канала, осталь­
ные свободны;..., iSjt — занято к каналов, остальные свободны;...,
S„ — заняты все л каналов (очереди нет); S_n+\ — заняты все л
каналов, в очереди одна заявка;..., S_n+r — заняты все л каналов, г
заявок стоит в очереди,.... '

X к\х	st	X (*+1)ц
X ^ Я|1	S„+r

лц

яц

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

 

 

 

 

 

So	X	Si	X
и	2|i

 

 

 

 

 

X	s.	X	S„+\
лц	лц

Рис. 15.9

Можно показать, что при р/я < 1 предельные вероятности су­ществуют. Если р/я 2: 1, очередь растет до бесконечности. Ис­пользуя формулы (15.16) и (15.17) для процесса гибели и размно­жения, можно получить следующие формулы для предельных вероятностей состояний я-канальной СМО с неограниченной очередью

( „ „2 _пп _пп+\ \

(15.45)

Ро =

1 + Л + Н-+ | Р ■ р 1! 2! '" я! я!(я-р),

Ро,---,Рк

Р\

к\

1!

А)>---.Л!=ПГР0. (15.46)

,л+1

п+г

Рп+\ =

пп

Ро,---,Р_п+г=—_г —-Л).-- (15.47)

ял!

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

вка окажется в очереди,

P₀₄ = -f^rPo- (15.48)

л!(л - р)

(15.49)

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

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

(15.50)

•^оч.

_ Р" РО

ял! 1

Р я

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

(15.51)

•^сист.⁼ А)Ч.~*~Р-

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

Замечание. Для СМО с неограниченной очередью при р < 1 любая заявка, пришедшая в систему, будет обслужена, т.е. ве-

Глава >15

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

 

роятность отказа Р_отк = 0, относительная пропускная способ­ность Q = 1, а абсолютная пропускная способность равна ин­тенсивности входящего потока заявок, т.е. А = X. &■ 15.9. В универсаме к узлу расчета поступает поток покупателей с интенсивностью X = 81 чел. в час. Средняя продолжитель­ность обслуживания контролером-кассиром одного покупателя '"об. ⁼ 2 мин. Определить:

а. Минимальное количество контролеров-кассиров я_тщ, при
котором очередь не будет расти до бесконечности, и соответст­
вующие характеристики обслуживания при n=n_min.

б. Оптимальное количество л_опт контролеров-кассиров, при
котором относительная величина затрат С_отн, связанная с из­
держками на содержание каналов обслуживания и с пребывани­
ем в очереди покупателей, задаваемая, например, как С_отн =

= — л + ЗГ_0Ч, будет минимальна, и сравнить характеристики об-

X

служивания при п=п_т\_п и л=л_опт.

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

Решение, а. По условию X = 81(1/ч) = 81/60 = 1,35 (1/мин.). По формуле (15.24) р = Х/ц = Я./_об. = 1,35-2 = 2,7. Оче­редь не будет возрастать до бесконечности при условии р/л < 1, т.е. при л > р = 2,7. Таким образом, минимальное количество контролеров-кассиров л_тщ = 3.

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

Вероятность того, что в узле расчета отсутствуют покупатели, по формуле (15.45) р₀ = (1+2,7+2,7²/2!+2,7³/3!+2,7⁴/3!(3-2,7))-¹ = = 0,025, т.е. в среднем 2,5% времени контролеры-кассиры будут простаивать.

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

Р_т. = (2,7⁴/3!(3-2,7))0,025 = 0,735. Среднее число покупателей, находящихся в очереди, по (15.50)

А>ч. = (2,7⁴/3-3!(1-2,7/3)²)0,025 = 7,35. Среднее время ожидания в очереди по (15.42)

Т_оч. = 7,35/1,35 = 5,44 (мин).

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

£сист. = 7,35+2,7 = 10,05.

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

Т'сист. ⁼ 10,05/1,35 = 7,44 (мин).

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

покупателей, по (15.49) к = 2,7.

Коэффициент (доля) занятых обслуживанием контролеров-кассиров

к = р/л = 2,7/3 = 0,9.

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

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

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

Со™. = -и +37оч. = 3/1,35+3-5,44 = 18,54.

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

Таблица 15.2

 

 

Характеристика обслуживания	Число контролеров-кассиров
Вероятность простоя кон­тролеров-кассиров р0	0,025	0,057	0,065	0,067	0,067
Среднее число покупателей в очереди Точ	5,44	0,60	0,15	0,03	0,01
Относительная величина затрат Сотн.	18,54	4,77	4,14	4,53	5,22

Как видно из табл. 15.2, минимальные затраты получены при и ⁼ "опт. ⁼ 5 контролерах-кассирах.

Глава 15

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

 

Определим характеристики обслуживания узла расчета при я = = «_опт = 5. Получим Р_оч. = 0,091; 1₀ч. = 0,198; Г_оч. = 0,146 (мин); Ажст. = 2,90; Г_сист. = 2,15 (мин); к = 2,7; к_г = 0,54.

Как видим, при п = 5 по сравнению с п = 3 существенно уменьшились вероятность возникновения очереди Р_оч., длина очереди Ь_оч и среднее время пребывания в очереди Г_оч и соот­ветственно среднее число покупателей L_clfCT и среднее время на­хождения в узле расчета Г_сист, а также доля занятых обслужива­нием контролеров &з- Но среднее число занятых обслуживанием контролеров-кассиров к и абсолютная пропускная способность узла расчета А естественно не изменились.

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

Р(Г й 3) = Р\+Р2+Р3+Р4+Р5 + P5+l⁺PS+2⁺P5+3=
(когда заняты от 1 (когда в очереди

до 5 контролеров-кассиров) стоят от 1 до 3 покупателей)

= l-P₀4.⁺Ps+i⁺Ps+2⁺P5+3> ^гД^е каждое слагаемое найдем по формулам (15.45)—(15.48). Получим при п - 5:

2 7⁷ 2 7⁸

+ -^-.0,065 + -4^—0,065 = 0,986.

5²-5! 5³-5!

(Заметим, что в случае я=3 контролеров-кассиров та же веро­ятность существенно меньше: Р(г<, 3)=0,464)> ^ 15.10. Железнодорожная касса с двумя окошками продает билеты в два пункта А и В. Интенсивность потока пассажиров, желающих купить билеты, для обоих пунктов одинакова: Х_А = Хд — 0,45 (пассажиров в минуту). На обслуживание пассажиров кассир тратит в среднем 2 мин. Рассматриваются два варианта продажи билетов: первый — билеты продаются в одной кассе с двумя окошками од­новременно в оба пункта А и В; второй — билеты продаются в двух специализированных кассах (по одному окошку в каждой), одна только в пункт А, другая — только в пункт В. Необходимо:

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

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

Решение, а. По первому варианту имеем двухканальную СМО, на которую поступает поток заявок интенсивностью X = 0,45+0,45 = = 0,9; интенсивность потока обслуживании ц. = 1/2 = 0,5; р = Х/\х. = = 1,8. Так как р/л = 1,8/2 = 0,9 < 1, то предельные вероятности существуют.

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

_Po=\i ₊ ±l₊^ll?L₊ Ь8³ 1 ₌₀₀₅₂₆

™ { 1! 2! 2!(2-l,8)J Среднее число пассажиров в очереди по (15.50) L₀₄. = 1,8³/2-2!(1-1,8/2)0,0526 = 7,67. Среднее число пассажиров у кассы по (15.51) 4ист. = 7,67+1,8 = 9,47.

Среднее время на ожидание в очереди и покупку билетов равно соответственно (по формулам (15.42) и (15.41)): Т_оч = 7,67/0,9 = = 8,52 (мин) и Гее-,, - 9,47/0,9 = 10,5 (мин).

По второму варианту имеем две одноканальные СМО (два спе­циализированных окошка); на каждую поступает поток заявок с интенсивностью X = 0,45. По-прежнему ц = 0,5; р ⁼ X/\i = 0,9 < 1, предельные вероятности существуют. По формулам (15.40), (15.36), (15.42), (15.41)

А>ч. = 0,9²/(1-0,9) = 8,1; 1_сист. = 0,9/(1-0,9) = 9,0; Г_оч. = 8,1/0,45 = 18,0 (мин), Г_сист. = 9,0/0,45 = 20,0 (мин).

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

Глава 15;

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

 

Можно заметить, что среднее время на покупку билетов по второму варианту увеличилось более чем в 2 раза. Такое значи­тельное увеличение связано с тем, что СМО работает на пределе своих возможностей (р = 0,9): достаточно незначительно увели­чить среднее время обслуживания 1 _об, т.е. уменьшить ц, и р пре­взойдет 1, т.е. очередь начнет неограниченно возрастать.

б. Выше было получено, что по первому варианту продажи би­летов при среднем времени обслуживания одного пассажира 1 ₀б. = 2 (мин) среднее время на покупку билетов составит T_cmJ = 10,5 (мин). По условию для второго варианта продажи

< т„

X 1-р 'об

Тсжт.2 < ^гсист,1 или с учетом (15.36) и (15.41):

< ^сист.,> откуда

1-Чб 10,5

1,83 (мин).

1 С11СТ.|

Полагая р = Vn ⁼ ^^{ об.> получим —

ИЛИ t об <

найдем / ₀б. <

1 + Х71

■сист, 1 + 0,45 10,5

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

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

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

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

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

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

_Л-_ЬМ =o,297. 1-0,8³⁺²

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

Л>тк=0,8³⁺¹-0,297=0,122.

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

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

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

_ 0^[l-0,8³(3 + l-3-0,8)'

= 0,861,

_ 0,861

(1-0,8³⁺²)(1-0,8) а среднее время ожидания разгрузки по (15.42)

* оч

0,8

1,076 (сутки).

Среднее число судов, находящихся у причала А:ист. = 0,861+(1-0,297) = 1,564, а среднее время пребывания судна у причала по (15.41):

Т'сист. = -~~ = 1,955 (сутки). ►
I 0,8

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

⇐ Предыдущая1234

Поделиться:

Воспользуйтесь поиском по сайту: