Исследование операций / ИСО Учебник
.pdfСреднее число заявок в системе |
|
|
|
|
|
|
|
|
~ |
|
~ |
|
|
|
~ |
|
|
zs |
= r |
+ k . |
||||||
Среднее время обслуживания |
|
|
|
|
|
|
|
|
~ |
|
|
~ |
|
|
|
||
|
|
|
k |
|
|
|
||
tобс |
= |
|
λ . |
|||||
Среднее время в очереди |
|
|
|
|
|
|
|
|
~ |
|
~ |
|
|
|
|
||
|
|
r |
|
|
|
|||
tоч |
= |
|
|
. |
|
|||
|
λ |
|||||||
Среднее время в системе |
|
|
|
|
|
|
|
|
~ |
|
~ |
|
|
|
~ |
|
|
|
k |
|
|
|
|
r |
||
tсис |
= |
|
+ |
|
|
. |
||
λ |
|
λ |
||||||
Пример. На автозаправочной станции установлены три колонки. Около станции находится площадка на три машины для ожидания в очереди. На станцию прибывает в среднем две машины в минуту. Среднее время заправки одной машины минута. Требуется определить вероятность отказа и среднюю длину очереди.
Решение. Так как |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
~ |
|
|
|
|
|
= 1, ρ = |
2 |
= 2 , ω = |
2 |
<1, |
|||||||
n = 3, m = 3, λ = 2, tобс =1, то μ |
1 |
3 |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
а финальная вероятность равна |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
1− |
|
2 3 |
−1 |
|
|
|
|||||
|
|
|
|
22 |
|
23 |
|
24 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
||||||
p0 = |
1 |
+ 2 |
+ |
2! |
+ |
3! |
+ |
3 3! |
|
|
|
2 |
|
|
|
≈ 0,122 , |
|
|
|||
|
|
|
|
|
|
|
1− |
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
151
Вероятность отказа равна вероятности пребывания в последнем состоянии Sn+m=S6:
pотк = рm+n = |
ρm+n |
|
|
|
2 |
3 |
23 |
|
≈ 0,048. |
|
|
p |
0 |
= |
|
|
|
0.122 |
|||
nm n! |
3 |
3! |
||||||||
|
|
|
|
|
|
Средняя длина очереди
~ |
|
p0 |
ρn m |
i |
|
0.122 23 |
|
2 |
|
2 |
2 |
|
2 |
3 |
|
|
|
r |
= |
|
|
∑i ω |
|
= |
|
|
|
+ 2 |
|
|
+ 3 |
|
|
|
= 0,35. |
n! |
|
3! |
3 |
3 |
3 |
||||||||||||
|
|
i =1 |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Многоканальные системы массового обслуживания с ожиданием
Многоканальная система массового обслуживания S имеет n каналов и бесконечную очередь. На вход системы поступают заявки, при этом интенсивность входящего потока равна λ. Заявка, попадающая в систему S, начинает обслуживаться, интенсивность потока обслуживания равна μ. Если все каналы заняты обслуживанием заявок, вновь пришедшая заявка ставится в очередь. В этом случае СМО имеет бесконечное число состояний:
S0 — система свободна;
S1 — один канал занят, очереди нет;
S2 — два канала заняты, очереди нет; …;
Sn — все каналы системы заняты обслуживанием заявок, поступивших в систему, очереди нет;
Sn+1 — все каналы системы заняты и занято одно место в очереди; Sn+2 — все каналы системы заняты и заняты два места в очереди;
…
В этом случае СМО можно представить в виде графа состояний (рис. 2.14).
|
λ |
|
λ |
|
λ |
… λ |
|
λ |
|
λ |
|
λ … |
|
S0 |
S1 |
S2 |
Sn |
Sn+1 |
Sn+2 |
||||||||
|
|||||||||||||
|
μ |
|
2μ |
|
3μ |
nμ |
|
nμ |
|
nμ |
|
nμ |
|
|
|
|
|
|
|
Рис. 2.14. Размеченный граф состояний многоканальной СМО с бесконечной очередью
152
Финальные вероятности состояний
|
|
n |
ρi |
|
|
ρn+1 |
|
|
|
1 |
|
|
−1 |
ρ |
|
||||
|
p0 |
= ∑ |
|
|
+ |
|
|
|
|
|
|
|
|
|
|
при ω = |
|
<1, |
|
|
i! |
n n! |
1 |
− |
|
n |
|||||||||||||
|
|
i=0 |
|
|
|
ω |
|
|
|
|
|||||||||
|
ρk |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ρn+k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
pk = |
|
p0 , k =1,n , |
|
|
pn+k = |
|
p0 , |
1 ≤ k ≤ m . |
|||||||||||
k! |
|
|
n!nk |
||||||||||||||||
Вероятность отказа
pотк = 0.
Относительная пропускная способность
q = 1.
Абсолютная пропускная способность
A = λ.
Среднее число занятых обслуживанием каналов
~ = ρ k .
Среднее число заявок в очереди (ω <1)
~ |
ω p0 |
|
|
|
ρn+1 p0 |
|||
r = |
|
= |
|
|
|
|
. |
|
(1 −ω)2 |
n n!(1 −ω)2 |
|||||||
Среднее число заявок в системе |
|
|
|
|
|
|
|
|
|
~ |
~ |
~ |
|
||||
|
zs = r |
+ k . |
||||||
Среднее время обслуживания |
|
|
|
|
|
|
|
|
|
~ |
|
|
1 |
|
|
|
|
|
tобс = |
|
|
|
. |
|||
|
|
μ |
||||||
Среднее время в очереди |
|
|
|
|
|
|
|
|
|
~ |
|
|
~ |
|
|
|
|
|
|
|
|
r |
||||
|
tоч = |
|
|
. |
||||
|
|
λ |
||||||
153
Среднее время в системе
~ |
~ |
|
~ |
|
k |
|
r |
||
tсис = |
|
+ |
|
. |
λ |
λ |
|||
Одноканальные системы массового обслуживания с отказами
Одноканальная система массового обслуживания S состоит из одного канала. На вход системы поступают заявки, при этом интенсивность входящего потока равна λ. Заявка, попадающая в систему S, начинает обслуживаться, интенсивность потока обслуживания равна μ. Если канал занят обслуживанием заявок, вновь пришедшая заявка отклоняется. В этом случае СМО имеет два состояния:
S0 — система свободна,
S1 — система занята.
Графически СМО можно представить следующим образом (рис. 2.15).
λ
S0 
S1
μ
Рис. 2.15. Размеченный граф состояний одноканальной СМО с отказами
Финальные вероятности состояний
p |
|
= |
|
1 |
, p = |
ρ |
. |
|
1 + ρ |
1 + ρ |
|||||
|
0 |
|
1 |
|
|||
Вероятность отказа
pотк= p1 = 1 +ρρ .
Относительная пропускная способность
q=1 +1ρ .
154
Абсолютная пропускная способность
A = 1 +λρ .
Среднее число занятых обслуживанием каналов
~ |
|
ρ |
|
k |
= |
|
. |
1 + ρ |
|||
Среднее число заявок в очереди
r = 0 .
Среднее число заявок в системе
~ = ~ zs k .
Среднее время обслуживания системой
ts = λk .
Среднее время ожидания в очереди
tоч = 0 .
Пример. Известно, что заявки на телефонные переговоры в телевизионном ателье поступают с интенсивностью λ = 90 заявок в час, а средняя продолжительность переговоров по телефону составляет две минуты. Определить показатели эффективности работы СМО при наличие одного телефонного аппарата.
|
1 |
|
~ |
= 2(мин). Тогда |
Решение. По условию задачи имеем λ = 90 |
|
, |
t |
|
ч |
|
обс |
|
|
1 |
|
1 |
|
1 |
|
||
интенсивность потока обслуживания μ = |
~ |
= 0,5 |
|
|
= 30 |
|
. |
|
|
||||||
|
tобс |
|
мин |
ч |
|
||
155
Относительная пропускная способность СМО равна
q = 9030+30 = 0,25,
т. е. в среднем только 25 % поступающих заявок осуществляют переговоры по телефону. Вероятность отказа в этом случае равна 0,75.
Абсолютная пропускная способность СМО равна
A = 90 0,25 = 22,5 ,
т. е. в среднем в час будут обслужены 22,5 заявки на переговоры. Следовательно, при одном телефоне ателье плохо справляется с потоком заявок.
Одноканальные системы массового обслуживания с ограниченной длиной очереди
Одноканальная система массового обслуживания S имеет 1 канал и m мест в очереди. На вход системы поступают заявки, при этом интенсивность входящего потока равна λ. Заявка, попадающая в систему S, начинает обслуживаться, интенсивность потока обслуживания равна μ. Если канал занят, то вновь пришедшая заявка ставится в очередь ожидания обслуживания заявок. Если все места в очереди заняты, то вновь пришедшая заявка отклоняется. В этом случае СМО имеет m+2 состояние:
S0 — система свободна;
S1 — канал занят, очереди нет;
S2 — канал занят, занято одно место в очереди; …;
Sm+2 — канал и все места в очереди заняты.
Графически данную СМО можно изобразить так (рис. 2.16).
|
λ |
|
λ |
… |
λ |
|
|
S0 |
S1 |
Sm+1 |
|||||
|
|
|
|||||
|
|
|
|
||||
|
μ |
|
μ |
|
μ |
|
|
|
|
|
|
||||
|
|
|
|
Рис. 2.16. Размеченный граф состояний одноканальной СМО с ограниченною очередью
156
Финальные вероятности состояний
p0 |
= |
|
1 |
− ρ |
, |
pk = ρk p0 , k=1, 2,…m + 1. |
|
− |
ρm+2 |
||||
|
1 |
|
|
|||
Вероятность отказа
pотк = ρm+1 p0 .
Относительная пропускная способность
q=1− ρm+1 p0 .
Абсолютная пропускная способность
A = λ (1− ρm+1 p0 ).
Среднее число занятых обслуживанием каналов
~ |
|
ρ |
|
k |
= |
|
. |
1 + ρ |
|||
Среднее число заявок в очереди
r = ρ2 |
1− ρm (m +1− mρ) |
. |
||
1− ρm+2 |
) |
(1− ρ) |
||
|
( |
|
|
|
Среднее число заявок в системе
zs = k + r .
Среднее время обслуживания системой
ts = λz .
Среднее время ожидания в очереди
tоч = λr .
157
Пример. В частном стоматологическом кабинете работает один врач. В приемной этого врача имеется три кресла для ожидания. Подсчитать характеристики эффективности данной простейшей одноканальной СМО с тремя местами в очереди при условии, что интенсивность потока заявок равна четырем заявкам в час, а время обслуживания одной заявки — 30 минут. Выяснить, как эти характеристики изменятся, если увеличить число мест в очереди до четырех.
Решение. По условию задачи имеем
|
|
заявки |
(мин). |
|
λ = 4 |
|
|
, tобс = 30 |
|
|
||||
|
|
час |
|
|
Тогда интенсивность потока обслуживания
μ = |
1 |
= 2 |
|
заявки |
ρ = |
λ |
= 2 . |
||
|
|
|
, |
|
|||||
tобс |
час |
μ |
|||||||
|
|
|
|
|
|
||||
При m = 3 финальные вероятности будут равны
p = |
1 |
, |
, p |
|
= 16 . |
|
4 |
||||
0 |
31 |
|
|
31 |
|
|
|
|
|
Зная финальные вероятности, найдем характеристики эффективности системы массового обслуживания:
q ≈ 0.484,
A ≈1.93 заявкичас , k ≈ 0.968(каналов), r ≈ 2.19(заявки), z ≈ 3.16(заявки), tоч ≈ 0.55(час),
tсис ≈ 0.79(час).
При m = 4 финальные вероятности будут равны
p = |
1 |
, |
, p = 32 . |
|
|
||||
0 |
63 |
|
5 |
63 |
|
|
|
||
158
В этом случае характеристики эффективности СМО будут равны: q ≈ 0.493,
A ≈1.96 заявкичас , r ≈ 3.11(заявки), z ≈ 4.09(заявки), tоч ≈ 0.78(час), tсис ≈1,02(час).
Из полученных данных следует, что увеличение числа мест в очереди с трех до четырех приводит к незначительному увеличению абсолютной и относительной пропускной способности, но при этом происходит некоторое увеличение среднего числа заявок в очереди и в системе в целом, а также соответствующих средних времен.
Одноканальные системы массового обслуживания с ожиданием
Одноканальная система массового обслуживания S имеет бесконечную очередь. На вход системы поступают заявки, при этом интенсивность входящего потока равна λ. Заявка, попадающая в систему S, начинает обслуживаться, интенсивность потока обслуживания равна μ. Если канал занят обслуживанием заявок, вновь пришедшая заявка ставится в очередь. В этом случае СМО имеет бесконечное число состояний:
S0 — система свободна;
S1 — один канал занят, очереди нет;
S2 — канал занят, занято одно место в очереди;
…
Графически данную СМО можно представить таким образом (рис. 2.17).
λ λ λ
S0 |
S1 |
S2 |
… |
μ μ μ
Рис. 2.17. Размеченный граф состояний одноканальной СМО с бесконечной очередью
159
Финальные вероятности состояний
p0 =1− ρ , pk = ρk p0 ,k=1, 2,…
Вероятность отказа
pотк =0.
Относительная пропускная способность
q=1.
Абсолютная пропускная способность
A = λ .
Среднее число занятых обслуживанием каналов
k = ρ .
Среднее число заявок в очереди
|
r = |
ρ2 |
|
|
|
|
|
||
|
|
. |
|
|
|
|
|
||
|
1− ρ |
|
|
|
|
|
|||
Среднее число заявок в системе |
|
|
|
|
|
|
|
||
∞ |
∞ |
|
|
|
|
|
ρ |
|
|
zs = ∑k pk = (1− ρ)∑kρk , для ρ <1 |
zs = |
|
|
. |
|||||
1 |
− ρ |
||||||||
k =1 |
k =1 |
|
|
|
|
||||
Среднее время обслуживания системой ts = λ (1ρ− ρ) .
Среднее время ожидания в очереди
tоч = λ (ρ−2 ρ) .
1
160