Системи з очікуванням при необмеженому вхідному потоці
На n однакових каналів надходить найпростіший потік заявок інтенсивністю λ . Якщо в момент надходження заявки всі канали зайняті, то ця заявка стає в чергу і чекає на початок обслуговування. Час обслуговування кожної заявки є випадковою величиною, яка підпорядковується експоненційному закону розподілу з параметром μ .Розрахункові формули
Імовірність того, що всі канали вільні
Імовірність того, що зайнято kканалів, за умови, що загальна кількість заявок, що знаходяться на обслуговуванні, не перевищує числа каналів,
Імовірність того, що в системі знаходиться kзаявок, у разі, коли їх кількість більша за кількість каналів,
Імовірність того, що всі канали зайняті,
Середній час очікування заявкою початку обслуговування у системі
Середня довжина черги
Середня кількість вільних від обслуговування каналів
Автозаправна станція з двома колонками обслуговує пуасонівський потік машин з інтенсивністю λ=0,8 машин на хвилину. Час обслуговування однієї машини підпорядковується показовому закону із середнім значенням 2 хвилини. У даному районі немає іншої АЗС, тож черга перед АЗС може рости практично необмежено. Знайдіть:
1) середня кількість зайнятих колонок;
2) ймовірність відсутності черги біля АЗС;
3) ймовірність того, що доведеться чекати на початок обслуговування;
4) середня кількість машин у черзі;
5) середній час очікування у черзі;
6) середній час перебування машини на АЗС;
7) середня кількість машин на АЗС.
Рішення. За умовою задачі n=2, λ=0.8; μ=1/t обсл =0.5; ρ=λ/μ=1.6
Оскільки ρ /n=0,8<1, то очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы системы массового обслуживания.
Знаходимо ймовірність станів СМО:
Середня кількість зайнятих колонок:
N зан = n-N 0 = 2-(2 · p 0 +1 · p 1) = 2-2 · 0.1111 - 0.1778 = 1.6
Імовірність відсутності черги біля АЗС:
Імовірність того, що доведеться чекати початку обслуговування дорівнює ймовірності того, що всі колонки зайняті:
p 0 +p 1 +p 2 = 0.1111+0.1778+0.1422 = 0.4311
Середня кількість машин у черзі:
Середній час очікування у черзі:
Середній час перебування машини на АЗС:
t преб = t обсл + t ож = 2 +3.5556 = 5.5556 хв.
Середня кількість машин на АЗС:
N зан + L оч = 1.6 +2.8444 = 4.4444
Розглянемо одноканальну СМО з очікуваннями, в якій число каналів дорівнює одиниці n= 1, інтенсивність надходження заявок – λ, інтенсивність обслуговування дорівнює μ. Заявка, що надійшла на той час, коли канал зайнятий, стає у чергу і чекає обслуговування. Кількість місць у черзі обмежена і дорівнює m. Якщо всі місця в черзі зайняті, заявка залишає чергу не обслуженою. Проаналізуємо стан системи:
- S 0 – канал вільний;
- S 1 – канал зайнятий;
- S 2 – канал зайнятий, одна заявка у черзі;
- Sk– канал зайнятий, (k–1) заявок у черзі;
- Sm+ 1 – канал зайнятий, у черзі mзаявок.
Мал. 25
За формулами Ерланга знайдемо ймовірність подій, які полягають у тому, що СМО перебуває в стані S 1 , S 2 , …, S m+1: 
(28)
При цьому ймовірність того, що заявка, яка прибула до системи, знайде її вільною, дорівнює 
. (29)
Відношення інтенсивності надходження заявок до інтенсивності обслуговування заявок є наведена інтенсивність, тобто.
ρ=λ/μ
Зробимо заміну у формулах (28) і (29) відношення λ/&mu на ρ, тоді вирази набудуть вигляду:
(30)
Ймовірність Р 0 буде обчислюватися за такою формулою:
p 0 = -1. (31)
Вираз для ймовірності P 0 є геометрична прогресія, сума якої дорівнюватиме
.
Таким чином, формули (30) і (31) дозволяють визначити ймовірність будь-якої події, яка може статися в системі, тобто визначити ймовірність знаходження системи у будь-якому стані.
Формула для P 0 справедлива для випадку, коли ρ ≠ 1 . У випадку, коли ρ = 1, тобто інтенсивність надходження заявок дорівнює інтенсивності їх обслуговування, використовується інша формула для обчислення ймовірності того, що система вільна:
,
де m – кількість заявок, що у черзі.
Визначимо характеристики ефективності одноканальної СМО:
- ймовірність того, що чергова заявка, яка прибула до системи, отримає відмову Рвідк;
- абсолютну пропускну спроможність А,
- відносну пропускну здатність Q,
- кількість зайнятих каналів k ,
- середня кількість заявок у черзі r ,
- середня кількість заявок, пов'язаних із СМО, z .
Чергова заявка, яка надійшла до системи, отримує відмову в тому випадку, коли зайнятий канал, тобто йде обслуговування іншої заявки, і все mмісць у черзі також зайняті. тоді ймовірність цієї події можна обчислити за такою формулою:
. (32)
Імовірність того, що заявка прийде в систему і або негайно буде обслужена, або місця в черзі, тобто відносну пропускну здатність, можна знайти за формулою
. (33)
Середня кількість заявок, які можуть бути обслужені в одиницю часу, тобто абсолютну пропускну здатність, розраховують так:
A=Q·λ (34)
Таким чином, за формулами (32), (33), (34) можна обчислити основні показники ефективності будь-якої системи масового обслуговування. тепер виведемо висловлювання обчислення показників, властивих лише даної СМО.
Середня кількість заявок у черзі r визначимо як математичне очікування дискретної випадкової величини, де R- Число заявок у черзі.
♦ Р 2 – це ймовірність того, що у черзі на обслуговування знаходиться одна заявка;
♦ Р 3 – ймовірність того, що у черзі дві заявки;
♦ Рk– ймовірність того, що у черзі (k–1) заявка;
♦ Рm+ 1 – ймовірність того, що в черзі m заявок.
Тоді середню кількість заявок у черзі можна обчислити так:
r = 1 · P 2 +2 · P 3 + ... + (k-1) · P k + ... + m · P m +1 . (35)
Підставимо у формулу (35) знайдені раніше значення ймовірностей, обчислені у формулі (30):
r = 1 · p 2 · p 0 +2 · p 3 · p 0 + ... + (k-1) · p k · p 0 + ... + m · p m +1 · p 0 . (35)
Винесемо за дужку ймовірність P 0 та Р 2 , тоді отримаємо підсумкову формулу для обчислення середньої кількості заявок у черзі на обслуговування:
r =ρ 2 ·p 0 (1+2·ρ+ ... +(k-1)·ρ k-2 + ... +m·ρ m-1)
Виведемо формулу для середнього числа заявок, пов'язаних із СМО, z, тобто число заявок у черзі, що знаходяться на обслуговуванні. Розглянемо загальну кількість заявок, пов'язаних із СМО, z як суму двох величин середньої кількості заявок у черзі r та числа зайнятих каналів k :
z = r + k.
Оскільки канал один, число зайнятих каналів k може приймати значення 0 чи 1. Ймовірність те, що k = 0, тобто. система вільна, відповідає ймовірності Р 0 значення якої можна знайти за формулою (31). Якщо k = 1, тобто. канал зайнятий обслуговуванням заявки, але місця у черзі ще є, то ймовірність цієї події можна вирахувати за формулою
.
Отже, z дорівнюватиме:
. (37)
Одноканальна СМО з очікуванням
Система масового обслуговування має один канал. Вхідний потік заявок обслуговування - найпростіший потік з інтенсивністю l. Інтенсивність потоку обслуговування дорівнює m (тобто в середньому безперервно зайнятий канал видаватиме m обслуговуваних заявок). Тривалість обслуговування - випадкова величина, підпорядкована показовому закону розподілу. Потік обслуговування є найпростішим пуасонівським потоком подій. Заявка, що надійшла в момент, коли канал зайнятий, стає в чергу і чекає на обслуговування.Припустимо, що незалежно від того, скільки вимог надходить на вхід обслуговуючої системи, дана система (черга + клієнти, що обслуговуються) не може вмістити більше N-вимог (заявок), тобто клієнти, які не потрапили в очікування, змушені обслуговуватися в іншому місці . Нарешті, джерело, що породжує заявки обслуговування, має необмежену (нескінченно велику) ємність.
Граф станів СМО у разі має вигляд, показаний на Рис. 3.2.
Граф станів одноканальної СМО з очікуванням (схема загибелі та розмноження)
Стани СМО мають таку інтерпретацію:
S 0 - канал вільний
S 1 - канал зайнятий (черги немає);
S 2 - канал зайнятий (одна заявка стоїть у черзі);
………………………………
S n -канал зайнятий (n – 1 заявок стоїть у черзі);
……………………………
S N – канал зайнятий (N – 1 заявок стоїть у черзі).
Стаціонарний провіс у даній системі буде описуватися наступною системою рівнянь алгебри :
п -номер стану.
Рішення наведеної вище системи рівнянь (3.10) для нашої моделі СМО має вигляд
Слід зазначити, що виконання умови стаціонарності для даної СМО необов'язкове, оскільки кількість заявок, що допускаються в обслуговувальну систему, контролюється шляхом введення обмеження на довжину черги (яка не може перевищувати N- 1), а чи не співвідношенням між інтенсивностями вхідного потоку, т. е. не ставленням
l/m = p
Визначимо характеристики одноканальної СМОз очікуванням та обмеженою довжиною черги, що дорівнює (N - 1):
Розглянемо приклад одноканальної СМО з очікуванням.
Приклад 3.2.Спеціалізований пост діагностики є одноканальною СМО. Число стоянок для автомобілів, що очікують проведення діагностики, обмежено і дорівнює 3 [(N- 1) = 3]. Якщо всі стоянки зайняті, тобто в черзі вже три автомобілі, то черговий автомобіль, що прибув на діагностику, в чергу на обслуговування не стає. Потік автомобілів, що прибувають на діагностику, розподілено за законом Пуассона та має інтенсивність l= 0,85 (автомобіля за годину). Час діагностики автомобіля розподілено за показовим законом і в середньому дорівнює 1,05 год.
Потрібно визначитиймовірнісні характеристики посту діагностики, що працює в стаціонарному режимі.
Рішення
1. Параметр потоку обслуговування автомобілів:
2. Наведена інтенсивність потоку автомобілів окреслюється відношення інтенсивностей l і m, тобто.
3. Обчислимо фінальні можливості системи:
P 1 = p · P 0 = 0.893 · 0.248 = 0.221
P 2 = ρ 2 · P 0 = 0.893 2 · 0.248 = 0.198
P 3 = p 3 · P 0 = 0.893 3 · 0.248 = 0.177
P 4 = ρ 4 · P 0 = 0.893 2 · 0.248 = 0.158
4. Імовірність відмови в обслуговуванні автомобіля:
P отк =P 4 =ρ 4 ·P 0 ≈ 0.158
5. Відносна пропускна здатність посту діагностики:
q=1-P відк = 1-0.158 = 0.842
6. Абсолютна пропускна здатність посту діагностики
A = λ · q = 0.85 · 0.842 = 0.716 (автомобіля на годину)
7. Середня кількість автомобілів, що знаходяться на обслуговуванні та в черзі (тобто в системі масового обслуговування):
8. Середній час перебування автомобіля у системі:
9. Середня тривалість перебування заявки у черзі обслуговування:
W q =W S -1/μ = 2.473-1/0.952 = 1.423 години
10. Середня кількість заявок у черзі (довжина черги): L q= А, (1 - P N) W q= 0,85
L q =λ(1-P N) · W q = 0.85 · (1-0.158) · 1.423 = 1.02
Роботу розглянутого поста діагностики можна вважати задовільною, оскільки пост діагностики не обслуговує автомобілі в середньому у 15,8% випадків. (Р відк= 0,158). Як показники ефективності СМО з очікуванням, крім вже відомих показників - абсолютної А та відносної Q пропускної спроможності, ймовірності відмови P отк. , середньої кількості зайнятих каналів (для багатоканальної системи) розглядатимемо також такі: L сист. - Середня кількість заявок системі; Т сист. - середній час перебування заявки у системі; L оч. - середня кількість заявок у черзі (довжина черги); Т оч. - середній час перебування заявки у черзі; Р зан.. - ймовірність того, що канал зайнятий (ступінь завантаження каналу).
Одноканальна система з необмеженою чергою
На практиці часто зустрічаються одноканальні СМО з необмеженою чергою (наприклад, телефон-автомат із однією будкою).Розглянемо завдання.
Є одноканальна СМО з чергою, на яку не накладено жодних обмежень (ні за довжиною черги, ні за часом очікування). Потік заявок, що надходять до СМО, має інтенсивність λ, а потік обслуговування - інтенсивність μ. Необхідно знайти граничні ймовірності станів та показники ефективності СМО.
Система може перебувати в одному із станів S 0 , S 1 , S 2 , …, S k , за кількістю заявок, що знаходяться в СМО: S 0 - канал вільний; S 1 - канал зайнятий (обслуговує заявку), черги немає, S 2 - канал зайнятий, одна заявка стоїть у черзі; ... S k - канал зайнятий, (k-1) заявок стоять у черзі і т.д.
Граф станів СМО подано на рис. 8.
Мал. 8
Це процес загибелі та розмноження, але з нескінченним числом станів, в якому інтенсивність потоку заявок дорівнює λ, а інтенсивність потоку обслуговування μ.
Перш ніж записати формули граничних ймовірностей, необхідно бути впевненим у їхньому існуванні, адже у разі, коли час t→∞, черга може необмежено зростати. Доведено, що якщоρ<1, тобто. середня кількість заявок, що приходять менше середньої кількості обслужених заявок (в одиницю часу), то граничні ймовірності існують. Якщоρ≥1, черга зростає до безкінечності.
Для визначення граничних ймовірностей станів скористаємося формулами (16), (17) для процесу загибелі та розмноження (тут ми допускаємо відому нестрогість, оскільки раніше ці формули були отримані для кінцевого числа станів системи). Отримаємо(32)
Оскільки граничні ймовірності існують лише за ρ< 1, то геометрический ряд со знаменателем
ρ < 1, записанный в скобках в формуле (32), сходится к сумме, равной . Поэтому
p 0 =1-ρ, (33)
та з урахуванням співвідношень (17)
p 1 = p 0 ; p 2 = ρ 2 · p 0; ...; p k = p k · p 0; ...
знайдемо граничні ймовірності інших станів
p 1 = ρ · (1-ρ); p 2 = ρ 2 · (1-ρ); ...; p k = p k · (1-ρ); ... (34)
Граничні ймовірності p 0 , p 1 , p 2 , …, p k , … утворюють спадну геометричну професію зі знаменником р< 1, следовательно, вероятность р 0 - наибольшая. Это означает, что если СМО справляется с потоком заявок (при ρ < 1), то наиболее вероятным будет отсутствие заявок в системе.
Середня кількість заявок у системі L сист. визначимо за формулою математичного очікування, яка з урахуванням (34) набуде вигляду 
(35)
(Підсумовування від 1 до ∞, так як нульовий член 0 · p 0 = 0).
Можна показати, що формула (35) перетворюється (при ρ< 1) к виду
(36)
Знайдемо середню кількість заявок у черзі L оч. Очевидно, що
L оч =L сист -L про (37)
де L про. - Середня кількість заявок, що знаходяться під обслуговуванням.
Середня кількість заявок під обслуговуванням визначимо за формулою математичного очікування числа заявок під обслуговуванням, що приймає значення 0 (якщо канал вільний) або 1 (якщо канал зайнятий):
L оч =0 · p 0 +1 · (1-p 0)
тобто. середня кількість заявок під обслуговуванням дорівнює ймовірності того, що канал зайнятий:
L оч =P зан =1-p 0 , (38)
В силу (33)
L оч =P зан ρ, (39)
Тепер за формулою (37) з урахуванням (36) та (39)
(40)
Доведено, що за будь-якого характеру потоку заявок, за будь-якого розподілу часу обслуговування, за будь-якої дисципліни обслуговування середній час перебування заявки в системі (черги) дорівнює середній кількості заявок у системі (у черзі), поділеному на інтенсивність потоку заявок,тобто. 
(41)
(42)
Формули (41) та (42) називаються формулами Літтла.Вони випливають із того, що в граничному, стаціонарному режимі середня кількість заявок, що прибувають до системи, дорівнює середній кількості заявок, що залишають її:обидва потоки заявок мають ту саму інтенсивність λ.
На підставі формул (41) та (42) з урахуванням (36) та (40) середній час перебування заявки в системі визначиться за формулою: 
(43)
а середній час перебування заявки у черзі
(44)
Одноканальна СМО з очікуванням без обмеження на місткість блоку очікування
Стаціонарний режим функціонування даної СМО існує при t→∞ для будь-якого п=0,1,2, і коли l< m.Система алгебраических уравнений, описывающих работу СМО при t®¥ для любого n = 0, 1, 2...., имеет видВирішення даної системи рівнянь має вигляд
P n =(1-ρ)·ρ n , n=0,1,2,... (3.21)
де ρ=λ/μ< 1
Характеристики одноканальної СМО з очікуванням, без обмеження на довжину черги, такі:
середня кількість клієнтів (заявок) на обслуговування, що знаходяться в системі:
середня тривалість перебування клієнта у системі:
приклад 3.3.Згадаймо про ситуацію, розглянуту приклад 3.2, де йдеться про функціонування посту діагностики. Нехай аналізований пост діагностики має в своєму розпорядженні необмежену кількість майданчиків для стоянки автомобілів, що прибувають на обслуговування, тобто довжина черги не обмежена.
Потрібно визначити фінальні значення наступних імовірнісних характеристик:
- ймовірності станів системи (поста діагностики);
- середня кількість автомобілів, що знаходяться в системі (на обслуговуванні та в черзі);
- середню тривалість перебування автомобіля у системі (на обслуговуванні та в черзі);
- середня кількість автомобілів у черзі на обслуговуванні;
- середню тривалість перебування автомобіля у черзі.
Рішення
1. Параметр потоку обслуговування m та наведена інтенсивність потоку автомобілів р визначено у прикладі 3.2:
m = 0,952; p = 0,893.
2. Обчислимо граничні ймовірності системи за формулами
P 0 =1-ρ = 1-0.893 = 0.107
P 1 = (1-ρ) · ρ = (1-0.893) · 0.893 = 0.096
P 2 = (1-ρ) · ρ 2 = (1-0.893) 2 · 0.893 = 0.085
P 3 = (1-ρ) · ρ 3 = (1-0.893) 3 · 0.893 = 0.076
P 4 = (1-ρ) · ρ 4 = (1-0.893) 4 · 0.893 = 0.068
P 5 = (1-ρ) · ρ 5 = (1-0.893) 5 · 0.893 = 0.061
і т.д.
Слід зазначити, що Ро визначає частку часу, протягом якого пост діагностики вимушено не діє (простує). У прикладі вона становить 10,7%, оскільки Ро= 0,107.
3. Середня кількість автомобілів, що знаходяться в системі (на обслуговуванні та в черзі):
4. Середня тривалість перебування клієнта у системі:
6. Середня тривалість перебування автомобіля в черзі-
7. Відносна пропускна спроможність системи:
т. е. кожну заявку, яка прийшла в систему, буде обслужена.
8. Абсолютна пропускна спроможність: А= l q= 0,85 · 1 = 0,85
Слід зазначити, що підприємство, яке здійснює діагностику автомобілів, насамперед цікавить кількість клієнтів, що відвідає посаду діагностики зі зняттям обмеження на довжину черги.
Припустимо, в початковому варіанті кількість місць для стоянки автомобілів, що прибувають, дорівнювала трьом (див. приклад 3.2). Частота m виникнення ситуацій, коли автомобіль, що прибуває на посаду діагностики, не має можливості приєднатися до черги:
т= l P N
У прикладі при N = 3 + 1 = 4 і р = 0,893,
m = l Р ор 4 = 0,85 · 0,248 · 0,8934 · 0,134 автомобіля на годину.
При 12-годинному режимі роботи посту діагностики це еквівалентно тому, що пост діагностики в середньому за зміну (день) втрачатиме 12 0,134 = 1,6 автомобіля.
Зняття обмеження на довжину черги дозволяє збільшити кількість обслужених клієнтів у нашому прикладі в середньому на 1,6 автомобіля за зміну (12 год. роботи) посту діагностики. Зрозуміло, що рішення щодо розширення площі для стоянки автомобілів, які прибувають на посаду діагностики, має ґрунтуватися на оцінці економічної шкоди, яка обумовлена втратою клієнтів за наявності лише трьох місць для стоянки цих автомобілів.
Багатоканальна СМО з необмеженою чергою
Розглянемо завдання. Є n-канальна СМО з необмеженою чергою. Потік заявок, що надходять до СМО, має інтенсивність λ, а потік обслуговування - інтенсивність μ. Необхідно знайти граничні ймовірності станів СМО та показники її ефективності.Система може перебувати в одному із станів S 0 , S 1 , S 2 ,…, S k ,…, S n ,…, - нумерованих за кількістю заявок, що перебувають у СМО: S 0 - у системі немає заявок (всі канали вільні) ; S 1 - зайнятий один канал, інші вільні; S 2 - зайняті два канали, інші вільні;..., S k - зайнято k каналів, інші вільні;..., S n - зайняті всі n каналів (черги немає); S n+1 - зайняті все n каналів, у черзі одна заявка;..., S n+r - зайняті все nканалів, rзаявок стоїть у черзі.
Граф станів системи показано на рис. 9. Звернемо увагу на те, що на відміну від попередньої СМО, інтенсивність потоку обслуговувань (що переводить систему з одного стану в інший справа наліво) не залишається постійною, а в міру збільшення числа заявок у СМО від 0 до n збільшується від величини m до nm , оскільки відповідно збільшується кількість каналів обслуговування. При числі заявок у СМО більшому, ніж n, інтенсивність потоку обслуговування зберігається рівною nm.
середня кількість заявок у черзі 
, (50)
середня кількість заявок у системі
L сист =L оч +ρ, (51)
Середній час перебування заявки у черзі та середній час перебування заявки у системі, як і раніше, перебувають за формулами Літтла (42) та (41).
Зауваження.Для СМО з необмеженою чергою при r< 1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа P отк = 0, относительная пропускная способность Q=1, а абсолютна пропускну здатність дорівнює інтенсивності вхідного потоку заявок, тобто. А=l.
СМО з обмеженою чергою
СМО з обмеженою чергою.СМО з обмеженою чергою відрізняються від розглянутих вище завдань лише тим, що кількість заявок у черзі обмежена (не може перевищувати певного заданого т).Якщо нова заявка надходить у момент, коли усі місця у черзі зайняті, вона залишає СМО необслуженной, тобто. отримує відмову.Очевидно: для обчислення граничних ймовірностей станів та показників ефективності таких СМО може бути використаний той самий підхід, що і вище, з тією різницею, що підсумовувати треба не нескінченну прогресію (як, наприклад, ми робили при виведенні формули (33)), а кінцеву .
Середній час перебування заявки в черзі та в системі, як і раніше, визначаємо за формулами Літтла (44) та (43).
СМО з обмеженим часом очікування.Насправді часто зустрічаються СМО з про " нетерплячими " заявками. Такі заявки можуть піти з черги, якщо час очікування перевищує певну величину. Зокрема, такі заявки виникають у різних технологічних системах, у яких затримка з початком обслуговування може призвести до втрати якості продукції, у системах оперативного управління, коли термінові повідомлення втрачають цінність (або навіть сенс), якщо вони не надходять на обслуговування протягом певного часу.
У найпростіших математичних моделях таких систем передбачається, що заявка може у черзі випадковий час, розподілене по показовому закону з деяким параметром υ, тобто. можна умовно вважати, що кожна заявка, яка стоїть у черзі обслуговування, може залишити систему з інтенсивністю υ.
Відповідні показники ефективності СМО з обмеженим часом виходять на основі результатів, отриманих для процесу загибелі та розмноження.
На закінчення відзначимо, що на практиці часто зустрічаються замкнуті системи обслуговування, у яких вхідний потік заявок істотно залежить від стану самої СМО. Як приклад можна навести ситуацію, коли на ремонтну базу надходять з місць експлуатації деякі машини: зрозуміло, що чим більше машин перебуває в стані ремонту, тим менше їх продовжує експлуатуватися і тим менша інтенсивність потоку машин, що знову надходять на ремонт. Для замкнутих СМО характерною є обмежена кількість джерел заявок, причому кожне джерело "блокується" на час обслуговування його заявки (тобто він не видає нових заявок). У подібних системах при кінцевому числі станів СМО граничні ймовірності існуватимуть за будь-яких значень інтенсивностей потоків заявок та обслуговування. Вони можуть бути обчислені, якщо знову звернутися до процесу загибелі та розмноження.
На практиці досить часто зустрічаються одноканальні СМО з чергою (лікар, який обслуговує пацієнтів; телефон-автомат з однією будкою; ЕОМ, що виконує замовлення користувачів). Теоретично масового обслуговування одноканальні СМО з чергою також займають особливе місце (саме до таких СМО належить більшість отриманих досі аналітичних формул для немарківських систем). Тому ми приділимо одноканальній СМО із чергою особливу увагу.
Нехай є одноканальна СМО з чергою, на яку не накладено жодних обмежень (ні за довжиною черги, ні за часом очікування). Цю СМО надходить потік заявок з інтенсивністю X; потік обслуговування має інтенсивність, зворотну середньому часу обслуговування заявки Потрібно знайти фінальні ймовірності станів СМО, а також характеристики її ефективності:
Середня кількість заявок у системі,
Середній час перебування заявки у системі,
Середня кількість заявок у черзі,
Середній час перебування заявки у черзі,
Імовірність того, що канал зайнятий (ступінь завантаження каналу).
Що стосується абсолютної пропускної спроможності А та відносної Q, то обчислювати їх немає потреби: в силу того, що черга необмежена, кожна заявка рано чи пізно буде обслужена, тому з тієї ж причини
Рішення. Стан системи, як і раніше, будемо нумерувати за кількістю заявок, що знаходяться в СМО:
Канал вільний,
Канал зайнятий (обслуговує заявку), черги немає,
Канал зайнятий, одна заявка стоїть у черзі,
Канал зайнятий, заявок стоять у черзі,
Теоретично кількість станів нічим не обмежена (нескінченно). Граф станів має вигляд, показаний на рис. 20.2. Це - схема загибелі та розмноження, але з нескінченним числом станів. По всіх стрілках потік заявок з інтенсивністю А переводить систему зліва направо, а праворуч наліво - потік обслуговування з інтенсивністю
Насамперед спитаємо себе, а чи існують у цьому випадку фінальні ймовірності? Адже кількість станів системи нескінченна, і, в принципі, при черзі може необмежено зростати! Так, так воно і є: фінальні ймовірності для такої СМО існують не завжди, а лише коли система не перевантажена. Можна довести, що якщо строго менше одиниці, то фінальні ймовірності існують, а при черзі при зростає необмежено. Особливо «незрозумілим» здається цей факт при Здавалося б, до системи не пред'являється нездійсненних вимог: за час обслуговування однієї заявки приходить в середньому одна заявка, і все має бути в порядку, а ось насправді – не так.
При СМО справляється з потоком заявок, тільки якщо цей потік - регулярний, і час обслуговування - теж не випадковий, рівний інтервалу між заявками. У цьому «ідеальному» випадку черги в СМО взагалі не буде, канал буде безперервно зайнятий і регулярно випускатиме обслужені заявки. Але варто лише потоку заявок або потоку обслуговувань стати хоча б трохи випадковими - і черга вже зростатиме до нескінченності. На практиці цього не відбувається лише тому, що «нескінченна кількість заявок у черзі» – абстракція. Ось яких грубих помилок може призвести заміна випадкових величин їх математичними очікуваннями!
Але повернемося до нашої одноканальної СМО із необмеженою чергою. Строго кажучи, формули для фінальних ймовірностей у схемі загибелі та розмноження виводилися нами лише для випадку кінцевого числа станів, але дозволимо собі вільність – скористаємося ними і для нескінченного числа станів. Підрахуємо фінальні ймовірності станів за формулами (19.8), (19.7). У разі число доданків у формулі (19.8) буде нескінченним. Отримаємо вираз для
Ряд у формулі (20.11) є геометричною прогресією. Ми знаємо, що при ряд сходиться - це нескінченно спадна геометрична прогресія зі знаменником. При ряд розходиться (що є непрямим, хоч і суворим доказом те, що фінальні ймовірності станів існують лише за ). Тепер припустимо, що ця умова виконана, і підсумовуючи прогресію в (20.11), маємо
(20.12)
Імовірності знайдуться за формулами:
звідки, з урахуванням (20.12), знайдемо остаточно:
Як видно, ймовірності утворюють геометричну прогресію із знаменником. Як це не дивно, максимальна з них - ймовірність того, що канал взагалі буде вільний. Як би не була навантажена система з чергою, якщо вона взагалі справляється з потоком заявок найімовірніша кількість заявок у системі буде 0.
Знайдемо середню кількість заявок у СМО. Тут доведеться трохи повозитися. Випадкова величина Z – число заявок у системі – має можливі значення з ймовірностями
Її математичне очікування одно
(20.14)
(Сума береться не від 0 до а від 1 до так як нульовий член дорівнює нулю).
Підставимо у формулу (20.14) вираз для
Тепер винесемо за знак суми:
Тут ми знову застосуємо «маленьку хитрість»: є не що інше, як похідна досі від виразу означає,
Змінюючи місцями операції диференціювання та підсумовування, отримаємо:
Але сума у формулі (20.15) є не що інше, як сума нескінченно спадної геометричної прогресії з першим членом і знаменником; ця сума дорівнює а її похідна. Підставляючи цей вираз (20.15), отримаємо:
(20.16)
Ну, а тепер застосуємо формулу Літтла (19.12) та наймемо середній час перебування заявки в системі:
Знайдемо середню кількість заявок у черзі Будемо міркувати так: кількість заявок у черзі дорівнює кількості заявок у системі мінус кількість заявок, що знаходяться під обслуговуванням. Значить (за правилом складання математичних очікувань), середня кількість заявок у черзі дорівнює середньому числу заявок у системі мінус середня кількість заявок під обслуговуванням. Число заявок під обслуговуванням може бути або банкрутом (якщо канал вільний), або одиницею (якщо він зайнятий). Математичне очікування такої випадкової величини дорівнює ймовірності того, що канал зайнятий (ми її позначили). Очевидно, одно одиниці мінус ймовірність того, що канал вільний;
Отже, середня кількість заявок під обслуговуванням дорівнює
Розглянемо багатоканальну СМО, на вхід якої надходить пуасонівський потік заявок з інтенсивністю, а інтенсивність обслуговування кожного каналу становить максимально можливе число місць у черзі обмежене величиною m. Дискретні стани СМО визначаються кількістю заявок, які надійшли до системи, які можна записати.
Всі канали вільні;
Зайнятий лише один канал (будь-який), ;
- - зайняті лише два канали (будь-яких), ;
- - зайняті всі канали, .
Поки СМО перебуває у будь-якому з цих станів, черги немає. Після того, як зайняті всі канали обслуговування, наступні заявки утворюють чергу, тим самим, визначаючи подальший стан системи:
Зайняті всі канали і одна заявка стоїть у черзі,
Зайняті всі канали і дві заявки стоять у черзі,
Зайняті всі канали і всі місця в черзі,
Перехід СМО в стан з великими номерами визначається потоком заявок, що надходять, з інтенсивністю, тоді як за умовою в обслуговуванні цих заявок беруть участь однакових каналів з інтенсивністю потоку обслуговування рівного для кожного каналу. При цьому повна інтенсивність потоку обслуговування зростає з підключенням нових каналів аж до такого стану, коли всі канали n виявляться зайнятими. З появою черги інтенсивність обслуговування більше збільшується, оскільки вона досягла максимального значення, рівного.
Запишемо вирази для граничних ймовірностей станів:
Вираз можна перетворити, використовуючи формулу геометричної прогресії для суми членів зі знаменником:
Освіта черги можливе, коли заявка, що знову надійшла, застане в системі не менше вимог, тобто. коли у системі буде перебувати вимог.
Ці події незалежні, тому ймовірність того, що всі канали зайняті, дорівнює сумі відповідних ймовірностей
Тому ймовірність утворення черги дорівнює:
Імовірність відмови в обслуговуванні настає тоді, коли всі канали і всі місця в черзі зайняті:
Відносна пропускна здатність дорівнюватиме:
Абсолютна пропускна спроможність -
Середня кількість зайнятих каналів -
Середня кількість каналів, що простоюють -
Коефіцієнт зайнятості (використання) каналів -
Коефіцієнт простою каналів -
Середня кількість заявок, що знаходяться у чергах -
Якщо ця формула набуває іншого вигляду -
Середній час очікування у черзі визначається формулами Літтла -
Розглянемо одноканальну систему масового обслуговування з очікуванням.
Припускатимемо, що вхідний потік заявок на обслуговування є найпростішим потоком з інтенсивністю λ.
Інтенсивність потоку обслуговування дорівнює μ. Тривалість обслуговування – випадкова величина, підпорядкована показовому закону розподілу. Потік обслуговування є найпростішим пуасонівським потоком подій.
Заявка, що надійшла в момент, коли канал зайнятий, стає в чергу і чекає на обслуговування. Вважатимемо, що розмір черги обмежений і не може вмістити більше m заявок, тобто. заявка, що залишила в момент свого приходу до СМО m +1 заявок (m тих, хто чекає в черзі і одну, яка перебуває на обслуговуванні), залишає СМО.
Система рівнянь, що описують процес у цій системі, має рішення:
(0‑1)
Знаменник першого виразу є геометричною прогресією з першим членом 1 і знаменником ρ, звідки отримуємо
При ρ = 1 можна вдатися до прямого підрахунку
(0‑8)
Середня кількість заявок, що знаходяться в системі.
Оскільки середня кількість заявок, що знаходяться в системі
(0‑9)
де - середня кількість заявок, що знаходяться під обслуговуванням, знаючи залишається знайти. Т.к. канал один, то кількість заявок, що обслуговуються, може дорівнювати або 0, або 1 з ймовірностями P 0 і P 1 = 1-P 0 відповідно, звідки
(0‑10)
і середня кількість заявок, що знаходяться в системі, дорівнює
(0‑11)
Середній час очікування заявки у черзі.
тобто, середній час очікування заявки в черзі дорівнює середній кількості заявок у черзі, поділеному на інтенсивність потоку заявок.
Середній час перебування заявки у системі.
Час перебування заявки у системі складається з часу очікування заявки у черзі та часу обслуговування. Якщо завантаження системи становить 100%, то =1/μ, інакше = q/μ. Звідси
(0‑13)
зміст роботи.
Підготовка інструментарію експерименту .
Виконується аналогічно відповідно до загальних правил.
Розрахунок на аналітичній моделі.
1. У Microsoft Excel підготуйте таблицю такого вигляду.
2. У стовпцях для параметрів СМО таблиці запишіть вихідні дані, що визначаються за правилом:
m=1,2,3
(максимальна довжина черги).
Для кожного значення m необхідно знайти теоретичні та експериментальні значення показників СМО для таких пар значень:
= <порядковый номер в списке группы>
3. У стовпчиках з показниками аналітичної моделі впишіть відповідні формули.
Експеримент на імітаційній моделі.
1. Встановіть режим запуску з експоненційно розподіленим часом обслуговування, задавши значення відповідного параметра рівним 1.
2. Для кожної комбінації m , та здійсніть запуск моделі.
3. Результати запусків внесіть до таблиці.
4. Внесіть у відповідні стовпці таблиці формули для розрахунку середнього значення показника P отк, q і А.
Аналіз результатів .
1. Проаналізуйте результати, отримані теоретичним та експериментальним способами, порівнявши результати між собою.
2. Для m=3 побудуйте одній діаграмі графіки залежності P відк від теоретично та експериментально отриманих даних.
Оптимізація параметрів СМО .
Розв'яжіть задачу оптимізації розміру числа місць у черзі m для приладу із середнім часом обслуговування = з погляду отримання максимального прибутку. Як умови завдання візьміть:
- дохід від обслуговування однієї заявки рівним 80 у.о./год.,
- вартість утримання одного приладу рівним 1у.о./год.
1. Для розрахунків доцільно створити таблицю:
Перший стовпець заповнюється значеннями чисел натурального ряду (1,2,3…).
Всі клітини другого та третього стовпців заповнюються значеннями і.
У клітини стовпців з четвертого до дев'ятого переносяться формули для стовпців таблиці розділу 0.
У стовпці з вихідними даними розділів Дохід, Витрата, Прибуток внесіть значення (див. вище).
У стовпцях з значеннями розділів, що обчислюються, Дохід, Витрата, Прибуток запишіть розрахункові формули:
- кількість заявок на одиницю часу
N r =A
- сумарний дохід за одиницю часу
I S = I r *N r
- сумарна витрата в одиницю часу
E S = E s + E q * (n-1)
- прибуток у одиницю часу
P = I S - E S
де
I r - Дохід від однієї заявки,
E s - Витрата на експлуатацію одного приладу,
E q - Витрата на експлуатацію одного місця в черзі.
Графіки для P отк ,
- таблицю з даними для знаходження найкращого m і значення m опт,
- графік залежності прибутку в одиницю часу від m.
Контрольні питання :
1) Дайте короткий опис одноканальної моделі СМО з обмеженою чергою.
2) Якими показниками характеризується функціонування одноканальної СМО із відмовами?
3) Як розраховується ймовірність p 0 ?
4) Як розраховуються ймовірності p i?
5) Як знайти можливість відмови від обслуговування заявки?
6) Як знайти відносну пропускну спроможність?
7) Чому дорівнює абсолютна пропускна спроможність?
8) Як підраховується середня кількість заявок у системі?
9) Наведіть приклади СМО з обмеженою чергою.
Завдання.
1) Порт має один вантажний причал для розвантаження суден. Інтенсивність потоку становить 0,5 заходи на добу. Середній час розвантаження одного судна 2 доби. Якщо в черзі на розвантаження стоять 3 судна, то судно, що приходить, направляється для розвантаження на інший причал. Знайти показники ефективності роботи причалу.
2) До довідкової залізничного вокзалу надходять телефонні запити з інтенсивністю 80 заявок на годину. Оператор довідкової відповідає на дзвінок, що надійшов, в середньому 0,7 хв. Якщо оператор зайнятий, клієнту видається повідомлення "Чекайте на відповідь", запит стає в чергу, довжина якої не перевищує 4 запитів. Дайте оцінку роботи довідкової та варіант її реорганізації
Багатоканальна система масового обслуговування з обмеженою чергою
Нехай на вхід СМО, що має канали обслуговування, надходить пуасонівський потік заявок з інтенсивністю. Інтенсивність обслуговування заявки кожним каналом дорівнює, а максимальна кількість місць у черзі дорівнює.
Граф такої системи представлений малюнку 7.
Малюнок 7 - Граф станів багатоканальної СМО з обмеженою чергою
Усі канали вільні, черги немає;
Зайняті lканалів ( l= 1, n), черги немає;
Зайняті всі n каналів, у черзі перебуває iзаявок ( i= 1, м).
Порівняння графів на малюнку 2 і малюнку 7 показує, що остання система є окремим випадком системи народження та загибелі, якщо в ній зробити наступні заміни (ліві позначення відносяться до системи народження та загибелі):
Вирази для фінальних ймовірностей легко знайти з формул (4) та (5). В результаті отримаємо:
Освіта черги відбувається, як у момент вступу до СМО черговий заявки все канали зайняті, тобто. у системі перебувають або n, або (n+1),…, або (n + m - 1) заявок. Т.к. ці події несумісні, то ймовірність утворення черги p оч дорівнює сумі відповідних ймовірностей:
Відмова в обслуговуванні заявки відбувається, коли всі m місць у черзі зайняті, тобто:
Відносна пропускна здатність дорівнює:
Середня кількість заявок, що перебувають у черзі, визначається за формулою (11) і може бути записана у вигляді:
Середня кількість заявок, які обслуговуються в СМО, може бути записана у вигляді:
Середня кількість заявок, що знаходяться в СМО:
Середній час перебування заявки до СМО та в черзі визначається формулами (12) та (13).
Багатоканальна система масового обслуговування з необмеженою чергою
Граф такий СМО зображений малюнку 8 і виходить із графа малюнку 7 при.
Малюнок 8 - Граф станів багатоканальної СМО з необмеженою чергою
Формули для фінальних ймовірностей можна отримати з формул для n-канальної СМО з обмеженою чергою. У цьому слід пам'ятати, що з ймовірність р 0 = р 1 =…= p n = 0, тобто. черга необмежено зростає. Отже, цей випадок практичного інтересу не є і нижче розглядається лише випадок. При з (26) отримаємо:
Формули для інших ймовірностей мають той самий вигляд, що й для СМО з обмеженою чергою:
З (27) отримаємо вираз для ймовірності утворення черги заявок:
Оскільки черга не обмежена, то ймовірність відмови в обслуговуванні заявки:
Абсолютна пропускна спроможність:
З формули (28) при отримаємо вираз для середньої кількості заявок у черзі:
Середня кількість заявок, що обслуговуються, визначається формулою:
Середній час перебування у СМО та в черзі визначається формулами (12) та (13).
Багатоканальна система масового обслуговування з обмеженою чергою та обмеженим часом очікування у черзі
Відмінність такої СМО від СМО, розглянутої в підрозділі 5.5, полягає в тому, що час очікування обслуговування, коли заявка знаходиться в черзі, вважається випадковою величиною, розподіленою за показовим законом з параметром, де середній час очікування заявки в черзі, а має сенс інтенсивності потоку догляду заявок із черги. Граф такий СМО зображений малюнку 9.
Малюнок 9 - Граф багатоканальної СМО з обмеженою чергою та обмеженим часом очікування у черзі
Інші позначення мають тут той самий зміст, що й у підрозділі.
Порівняння графів на рис. 3 і 9 показує, що остання система є окремим випадком системи народження та загибелі, якщо в ній зробити наступні заміни (ліві позначення відносяться до системи народження та загибелі):
Вирази для фінальних ймовірностей легко знайти з формул (4) та (5) з урахуванням (29). В результаті отримаємо:
де. Імовірність утворення черги визначається формулою:
Відмова у обслуговуванні заявки відбувається, коли всі m місць у черзі зайняті, тобто. ймовірність відмови в обслуговуванні:
Відносна пропускна спроможність:
Абсолютна пропускна спроможність:
Середня кількість заявок, що перебувають у черзі, знаходиться за формулою (11) і дорівнює:
Середня кількість заявок, що обслуговуються в СМО, знаходиться за формулою (10) і дорівнює:
