Опорний конспект лекцій з курсу Дослідження операцій Тема 15 Моделювання систем масового обслуговування, Визначення характеристик систем масового обслуговування, НУДПСУ

Лекція №15. МОДЕЛЮВАННЯ СИСТЕМ МАСОВОГО ОБСЛУГОВУВАННЯ. Визначення характеристик систем масового обслуговування

План

1. Багатоканальна СМО.

2. Формули Ерланга.

3. Багатоканальна СМО з очікуванням.

4. Модель обслуговування машинного парку.

4.2.2. Багатоканальна модель з пуассонівським вхідним потоком і експоненціальним розподілом тривалості обслуговування

У переважній більшості випадків на практиці системи масового обслуговування є багатоканальними, і, отже, моделі з n обслуговуючими каналами (де n > 1) представляють безперечний інтерес.

Процес масового обслуговування, що описується даною моделлю, характеризується інтенсивністю вхідного потоку, при цьому паралельно може обслуговуватися не більш за n клієнтів (заявок). Середня тривалість обслуговування однієї заявки дорівнює 1/μ. Вхідний і вихідний потоки є пуасcонівськими. Режим функціонування того або іншого обслуговуючого каналу не впливає на режим функціонування інших обслуговуючих каналів системи, причому тривалість процедури обслуговування кожним з каналів є випадковій величиною, підпорядкованою експоненціальному закону розподілу. Кінцева мета використання n паралельно включених обслуговуючих каналів полягає в підвищенні (в порівнянні з одноканальною системою) швидкості обслуговування вимог за рахунок обслуговування одночасно n клієнтів.

Граф станів багатоканальної системи масового обслуговування з відмовами має вигляд, показаний на мал. 4.3.

Стани СМО мають наступну інтерпретацію:

S₀ – всі канали вільні;

S₁ – зайнятий один канал, інші вільні;

S_k – зайняті рівно k каналів, інші вільні;

S_n – зайняті всі n каналів, інші вільні.

Рівняння Колмогорова для імовірності станів системи P₀,...,P_k,...,P_nматимуть наступний вигляд

Початкові умови розв'язку системи такі

P₀(0) = 1, P₁(0) = P₂(0) = ... = P_k(0) = ... = P_n(0) = 0.

Стаціонарний розв'язок системи має вигляд

де Y = λ/μ.

Формули для обчислення імовірності P_k називаються формулами Ерланга.

Визначимо імовірнісні характеристики функціонування багатоканальної СМО з відмовами в стаціонарному режимі:

імовірність відмови

оскільки заявка дістає відмову, якщо приходить в мить, коли всі n каналів зайняті. Величина P_відм характеризує повноту обслуговування вхідного потоку;

імовірність того, що заявка буде прийнята до обслуговування (вона ж – відносна пропускна спроможність системи q доповнює P_відм до одиниці

абсолютна пропускна спроможність

А = λ*q = λ*(1 – P_відм). (4.30)

середнє число каналів, зайнятих обслуговуванням (k_c) наступне

Величина k_c характеризує ступінь завантаження СМО.

Приклад 4.4. Хай n-канальна СМО є обчислювальним центром (ОЦ) з трьома (n = 3) взаємозамінними ПЕОМ для вирішення задач, що поступають до ОЦ. Потік задач, що поступають на ОЦ, має інтенсивність λ = 1 задача на годину. Середня тривалість обслуговування t_c = 1,8 год. Потік заявок на розв'язок задач і потік обслуговування цих заявок є простими.

Потрібно обчислити фінальні значення:

- імовірність станів ОЦ;

- імовірність відмови в обслуговуванні заявки;

- відносної пропускної спроможності ОЦ;

- абсолютної пропускної спроможності ОЦ;

- середнього числа зайнятих ПЕОМ на ОЦ.

Визначити, скільки додатково треба придбати ПЕОМ, щоб збільшити пропускну спроможність ОЦ в 10 разів.

Розв'язок

1. Визначимо параметр μ потоку обслуговуванні

μ = 1/t_c = 1/1,8 = 0,555.

2. Приведена інтенсивність потоку заявок

Y = λ/μ = 1/0,555 = 1,8.

3. Граничну імовірність станів знайдемо по формулах Ерланга (4.27)

Р₁ ≈ 1,8*0,186 ≈ 0,344,

Р₂ ≈ 1,62*0,186 ≈ 0,301,

Р₃ ≈ 0,97*0,186 ≈ 0,180.

4. Імовірність відмови в обслуговуванні заявки

P_відм = Р₃ = 0,18.

5. Відносна пропускна спроможність ОЦ

q = 1 – P_відм = 1 – 0,18 = 0,82.

6. Абсолютна пропускна спроможність ОЦ

А = λ*q = 1*0,82 = 0,82.

7. Середнє число зайнятих каналів – ПЕОМ

Таким чином, при сталому режимі роботи СМО в середньому буде зайнято 1,5 комп'ютера з трьох – інші півтора простоюватимуть. Роботу розглянутого ОЦ навряд чи можна вважати задовільною, оскільки центр не обслуговує заявки в середньому в 18% випадків. Очевидно, що пропускну спроможність ОЦ при даних λ і μ можна збільшити тільки за рахунок збільшення числа ПЕОМ.

Визначимо, скільки потрібно використовувати ПЕМ, щоб скоротити число необслужених заявок, що поступають на ОЦ, в 10 разів, тобто щоб імовірність відмови в розв'язку задач не перевершували 0,0180. Для цього використовуємо формулу (4.28).

Складемо наступну таблицю:

Як неважко зрозуміти, для реалізації такої можливості на ОЦ слід використовувати 6 комп'ютерів, тобто додатково необхідно придбати 3 комп'ютері.

Розглянемо багатоканальну систему масового обслуговування з очікуванням. Процес масового обслуговування при цьому характеризується наступним: вхідний і вихідний потоки є пуассонівськими з інтенсивностями λ і μ відповідно; паралельно обслуговуватися можуть не більш S клієнтів. Система має S каналів обслуговування. Середня тривалість обслуговування одного клієнта дорівнює – 1/μ.

У сталому режимі функціонування багатоканальної СМО з очікуванням і необмеженою чергою може бути описане за допомогою системи алгебраїчних рівнянь

Розв'язок системи рівнянь (4.32) має вигляд.

Розв'язок буде дійсним, якщо виконується наступна умова:

Імовірнісні характеристики функціонування в стаціонарному режимі багатоканальної СМО з очікуванням і необмеженою чергою визначаються по наступних формулах:

- імовірність того, що в системі знаходиться n клієнтів на обслуговуванні, визначається за формулами (4.33) і (4.34);

- середнє число клієнтів в черзі на обслуговування;

- середнє число клієнтів, що знаходяться в системі (заявок на обслуговування і в черзі);

- середня тривалість перебування клієнта (заявки на обслуговування) в черзі;

- середня тривалість перебування клієнта в системі.

Розглянемо приклади багатоканальної системи масового обслуговування з очікуванням.

Приклад 4.5. Механічна майстерня заводу з трьома постами (каналами) виконує ремонт малої механізації. Потік несправних механізмів, що прибувають в майстерню, – пуассонівський і має інтенсивність λ = 2,5 механізму на добу, середній час ремонту одного механізму розподілений за показовим законом і дорівнює t_c = 0,5 доби. Припустимо, що іншої майстерні на заводі немає, і, значить, черга механізмів перед майстернею може рости практично необмежено.

Потрібно обчислити наступні граничні значення імовірнісних характеристик системи:

- імовірність станів системи;

- середнє число заявок в черзі на обслуговування;

- середнє число заявок, що знаходяться в системі;

- середню тривалість перебування заявки в черзі;

- середню тривалість перебування заявки в системі.

Розв'язок

1. Визначимо параметр потоку обслуговувань

μ = 1/t_c = 1/0,5 = 2.

2. Приведена інтенсивність потоку заявок

Y = λ/μ = 2,5/2 = 1,25,

при цьому λ/(μS) = 2,5/(2*3) = 0,41.

Оскільки 0,41 < 1, то черга не росте безмежно і в системі наступає граничний стаціонарний режим роботи.

3. Обчислимо імовірність станів системи

4. Імовірність відсутності черги у майстерні

5. Середнє число заявок в черзі на обслуговування

6. Середнє число заявок, що знаходяться в системі

7. Середня тривалість перебування механізму в черзі на обслуговування доби.

8. Середня тривалість перебування механізму в майстерні (у системі) доби.

4.2.3. Модель обслуговування машинного парку

Модель обслуговування машинного парку є модель замкнутої системи масового обслуговування.

До цих пір ми розглядали тільки такі системи масового обслуговування, для яких інтенсивність λ вхідного потоку заявок не залежить від стану системи. В цьому випадку джерело заявок є зовнішнім по відношенню до СМО і генерує необмежений потік вимог. Розглянемо системи масового обслуговування, для яких λ залежить від стану системи, при чому джерело вимог є внутрішнім і генерує обмежений потік заявок.

Наприклад, обслуговується машинний парк, що складається з N машин, бригадою R механіків (N > R), причому кожна машина може обслуговуватися тільки одним механіком. Тут машини є джерелами вимог (заявок на обслуговування), а механіки – обслуговуючими каналами. Несправна машина після обслуговування використовується по своєму прямому призначенню і стає потенційним джерелом виникнення вимог на обслуговування. Очевидно, що інтенсивність λ залежить від того, скільки машин в даний момент знаходиться в експлуатації (N – k) і скільки машин обслуговується або стоїть в черзі, чекаючи обслуговування (k).

У даній моделі місткість джерела вимог слід вважати обмеженою. Вхідний потік вимог виходить з обмеженого числа експлуатованих машин (N – k), які у випадкові моменти часу виходять з ладу і вимагають обслуговування. При цьому кожна машина з (N – k) знаходиться в експлуатації. Пуассонівський потік вимог генерується з інтенсивністю λ незалежно від інших об'єктів, отже, загальний (сумарний) вхідний потік має інтенсивність (N – k)λ. Вимога, що поступила в систему в момент, коли вільний хоч би один канал, негайно йде на обслуговування. Якщо вимога застає всі канали зайнятими обслуговуванням інших вимог, то вона не покидає систему, а стає в чергу і чекає, поки один з каналів не стане вільним.

Таким чином, в замкнутій системі масового обслуговування вхідний потік вимог формується з того потоку, що виходить з системи.

Стан S_k системи характеризується загальним числом вимог, що знаходяться на обслуговуванні і в черзі, рівним k. Для даної замкнутої системи, очевидно, k = 0,1,2,...,N. При цьому, якщо система знаходиться в стані S_k, то число об'єктів, що знаходяться в експлуатації, дорівнює (N – k).

Якщо λ – інтенсивність потоку вимог з розрахунку на одну машину, то.

Система алгебраїчних рівнянь, що описують роботу замкнутої СМО в стаціонарному режимі, виглядає таким чином.

Розв'язуючи дану систему, знаходимо імовірність k-гo стану.

Величина P₀ визначається з умови нормування  отриманих результатів за формулами (4.40) для P, k = 0,1,2,..., N. Визначимо наступні імовірнісні характеристики системи:

- середнє число вимог в черзі на обслуговування;

- середнє число вимог, що знаходяться в системі (на обслуговуванні і в черзі);

- середнє число механіків (каналів), що «простоюють» через відсутність роботи;

- коефіцієнт простою обслуговуваного об'єкту (машини) в черзі;

- коефіцієнт використання об'єктів (машин);

- коефіцієнт простою обслуговуючих каналів (механіків);

- середній час очікування обслуговування (час очікування обслуговування в черзі).

Приклад 4.6. Хай для обслуговування десяти персональних комп'ютерів (ПК) виділено двох інженерів однакової продуктивності. Потік відмов (несправностей) одного комп'ютера – пуассонівський з інтенсивністю λ = 0,2. Час обслуговування ПК підкоряється показовому закону. Середній час обслуговування одного ПК одним інженером складає: t_c =1,25 час.

Можливі наступні варіанти організації обслуговування:

- обох інженерів обслуговують всі десять комп'ютерів, так що при відмові ПК його обслуговує один з вільних інженерів, в цьому випадку R = 2, N = 10;

- кожний з двох інженерів обслуговує по п'ять закріплених за ним ПК. В цьому випадку R = 1, N = 5.

Необхідно вибрати якнайкращий варіант організації обслуговування ПК.

Розв'язок

1. Обчислимо параметр обслуговування

μ = 1/t_c = 1/1,25 = 0,8.

2. Приведена інтенсивність потоку заявок

Y = λ/μ = 0,2/0,8 = 0,25.

3. Обчислимо імовірнісні характеристики СМО для двох варіантів організації обслуговування ПК.

Варіант 1

1. Визначимо імовірність станів системи:

Враховуючи, що  і використовуючи результати розрахунку P_k, обчислимо P₀

Звідки P₀ = 0,065.

Тоді

P₁ = 0,162,

P₂ = 0,183,

P₃ = 0,182,

P₄ = 0,160,

P₅ = 0,110,

P₆ = 0,075,

P₇ = 0,037,

P₈ = 0,014,

P₉ = 0,003,

P₁₀ = 0,000.

Визначимо середнє число комп'ютерів в черзі на обслуговування

Визначимо середнє число ПК, що знаходяться в системі (на обслуговуванні і в черзі)

Визначимо середнє число інженерів, що простоюють через відсутність роботи

Коефіцієнт простою персонального комп'ютера в черзі наступний

Коефіцієнт використання комп'ютерів визначається по формулі

Коефіцієнт простою обслуговуючих інженерів розраховується так

Середній час очікування ПК обслуговування  год.

Варіант 2

Визначимо імовірність станів системи:

Звідки P₀ = 0,199.

Тоді

P₁ = 0,249,

P₂ = 0,249,

P₃ = 0,187,

P₄ = 0,093,

P₅ = 0,023.

Середнє число комп'ютерів в черзі на обслуговування таке

Середнє число комп'ютерів, що знаходяться на обслуговуванні і в черзі розраховується так

Середнє число інженерів, що простоюють через відсутність роботи

Коефіцієнт простою персонального комп'ютера в черзі

Коефіцієнт використання комп'ютерів

Коефіцієнт простою обслуговуючих інженерів

Середній час очікування ПК обслуговування год.

Зведемо отримані результати по двох варіантах в наступну таблицю

Таким чином, у варіанті 1 кожен комп'ютер стоїть в черзі в очікуванні початку його обслуговування приблизно 0,142 частини робочого часу, що менше цього показника при варіанті 2 організації робіт. Далі у варіанті 1 імовірність того, що ПК і будь-який момент часу працюватиме вище, ніж у варіанті 2, і дорівнює  Очевидно, варіант 1 організації робіт по обслуговуванню ПК ефективніший, ніж варіант 2.

Контрольні запитання

1. Що таке багатоканальна СМО?

2. Наведіть формули Ерланга.

3. Що таке багатоканальна СМО з очікуванням?

4. Основні характеристики моделі обслуговування машинного парку.

З повагою ІЦ “KURSOVIKS”!