- •ПРЕДИСЛОВИЕ
- •1. ОБЩАЯ ХАРАКТЕРИСТИКА СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ
- •1.1. Основные элементы систем массового обслуживания
- •1.2. Пуассоновский поток требований
- •1.3. Типы систем обслуживания. Краткая символика
- •1.4. Показатели эффективности систем массового обслуживания
- •2. ОСНОВНЫЕ ТИПЫ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ
- •2.1. Системы масового обслуживания с отказами
- •2.2. Системы с бесконечным числом приборов
- •2.3. Системы массового обслуживания с ожиданием
- •2.4. Замкнутые системы массового обслуживания
- •2.5. Смешанные системы с ожиданием
- •3. СПЕЦИАЛЬНЫЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ
- •3.1. Упорядоченные системы
- •3.2. Системы с поступлением групповых заявок
- •3.3. Системы с приборами разной производительности
- •3.4. Многофазные системы
- •3.5. Системы с накопителем требований
- •3.6. Системы со смешанным потоком требований
- •3.7. Системы с ненадежными обслуживающими приборами
- •3.8. Системы с групповым обслуживанием
- •4. МАРКОВИЗИРОВАНИЕ МОДЕЛЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ
- •4.1. Потоки Эрланга и их свойства
- •4.2. Замена реальных потоков потоками Эрланга
- •4.3. Марковские модели процессов с ограниченным последействием
λ = 20, μ1 = 50 , μ2 = 25. Здесьα1 = 20 / 50 = 0,4 ; α2 = 20 / 25 = 0,8 и, следова-
тельно, по формулам (3.14) — (3.18) находим
p00 = (1− 0,4)(1− 0,8) = 0,12 ; P1 = 0,8(1− 0,4) = 0,48 ; P2 = 0,08; N1 = 0,67 ; N2 = 4 .
Таким образом, оба контролера одновременно незаняты в среднем 12% рабочего времени, а в отдельности незаняты в среднем: контролер А — 48% и контролер В — 8% рабочего времени. Очереди у контролера А практически нет, а у контролера В в среднем ожидают проверки три изделия.
Если система массового обслуживания замкнутая и, стало быть, число требований, поступающих на обслуживание, ограничено числом m, то вместо формулы (3.14) имеем
n |
n |
|
(1 − α1 )(1 − α2 )(α1 |
− α 2 ) |
|
pn1 ,n2 = α11 |
α1 |
2 |
(α1 − α2 )(α1m+2 − α 2m+2 )+ α1α 2 (α1m+1 − α2m+1 ) |
. |
При m → ∞ эта формула, естественно, переходит в формулу (3.14).
Если рассматривается система массового обслуживания с отказами, то вместо формулы (3.14) вероятности всех возможных состояний удовлетворяют следующим формулам:
p |
|
= |
1 |
|
; p = |
α1α22 |
|
p |
|
; |
|
00 |
|
(1+ α1 )(1 + α |
2 ) |
11 |
α1 + α |
2 |
|
00 |
|
|
p01 = α2 p00 ; p00 |
+ p01 + p10 + p11 |
= 1. |
|
При этом вероятность обслуживания каждого требования в обеих фазах (про- пускная способность системы) может быть найдена из равенства
pобсл = 1 (p00 + p10 ).
α2
Так, если в рассмотренном примере предположить, что изделия, посту- пающие на контрольный пункт, остаются не проверенными, когда они застают занятым соответствующий прибор, то
p00 = 0,397; p11 = 0,085; p01 = 0,318; p10 = 0,200; pобсл = 0,75
т. е. в этом случае только 75% изделий будут проверены.
3.5. Системы с накопителем требований
На практике встречаются такие системы массового обслуживания, в ко- торых требования поступают сначала в так называемый накопитель, а затем, после окончания обслуживания предыдущей партии накопившихся требований,
— на обслуживание. Такая ситуация возникает, например, при обработке дета- лей, предварительно накапливающихся в бункере.
Рассмотрим систему массового обслуживания, состоящую из накопителя требований и обслуживающего прибора. В накопитель поступает пуассонов- ский поток требований с параметром λ. Если в накопителе имеется уже m тре- бований, то очередное требование получает отказ. Время обслуживания прибо- ром каждой партии требований, поступивших с накопителя, подчиняется пока- зательному закону с параметром μ. Моменты поступления партий накопивших-
51
ся требований на обслуживающий прибор являются случайными. В этом случае вероятность pk того, что в накопителе при установившемся режиме имеется ровно k требований, можно определить по формуле
ì |
|
ak |
|
|
|
,k < m; |
|
ï |
|
|
|
|
|||
(a + |
1) |
k+1 |
|||||
ï |
|
|
(3.19) |
||||
pk = í |
|
a |
m |
|
|
||
ï |
|
|
|
|
,k = m, |
||
|
|
|
|
|
|||
|
(a + 1) |
m |
|||||
î |
|
|
|
|
|||
ï |
|
|
|
|
|
|
|
где α = λ / μ . Очевидно, величина pm равна вероятности отказа.
Зная вероятности pk , легко находим среднее число М требований, нахо- дящихся в накопителе:
m |
|
M = åkpk . |
(3.20) |
k =1 |
|
Если M << m , то это значит, что загрузка накопителя слабая. |
|
Пример. В некотором музее имеется только один экскурсовод, который обслуживает группы туристов, состоящие не более чем из 10 человек. Среднее время обслуживания группы туристов этим экскурсоводом составляет 20 мин. Туристы приходят в музей в случайные моменты времени в среднем 30 человек в час и ждут, пока не освободится экскурсовод, если число ожидающих тури- стов менее 10, или уходят, если нет возможности попасть в музей с ближайшей группой.
|
Здесь |
α = λ / μ = 30 / 3 = 10. |
Следовательно, по |
формулам |
(3.19), |
(3.20) |
||||||||
имеем: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k |
0 |
1 |
2 |
3 |
|
4 |
5 |
6 |
|
7 |
8 |
|
9 |
10 |
pk |
0,091 |
0,083 |
0,075 |
0,068 |
|
0,062 |
0,056 |
0,052 |
|
0,047 |
0,042 |
|
0,038 |
0,386 |
10
и M = åkpk = 6,14. Это означает, что в среднем 38,6% туристов не попадают в
k =1
музей, а среднее число ожидающих туристов равно 6,14. Если среднее время обслуживания группы туристов сократить, скажем, вдвое, то p10 = 0,162, т. е.
только 16,2% туристов не попадут в музей.
3.6. Системы со смешанным потоком требований
До сих пор мы рассматривали системы массового обслуживания с един- ственным входящим потоком требований. Однако на практике весьма распро- странены системы массового обслуживания с двумя, тремя и более независи- мыми входящими потоками требований. Такие системы называются системами со смешанным потоком требований. Простейшая система массового обслужи- вания со смешанным потоком требований, для которой полностью разработан математический аппарат, функционирует следующим образом. В систему, со- стоящую из одного обслуживающего прибора, поступают независимо друг от друга два пуассоновских потока требований; первый с интенсивностью l1, а второй — l2. Застав прибор занятым, требование из первого потока становится
52
в очередь, а из второго потока покидает систему необслуженным. Время об- служивания требований из обоих потоков подчиняется показательному закону.
Рассмотрим более интересный случай, когда требования обоих потоков должны быть в конечном счете обслужены, причем требования первого потока имеют абсолютный приоритет в обслуживании. Это означает следующее: если при поступлении требования из любого потока прибор свободен, то это требо- вание начинает немедленно обслуживаться; если же прибор занят, то требова- ние из второго потока становится в очередь в любом случае, а требование из первого, т. е. приоритетного потока, — только при наличии ранее поступивших необслуженных требований из первого потока, включая сюда и требование, на- ходящееся на обслуживании. Если же таковых нет и, стало быть, в очереди сто-
ят только требования из второго потока и на обслуживании находится также требование из второго потока, то это требование снимается с обслуживания не- зависимо от того, сколько времени оно там находилось, и начинает обслужи- ваться требование из первого (приоритетного) потока. После освобождения прибора на обслуживание поступает то требование приоритетного потока (если таковое имеется), время ожидания которого наибольшее. Требования из второ- го потока поступают на обслуживание только при условии, если нет ожидаю- щих требований приоритетного потока. При этом среди требований второго по- тока соблюдается обычная дисциплина очереди: «Первым пришел, первым и поступай на обслуживание». В частности, первым на обслуживание поступает то требование из второго потока, обслуживание которого было прервано появ- лением требования из приоритетного потока.
Заметим, что система с относительным приоритетом в обслуживании от- личается от рассматриваемой системы с абсолютным приоритетом в обслужи- вании только тем, что требование из приоритетного потока, застав прибор заня- тым обслуживанием требования из второго (неприоритетного) потока, ждет окончания его обслуживания. Например, хотя в билетной кассе инвалиды вой- ны пропускаются вне очереди, процесс продажи билетов очередному пассажи- ру не прерывается при появлении инвалида.
Естественно считать, что в общем случае среднее время обслуживания требований из разных потоков неодинаково. Обозначим через 1/ μ1 среднее
время обслуживания требований, имеющих абсолютный приоритет, а через 1/ μ2 — аналогичную величину для требований из второго (неприоритетного)
потока.
Для рассматриваемой системы массового обслуживания представляет ин- терес M1' —среднее число требований из приоритетного потока, находящихся в очереди; M 2'' — среднее число требований из неприоритетного потока, нахо- дящихся в системе, θ'ож — среднее время ожидания в очереди требования из приоритетного потока, θ'ож' — среднее время ожидания в очереди требования из
неприоритетного потока.
Если выполняется условие α1 + α2 < 1, где α1 = λ1 / μ1 , α2 = λ2 / μ2 , то
для установившегося режима справедливы формулы
53
M ' |
|
|
a2 |
M '' |
|
|
|
|
a |
2 |
|
|
|||
= |
|
1 |
; |
= |
|
|
|
|
|
|
|||||
|
1 |
- a1 - a2 |
|||||||||||||
1 |
|
1- a1 |
|
2 |
|
|
|||||||||
|
|
|
qож |
= |
M ' |
; |
qож |
= |
M '' |
||||||
|
|
' |
|
|
|
1 |
|
|
|
'' |
|
|
2 |
|
|
|
|
|
|
|
|
l1 |
|
|
|
|
|
|
l2 |
|
æ |
|
m2 |
|
a1 |
ç |
+ |
|
|
|
|
|
|
||
ç1 |
m1 |
1- a1 |
||
è |
|
- 1 . m2
ö
÷;
÷
ø
(3.21)
Пример. Обувная мастерская с одним мастером осуществляет обычный и срочный (в присутствии заказчика) ремонт обуви. При поступлении заказа на срочный ремонт обычный ремонт прерывается. В среднем в час поступает одна пара обуви на срочный ремонт и три пары обуви на обычный ремонт. На обыч- ный ремонт одной пары мастер затрачивает в среднем 15 мин, а на срочный
(обычно мелкий) — 3 мин. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Здесь |
λ1 = 1; λ2 |
= 3; |
|
|
|
|
μ1 = 20 ; |
|
|
μ2 = 4 |
и, |
следовательно, |
||||||||
α1 = 1/ 20 = 0,05; α2 = 3 / 4 = 0,75. Так как α1 |
+ α2 = 0,05 + 0,75 < 1, то по фор- |
|||||||||||||||||||
мулам (3.21) находим: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
M1' = |
|
0,052 |
|
= 0,0026; |
|
|
|
||||||||||
|
|
1- 0,05 |
|
|
|
|||||||||||||||
|
|
0,75 |
|
|
|
0,05 |
|
|
|
|||||||||||
|
'' |
æ |
|
|
4 |
|
ö |
|
|
|||||||||||
|
M 2 = |
|
|
|
|
|
|
|
|
ç1 |
+ |
|
|
|
÷ |
= 3,8 ; |
|
|||
|
1- 0,05 - |
|
|
|
20 1 - 0,05 |
|
||||||||||||||
|
|
0,75 è |
|
|
ø |
|
|
|||||||||||||
|
|
|
q'ож |
= |
0,0026 |
ч » 0,16 мин; |
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
3,8 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
q''ож = |
|
- |
1 |
=1,02ч » 61 мин. |
|
|
||||||||||||
|
|
3 |
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
Таким образом, для срочного ремонта среднее время ожидания в очереди составляет 0,16 мин (т. е. практически никакой очереди нет), а для обычного —
61 мин.
3.7. Системы с ненадежными обслуживающими приборами
На практике встречаются системы массового обслуживания, в которых каждое требование, проходящее через обслуживающий прибор, обслуживается не достоверно, а с некоторой вероятностью p. Если подобная система есть сис- тема с отказами, состоящая из п однотипных приборов со средним временем обслуживания 1 / μ , на которую поступает поток требований с интенсивностью
l, то вместо классической формулы Эрланга |
|
|
|||||
pобсл |
=1 − pотк , |
(3.22) |
|||||
где |
|
|
|
|
|
−1 |
|
pотк = a |
n é n |
a |
k |
ù |
|
||
|
êå |
|
ú |
, |
α = λ / μ, |
||
|
k! |
||||||
n! ëk =0 |
û |
|
|
||||
имеем |
|
|
|
|
|
|
|
pобсл' |
= pобсл × p . |
(3.23) |
Действительно, вероятность pобсл' того, что требование будет обслужено по теореме умножения вероятностей независимых событий, равна произведе-
54
нию вероятности pобсл того, что требование будет принято к обслуживанию, на вероятность p обслуживания этого требования.
Таким образом, при p < 1 вероятность обслуживания и, следовательно,
пропускная способность системы уменьшаются по сравнению с рассмотренным в п. 2.1 классическим случаем p = 1.
Пример. В ателье проката имеется восемь полотеров, каждый из которых берется на прокат в среднем на два дня. В среднем в ателье за полотерами об- ращаются пять человек в день. Вероятность того, что взятый на прокат полотер будет исправно работать, равна 0,95.
Здесь n = 8;λ = 5 ; μ = 0,5; p = 0,95, откуда по формулам (3.22), (3.23) на-
ходим pобсл' = 0,76; pобсл = 0,76 × 0,95 = 0,73. Таким образом, ателье проката в среднем на 73% обеспечивает население полотерами. Если бы эти полотеры время от времени не выходили из строя, то население было бы обеспечено ими на 76%.
Рассмотрим теперь такие системы массового обслуживания, в которых отказавшие приборы ремонтируются в процессе функционирования системы. Пусть в систему массового обслуживания, состоящую из n однотипных прибо- ров, поступает пуассоновский поток требований с интенсивностью λ. Время обслуживания требований каждым прибором подчиняется показательному за- кону с параметром μ. Приборы в случайные моменты времени выходят из строя как тогда, когда они свободны, так и тогда, когда они заняты обслуживанием требования. Неисправные приборы сразу же поступают в ремонт, так что вме- сто того, чтобы обслуживать, эти приборы сами начинают обслуживаться. Вре-
мя работы каждого прибора случайно и подчиняется показательному закону с параметром γ. Одновременно в ремонте может находиться только один прибор, так что если имеются другие неисправные приборы, то они стоят в очереди. Отремонтированные приборы могут также выходить из строя. Суммарный по- ток отказов еще не ремонтированных и ремонтированных (возможно много- кратно) приборов предполагается пуассоновским с параметром q. Если прибор отказал во время обслуживания требования, то это требование теряется (даже, если имеются свободные исправные приборы).
Рассмотрим сначала систему с отказами. В этом случае требование теря- ется, если в момент его поступления в систему нет ни одного свободного ис- правного прибора. Если имеется только один прибор ( n = 1), то для такой сис-
темы в случае установившегося режима справедливы формулы: |
|
|
|
|
|||||||||
π1 = |
q |
; π2 |
= 1− π1 ; p1 |
= |
|
|
λλ |
= 1− p1 , |
p |
' |
= p1 |
+ p1 ; |
|
|
|
|
|
; p0 |
|
||||||||
q + γ |
(λ + q)(μ + q)+ γλ |
|
|||||||||||
|
|
|
p'' |
= |
qp1 |
; pотк = p' + p'' , |
|
|
|
|
(3.24) |
||
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
λ |
|
|
|
|
|
где π1— вероятность того, что прибор неисправен; π0 —вероятность того, что прибор исправен; p1— вероятность того, что прибор занят обслуживанием; p0 — вероятность того, что прибор свободен; p' — вероятность того, что прибор либо
55
неисправен, либо занят обслуживанием; p" — вероятность того, что требование покинет систему не полностью обслуженным из-за выхода из строя прибора; pотк — вероятность отказа в обслуживании.
Пример. В случайные моменты времени к моечной установке подъезжают в среднем четыре автомашины в час. Средняя производительность моечной ус- тановки составляет 10 автомашин в час. В случайные моменты времени моеч- ная установка выходит из строя в среднем два раза за 100 ч работы. Иными словами, среднее время наработки моечной установки на один отказ равно 50 ч. Время, необходимое для ремонта моечной установки, случайное и составляет в среднем 1 ч. Если автомашина подъезжает к моечной установке в тот момент, когда установка занята или находится в ремонте, то она уезжает невымытой.
Здесь λ = 4; μ = 10 ; q=0,02; γ = 1, из формул (3.24) находим: |
|
||||||||||||
p |
|
= |
|
0,02 |
= 0,020; |
p |
= |
|
4 ×1 |
|
|
= 0,281; |
|
|
1+ 0,02 |
(1+ 0,02)(10 + 0,02)+1× 4 |
|
||||||||||
|
1 |
|
|
1 |
|
|
|
||||||
|
|
|
|
p' = 0,281+ 0,020 = 0,301; p'' |
= |
0,02 × 0,281 |
= 0,001; |
||||||
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
pотк |
= 0,301 + 0,001= 0,302. |
|
|
|
Отсюда следует, что в среднем 30,2% автомашин не будут вымыты моеч- ной установкой. Из них только 0,1% — по причине выхода из строя моечной установки во время мойки. Это указывает на то, что узким местом здесь являет- ся не плохая надежность моечной установки, а ее перегруженность.
Перейдем теперь к другому варианту рассматриваемой системы с нена- дежными приборами — к системе с ожиданием. В этом случае требование не теряется, а становится в очередь, если в момент его поступления в систему нет ни одного исправного прибора. Очевидно, эта система может быть как с огра- ничением на длину очереди и время пребывания в очереди или системе, так и без ограничений. Для определенности рассмотрим случай с ограничением на длину очереди, когда в очереди имеется только m мест. Так как формулы для произвольных n и m громоздки, то приведем формулы только для частного слу-
чая n = 1, m = 2 и установившегося режима: |
|
|
|
|
|
|
|
|
|
|||||||||||
p0 = |
1 |
|
|
|
|
|
|
|
|
|
l |
|
|
|
|
|
g |
|
||
|
|
|
|
; |
w = |
|
; p0 |
= |
|
; |
|
|||||||||
1+ w + w2 + w3 |
(m + q)p0 |
(q + g) |
|
|||||||||||||||||
|
|
p = ωp |
0 |
; p |
2 |
= ω2 p |
0 |
; p |
3 |
= ω3 p |
0 |
; |
|
|
|
|||||
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
M = (p1 + p2 + p3 )π0 ; M 2 = M + p2 + 2 p3 ; |
(3.25) |
||||||||||||||||||
|
|
p'' |
= |
qM |
; pотк = p3 |
+ p'' . |
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
l |
|
|
|
|
|
|
|
|
|
|
|
|
|
Здесь p0— вероятность того, что прибор свободен; p1 - вероятность того, что прибор занят и очередь отсутствует; p2 - вероятность того, что прибор занят и имеется одно требование в очереди; p3 - вероятность того, что прибор занят и имеются два требования в очереди; М - среднее число требований, находящих- ся на обслуживании; M 2 - среднее число требований, находящихся в системе;
π0 , pотк , p'' имеют тот же смысл, что и для системы с отказами.
56