Системы массового обслуживания (90
..pdf
заявки), ..., S1+m (канал занят, в очереди т заявок). Размеченный граф состояний имеет следующий вид:
Так как число состояний конечно, то существуют предельные
вероятности: |
р , |
р |
|
р |
|
р |
|
, |
р |
|
|
|
р р |
|
2 |
р |
|
, |
|
0 |
1 |
|
|
0 |
|
0 |
|
1 |
1 |
|
|
1 |
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
р1 2
р1 k
|
|
р2 2 р |
|
3 |
р0 и т.д. |
р |
|
1 k р |
|
, k = 0, 1, 2, … m. |
||||
|
0 |
k |
0 |
|||||||||||
|
|
|
|
1 |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Вероятность того, что канал свободен р |
|
|
1 |
. |
|||||||||
|
1 |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
0 |
m 2 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Тогда вероятность состояния S1+k (канал занят, в очереди k заявок) равна
1 k р0 1 k |
1 |
|
, где k = 0, 1, 2, … m. |
|
1 m 2 |
||||
|
|
|||
|
Вероятность отказа (канал |
занят, в очереди |
нет свободных |
мест) |
||||||||||
р р |
|
1 т |
|
1 |
. |
|
|
|
|
|
|
|
||
т |
|
|
|
|
|
|
|
|
|
|||||
отк |
1 |
1 |
m |
2 |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|||||
|
Относительная |
пропускная |
способность Q 1 р |
|
1 1 т |
|
1 |
|
. Это |
|||||
|
отк |
|
m 2 |
|||||||||||
|
|
|
|
|
|
|
|
|
1 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
||||
вероятность того, что заявка будет обслужена.
|
|
|
|
1 |
|
Абсолютная пропускная способность |
А Q 1 |
1 |
т |
|
|
|
|||||
|
|
|
|
. |
|
|
|
|
|
1 m 2 |
|
Среднее число заявок в очереди Lоч 2 1 т (т 1 т ) .
(1 т 2)(1 )
Среднее время пребывания заявки в очереди Точ = Lоч/λ.
Среднее число заявок, находящихся под обслуживанием (среднее число занятых каналов) Lобсл= 0 × р0 + 1 × (1 – р0) = 1 – р0.
Тогда среднее число заявок в системе Lсист = Lоч + Lобсл.
Отсюда среднее время пребывания заявки в системе Тсист = Lсист/λ.
7. Многоканальная СМО с ограниченной очередью
СМО содержит п обслуживающих каналов. На вход поступает простейший поток заявок с интенсивностью λ. Если в момент поступления требования имеется свободный канал, то он немедленно приступает к обслуживанию поступившего требования. Каждый канал может одновременно обслуживать только одно требование. Все каналы функционируют независимо.
Если заявка застала все обслуживающие каналы занятыми, то она встает в очередь и ожидает начала обслуживания. Число мест в очереди ограничено и равно т. Если заявка застала все обслуживающие каналы занятыми и в очереди нет свободных мест, то она покидает систему необслуженной.
Время обслуживания заявки есть случайная величина, которая подчиняется экспоненциальному закону распределения с параметром µ.
Среднее время обслуживания одной заявки tобсл = 1/μ.
Возможные состояния СМО: S0 (все каналы свободны), S1 (один канал занят, остальные свободны), S2 (два канала заняты, остальные свободны), ..., Sn
(все каналы заняты), Sn+1 (все каналы заняты, в очереди одна заявка), Sn+2 (все каналы заняты, в очереди две заявки), ..., Sn+т (все каналы заняты, в очереди т заявок).
Приведенная интенсивность потока заявок ρ = λ/µ. Размеченный граф
|
λ |
λ |
λ |
… |
λ |
λ |
λ |
λ |
… |
S0 |
|
S1 |
S2 |
Sn-1 |
Sn |
Sn+1 |
|
||
|
… |
|
… |
||||||
|
μ |
2μ |
3μ |
|
(n-1)μ |
nμ |
nμ |
nμ |
|
… |
λ |
λ |
|
|
|
|
|
|
|
|
Sn+m-1 |
Sn+m |
|
|
|
|
|
|
|
… |
nμ |
|
|
|
|
|
|
||
|
nμ |
|
|
|
|
|
|
|
состояний имеет следующий вид:
|
|
|
|
|
|
2 |
р |
0 |
1 |
|
|
|
|
|
|
|||||
|
|
|
1! |
|
2! |
|
|
|
|
|
|
|
|
n 1 |
|
|
n |
|
1 ( / n) |
m 1 |
1 |
|
... |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
||||
|
(n 1)! |
n! |
|
1 / n |
|
|||||
|
|
|
||||||||
n1 |
k |
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k 0 |
k! |
|
n! |
|
|
1 ( / n)m 1 1 |
|
|
|
|
|
1 / n |
. |
|
|
Вероятность того, что в системе находится k требований, в случае, когда
их число не превосходит числа каналов обслуживания, равна рk k
k!
k = 1, 2, … n. |
|
|
|
|
|
||||
|
|
Вероятность |
того, |
что в очереди находится k требований, |
равна |
||||
|
|
|
n |
|
|
|
|
|
|
р |
|
|
|
( / n)kp0 , где k = 1, 2, … т. |
|
||||
|
|
|
|||||||
n k |
|
|
n! |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
ротк pn m |
n m |
|
|
|
|
Вероятность |
отказа |
|
p0 (все обслуживающие |
каналы |
|||
|
|
nm n! |
|||||||
заняты, в очереди нет свободных мест).
Вероятность того, что все обслуживающие каналы заняты,
рзан n 1 ( / n)m 1 р0 . n! 1 / n
Относительная пропускная способность Q = 1 – ротк. Это вероятность того,
что заявка будет обслужена.
Абсолютная пропускная способность А = λQ.
Среднее число свободных от обслуживания каналов равно
|
|
|
n |
|
|
|
|
N 0 np0 (n 1) p1 (n 2) p2 ... 1 pn 1 (n k)pk . |
|
|
|||||
|
|
|
k 0 |
|
|
|
|
Среднее число заявок в очереди равно |
Lоч |
n 1 p0(1 ( / n)n (т 1 т / n)) |
. |
||||
n n!(1 / n)2 |
|
||||||
|
|
|
|
|
|
|
|
Среднее число заявок под обслуживанием (среднее число |
занятых |
||||||
|
n m |
|
|
|
|
|
|
каналов) Lобсл 1 |
|
p0 |
. |
|
|
|
|
|
|
|
|
|
|||
|
n m n! |
|
|
|
|
|
|
Тогда среднее число заявок в системе Lсист = Lоч + Lобсл.
8. Замкнутая СМО
СМО содержит п обслуживающих каналов. На вход поступает простейший поток заявок с интенсивностью λ. Если в момент поступления требования имеется свободный канал, то он немедленно приступает к обслуживанию поступившего требования. Каждый канал может одновременно обслуживать только одно требование. Все каналы функционируют независимо.
Если заявка застала все обслуживающие каналы занятыми, то она встает в очередь и ожидает начала обслуживания. Требования на обслуживание поступают от т обслуживаемых объектов, то есть поток поступающих требований ограничен.
Время обслуживания заявки есть случайная величина, которая подчиняется экспоненциальному закону распределения с параметром µ.
Среднее время обслуживания одной заявки tобсл = 1/µ.
Существует взаимосвязь между длиной очереди и темпом поступления заявок: чем длиннее очередь на обслуживание, тем ниже темп поступления новых заявок.
9. СМО с ограниченным временем ожидания
Предполагается, что заявка может находиться в очереди случайное время, которое подчиняется экспоненциальному закону распределения с параметром v, то есть v – среднее количество требований, покидающих очередь в единицу времени, вызванное появлением в очереди одного требования. Среднее время ожидания в очереди tожидания = 1/v.
СМО содержит п обслуживающих каналов. На вход поступает простейший поток заявок с интенсивностью λ. Если в момент поступления требования имеется свободный канал, то он немедленно приступает к обслуживанию поступившего требования. Каждый канал может одновременно обслуживать только одно требование. Все каналы функционируют независимо.
Если заявка застала все обслуживающие каналы занятыми, то она встает в очередь и ожидает начала обслуживания.
Время обслуживания заявки есть случайная величина, которая подчиняется экспоненциальному закону распределения с параметром µ.
Среднее время обслуживания одной заявки tобсл = 1/µ.
Возможные состояния СМО: S0 (все каналы свободны), S1 (один канал занят, остальные свободны), S2 (два канала заняты, остальные свободны), ..., Sn
(все каналы заняты), Sn+1 (все каналы заняты, в очереди одна заявка), Sn+2 (все каналы заняты, в очереди две заявки) и т.д. Размеченный граф состояний имеет
|
λ |
λ |
λ |
λ |
… |
λ |
λ |
λ |
S0 |
|
S1 |
S2 |
S3 |
|
Sn-1 |
Sn |
|
|
… |
|
||||||
|
μ |
2μ |
3μ |
4μ |
|
(n-1)μ |
nμ |
nμ+v |
λ |
|
λ |
λ |
λ |
… |
|
|
|
|
Sn+1 |
nμ+2v Sn+2 |
nμ+3v Sn+3 |
|
|
|
|
|
nμ+v |
nμ+4v |
… |
|
|
|
следующий вид:
Примеры решения задач
Пример 1. Одноканальная телефонная линия. Заявка-вызов, поступившая в момент, когда линия занята, получает отказ. Простейший поток заявок поступает с интенсивностью λ = 50 звонков/ч. Время обслуживания заявки есть случайная величина, которая подчиняется экспоненциальному закону распределения. Средняя продолжительность разговора tобсл = 3 мин.
Определите показатели эффективности работы СМО.
Решение. Данная телефонная линия – это одноканальная СМО с отказами. Время обслуживания tобсл = 3 мин = 3/60 ч = 0,05 ч. Тогда интенсив-
50
S0 
S1
20
ность обслуживания μ = 1/tобсл = 1/0,05 = 20 звонков/ч. Размеченный граф состояний имеет следующий вид:
р0 – предельная вероятность состояния S0, р1 – предельная вероятность состояния S1. Состояние S1 связано с состоянием S0 двумя стрелками с
интенсивностями 50 и 20, тогда р1 5020 р0 2,5 р0 .
Так как р0 + р1 = 1, то 1 = р0 + 2,5 р0 = 3,5 р0. Отсюда р0 = 1/3,5 ≈ 0,286. Тогда
р1 = 2,5р0 ≈ 0,714.
Вероятность отказа ротк – это вероятность того, что линия занята, то есть предельная вероятность состояния S1. Поэтому ротк =р1 ≈ 0,714.
Относительная пропускная способность Q = 1 – ротк = 1 – 0,714 = 0,286.
Это вероятность того, что заявка будет обслужена.
Абсолютная пропускная способность А = λQ = 50×0,286 = 14,3 звонка/ч, то есть в среднем в час СМО обслуживает 14,3 звонка.
Таким образом, получаем, что номинальная пропускная способность телефонной линии μ = 20 звонков/ч отличается от абсолютной пропускной способности А = 14,3 звонка/ч из-за случайного характера потока звонков и случайности времени обслуживания.
Пример 2. Трехканальная телефонная линия. Заявка-вызов, поступившая в момент, когда все п = 3 канала заняты, получает отказ. Простейший поток заявок поступает с интенсивностью λ = 60 звонков/ч. Время обслуживания заявки есть случайная величина, которая подчиняется экспоненциальному закону распределения. Средняя продолжительность разговора tобсл = 3 мин.
Определите показатели эффективности работы СМО.
Решение. Данная телефонная линия – это многоканальная СМО с отказа-
ми. tобсл = 3 мин = 3/60 ч = 0,05 ч. Тогда интенсивность обслуживания μ = 1/tобсл =
=1/0,05 = 20 звонков/ч. Приведенная интенсивность потока заявок ρ = λ/μ =
=60/20 = 3. Размеченный граф состояний имеет следующий вид:
|
|
|
|
|
|
|
|
|
|
|
|
|
λ |
|
|
λ |
|
|
|
|
λ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S0 |
μ |
S1 |
|
2μ |
S2 |
|
|
3μ |
|
S3 |
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
р |
р |
|
р |
|
3 р |
|
, |
р |
|
|
|
р1 |
|
р |
3 |
р |
|
4,5 р |
|
, |
р |
|
|
|
р |
|
|
|
р |
|
|
3 |
4,5 р |
|
4,5 р |
|
|
0 |
0 |
0 |
2 |
|
|
|
0 |
0 |
3 |
|
2 |
|
2 |
|
0 |
0 |
|||||||||||||||||||||
1 |
|
|
|
|
|
|
|
2 |
2 |
1 |
2 |
|
|
|
|
|
3 |
|
3 |
|
|
3 |
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
Так как р0 + р1 + р2 + р3 = 1, то 1 = р0 + 3р0 + 4,5р0 + 4,5р0 = 13р0. Отсюда р0 = 1/13 ≈ 0,077 (вероятность того, что все обслуживающие каналы свободны).
Тогда р1 = 3р0 = 0,231; р1 = 4,5р0 ≈ 0,346; р3 = 4,5р0 ≈ 0,346. Мы нашли вероятности того, что в системе k требований, где k = 0, 1, 2, 3.
Вероятность отказа ротк – это вероятность того, что все каналы заняты, то есть предельная вероятность состояния S3. Поэтому ротк = р3 ≈ 0,346.
Относительная пропускная способность Q = 1 – ротк = 1 – 0,346 = 0,654. Это вероятность того, что заявка будет обслужена.
Абсолютная пропускная способность А = λQ = 60×0,654 = 39,24 звонка/ч,
то есть в среднем в час СМО обслуживает 39,24 звонка.
Среднее число свободных от обслуживания каналов N0 есть математическое ожидание числа свободных каналов, то есть число свободных каналов в каждом состоянии надо умножить на предельную вероятность этого состояния и полученные произведения сложить:
N0 = 3×р0 + 2×р1 + 1×р2 + 0×р3 = 3×0,077 + 2×0,231 + 1×0,346 + 0×0,346 = 1,039.
Коэффициент простоя каналов Кпр = N0/n = 1,039/3 ≈ 0,346.
Среднее число занятых обслуживанием каналов Nзан = А/μ = λQ/μ = ρQ = = 3×0,654 = 1,962. Таким образом, из-за ошибок округления n = N0 + Nзан = = 1,039 + 1,962 = 3,001.
Коэффициент загрузки каналов Кзан = Nзан/n = 1,962/3 = 0,654.
Пример 3. Первый магазин с одним продавцом, второй магазин с двумя продавцами. Предполагается, что в обоих случаях простейший поток покупателей поступает с интенсивностью λ = 20 человек/ч. Время обслуживания заявки – случайная величина, которая подчиняется экспоненциальному закону распределения с параметром μ = 25 человек/ч.
Определите:
–среднее время пребывания покупателя в очереди;
–среднюю длину очереди;
–среднее число покупателей в магазине;
–среднее время пребывания покупателя в магазине;
–вероятность того, что в магазине не окажется покупателей;
–вероятность того, что в магазине окажется ровно 4 покупателя.
Решение №1. Магазин с одним продавцом – одноканальная СМО с неограниченной очередью. Размеченный граф состояний имеет следующий
λ |
λ |
|
λ |
… |
S0 |
S1 |
S2 |
|
|
μ |
… |
|||
μ |
μ |
|
|
вид:
Так как ρ = λ/μ = 20/25 = 0,8 < 1, то существуют предельные вероятности.
Вероятность того, что в магазине не окажется покупателей, равна
р0 = 1 – ρ = 1 – 0,8 = 0,2.
Вероятность того, что в магазине окажется ровно 4 покупателя, равна
р4 = ρ4р0 = 0,84 × 0,2 = 0,082.
Средняя длина очереди Lоч |
|
2 |
|
0,82 |
3,2 . |
|
|
|
|||
1 |
|
1 0,8 |
|||
Среднее время пребывания покупателя в очереди
Точ = Lоч/λ = 3,2/20 =0,16 ч = 0,16 × 60 мин = 9,6 мин.
Среднее число покупателей в магазине Lсист |
|
|
0,8 |
4 . |
|
|
|||
1 |
1 0,8 |
Среднее время пребывания покупателя в магазине
Тсист = Lсист/λ = 4/20 = 0,2 ч = 0,2 × 60 мин = 12 мин.
Решение №2. Магазин с двумя продавцами – это двухканальная СМО с
|
λ |
λ |
λ |
|
λ |
S0 |
S1 |
|
S2 |
S3 |
S4 |
|
μ |
2μ |
2μ |
|
2μ |
неограниченной очередью. Размеченный граф состояний имеет следующий вид:
Так как р/п = 0,8/2 = 0,4 < 1, то существуют предельные вероятности.
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
3 |
|
|
|
|
n |
|
n |
|
|
|
|
1 |
|
2 |
|
2 |
|
|
|
|
1 |
|||||||||||||
|
|
|
|
р |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
... |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
2! |
|
|
|
3! |
|
|
|
|
|
|
n! |
|
|
|
|
|
|
|
|
2! |
|
2! 2 |
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n! n |
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
0,82 |
|
|
0,82 |
|
|
|
|
0,8 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
1 |
0,8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,429 . |
Это вероятность |
|
того, |
что |
в магазине не |
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
2! |
|
|
2! |
|
2 |
0,8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
окажется покупателей. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
Вероятность того, что в магазине окажется ровно 4 покупателя (то есть 2 |
|||||||||||||||||||||||||||||||||||||||||||||||
покупателя |
обслуживаются |
|
и |
еще |
2 |
покупателя |
в очереди), равна |
|||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
2 |
n |
|
|
|
|
|
|
|
|
|
|
0,8 2 0,82 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
р |
|
|
|
|
|
|
|
|
p |
0 |
р |
2 |
2 |
|
|
|
|
|
|
|
0,429 0,022 . |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||
n 2 |
n |
n! |
|
|
|
|
|
|
|
2 |
2! |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
Средняя длина очереди Lоч |
|
|
n 1 |
|
|
|
0,82 1 |
|
|
|
0,429 0,153 . |
||||||||||||||||||||||||||||||||||||
|
|
|
|
p0 |
|
|
|
|||||||||||||||||||||||||||||||||||||||||||
|
|
|
(n 1)!(n )2 |
|
(2 1)!(2 0,8)2 |
|||||||||||||||||||||||||||||||||||||||||||||
Среднее время пребывания покупателя в очереди Точ = Lоч/λ = 0,153/20 ≈ ≈ 0,008 ч = 0,008 × 60 мин = 0,48 мин.
Среднее число покупателей в магазине Тсист= Lоч + ρ = 0,153 + 0,8 = 0,953.
Среднее время пребывания покупателя в магазине Тсист = Lсист/λ = |
= |
0,953/20 ≈ 0,048 ч = 0,048 × 60 мин = 2,88 мин. |
|
Пример 4. На склад для разгрузки поступает простейший поток грузовиков с интенсивностью λ = 6 грузовиков/ч. Разгрузка одного грузовика занимает tобсл = 6 мин = 0,1 ч. Найдите параметры этой одноканальной СМО с фиксированным временем обслуживания.
Решение. Интенсивностьобслуживания µ = 1/tобсл = 1/0,1 = 10 грузовиков/ч.
Средняя длина очереди Lоч |
2 |
62 |
0,45 грузовика. |
|
|
|
|
|
|
||
2( ) |
2 10(10 6) |
|
|||
Среднее время ожидания в очереди Точ = Lоч/λ = 0,45/6 = 0,075 ч = |
= |
||||
0,075×60 мин = 4,5 мин.
Среднее число грузовиков в системе Lсист = Lоч + λ/µ = 0,45 + 6/10= 1,05.
Среднее время пребывания грузовика на складе Тсист = Точ + tобсл = 4,5 + 6 =
= 10,5 мин.
Пример 5. Автозаправочная станция имеет п = 1 бензоколонку с площадкой, допускающей пребывание в очереди на заправку не более двух автомашин одновременно. Если в очереди находятся m = 2 автомашины, то очередная прибывшая автомашина проезжает мимо автозаправочной станции.
Предполагается, что простейший поток автомашин поступает на станцию с интенсивностью λ = 10 автомашин/ч. Время обслуживания заявки есть случайная величина, которая подчиняется экспоненциальному закону