- абсолютна та відносна пропускна здатність системи;
- коефіцієнти завантаження та простою;
- середній час повного завантаження системи;
- середній час перебування заявки у системі.
- P обс - ймовірність обслуговування заявки,
- t сист – час перебування заявки у системі.
- λ b- Абсолютна пропускна здатність системи (середня кількість обслужених заявок в одиницю часу),
- P обс - відносна пропускна здатність системи,
- k з - Коефіцієнт завантаження системи.
Завдання. До обчислювального центру колективного користування з трьома ЕОМ надходять замовлення від підприємств на обчислювальні роботи. Якщо працюють всі три ЕОМ, то знову надходить замовлення не приймається, і підприємство змушене звернутися до іншого обчислювального центру. Середній час роботи з одним замовленням становить 3 години. Інтенсивність потоку заявок 0,25 (1/год). Знайти граничні ймовірності станів та показники ефективності роботи обчислювального центру.
Рішення.
За умовою n=3, λ=0,25(1/год), t про. =3 (год). Інтенсивність потоку обслуговувань μ=1/t про. = 1/3 = 0,33. Інтенсивність навантаження ЕОМ за формулою (24) ρ=0,25/0,33=0,75. Знайдемо граничні ймовірності станів:
за формулою (25) p 0 = (1 +0,75 +0,75 2 / 2! +0,75 3 / 3!) -1 = 0,476;
за формулою (26) p 1 =0,75∙0,476=0,357; p 2 =(0,75 2 /2!)∙0,476=0,134; p 3 = (0,75 3 /3!) ∙ 0,476 = 0,033 тобто. у стаціонарному режимі роботи обчислювального центру в середньому 47,6% часу немає жодної заявки, 35,7% - є одна заявка (зайнята одна ЕОМ), 13,4% - дві заявки (дві ЕОМ), 3,3% часу -
три заявки (зайняті три ЕОМ).
Імовірність відмови (коли зайняті всі три ЕОМ), таким чином, P отк. = p 3 = 0,033.
За формулою (28) відносна пропускну здатність центру Q = 1-0,033 = 0,967, тобто. у середньому із кожних 100 заявок обчислювальний центр обслуговує 96,7 заявок.
За формулою (29) абсолютна пропускна спроможність центру A=0,25∙0,967=0,242, тобто. за одну годину в середньому обслуговується 0,242 заявки.
За формулою (30) середня кількість зайнятих ЕОМ k =0,242/0,33 = 0,725, тобто. кожна з трьох ЕОМ буде зайнята обслуговуванням заявок у середньому лише 72,5/3 =24,2%.
При оцінці ефективності роботи обчислювального центру необхідно зіставити доходи від виконання заявок із втратами від простою дорогих ЕОМ (з одного боку, ми маємо високу пропускну здатність СМО, з другого боку - значний простий каналів обслуговування) і вибрати компромісне рішення.
Завдання. У порту є один причал для розвантаження суден. Інтенсивність потоку суден дорівнює 0,4 (судів на добу). Середній час розвантаження одного судна складає 2 доби. Передбачається, що черга може бути необмеженою довжиною. Знайти показники ефективності роботи причалу, а також ймовірність того, що очікують розвантаження не більше ніж 2 судна.
Рішення.
Маємо ρ = λ/μ = μt про. =0,4∙2=0,8. Оскільки ρ = 0,8 <
1, то черга на розвантаження не може нескінченно зростати та граничні ймовірності існують. Знайдемо їх.
Імовірність того, що причал вільний, (33) p 0 = 1 - 0,8 = 0,2, а ймовірність того, що він зайнятий, P зан. = 1-0,2 = 0,8. За формулою (34) ймовірності того, що біля причалу знаходяться 1, 2, 3 судна (тобто очікують на розвантаження 0, 1, 2 судна), дорівнюють p 1 = 0,8(1-0,8) = 0, 16; p 2 = 0,8 2 ∙ (1-0,8) = 0,128; p 3 = 0,8 3 ∙ (1-0,8) = 0,1024.
Імовірність того, що очікують розвантаження не більше ніж 2 судна, дорівнює
P = p 1 + p 2 + p 3 = 0,16 + 0,128 + 0,1024 = 0,3904
За формулою (40) середня кількість суден, що очікують на розвантаження
L jч =0,8 2 /(1-0,8) = 3,2
а середній час очікування розвантаження за формулою (15.42)
T оч =3,2/0,8 = 4 добу.
За формулою (36) середня кількість суден, що знаходяться у причалу, L сист. = 0,8/(1-0,8) = 4 (доба) (або простіше за (37) L сист. = 3,2+0,8 = 4 (доба), а середній час перебування судна у причалу за формулою (41) T сист = 4/0,8 = 5 (добу).
Очевидно, що ефективність розвантаження суден невисока. Для її підвищення необхідно зменшення середнього часу розвантаження судна t або збільшення числа причалів n .
Завдання. В універсамі до вузла розрахунку надходить потік покупців з інтенсивністю λ = 81 чол. в годину. Середня тривалістьобслуговування контролером-касиром одного покупця t про = 2 хв. Визначити:
а. Мінімальна кількість контролерів-касирів п min ,при якому черга не зростатиме до нескінченності, і відповідні характеристики обслуговування при n = n min.
б. Оптимальна кількість опт. контролерів-касирів, при якому відносна величина витрат С отн., пов'язана з витратами на утримання каналів обслуговування і з перебуванням у черзі покупців, що задається, наприклад, як буде мінімальна, і порівняти характеристики обслуговування при n=n min і n=n опт .
в. Імовірність того, що у черзі буде не більше трьох покупців.
Рішення.
а. За умовою l = 81(1/год) = 81/60 = 1,35 (1/хв.). За формулою (24) r = l/m = lt = 1,35×2 = 2,7. Черга не зростатиме до нескінченності за умови r/n< 1, т.е. при n >r = 2,7. Отже, мінімальна кількість контролерів-касирів n min = 3.
Знайдемо характеристики обслуговування СМО при п= 3.
Імовірність того, що у вузлі розрахунку відсутні покупці, за формулою (45) p 0 = (1+2,7+2,7 2 /2!+2,7 3 /3!+2,7 4 /3!(3 -2,7)) -1 = 0,025, тобто. у середньому 2,5%
часу контролери-касири простоюватимуть.
Імовірність те, що у вузлі розрахунку буде черга, по (48) P оч. = (2,7 4 /3! (3-2,7)) 0,025 = 0,735
Середня кількість покупців, що у черзі, по (50) L оч. = (2,7 4 /3∙3!(1-2,7/3) 2)0,025 = 7,35.
Середній час очікування в черзі (42) T оч. = 7,35 / 1,35 = 5,44 (хв).
Середня кількість покупців у вузлі розрахунку (51) L сист. = 7,35 +2,7 = 10,05.
Середній час перебування покупців у вузлі розрахунку (41) T сист. = 10,05/1,35 = 7,44 (хв).
Таблиця 1
| Характеристика обслуговування | Число контролерів-касирів | ||||
| 3 | 4 | 5 | 6 | 7 | |
| Імовірність простою контролерів-касирів p 0 | 0,025 | 0,057 | 0,065 | 0,067 | 0,067 |
| Середня кількість покупців у черзі T оч. | 5,44 | 0,60 | 0,15 | 0,03 | 0,01 |
| Відносна величина витрат З отн. | 18,54 | 4,77 | 4,14 | 4,53 | 5,22 |
Коефіцієнт (частка) зайнятих обслуговуванням контролерів-касирів
= ρ/n = 2,7/3 = 0,9.
Абсолютна пропускна спроможність вузла розрахунку А = 1,35 (1/хв) або 81 (1/год), тобто. 81 покупець за годину.
Аналіз характеристик обслуговування свідчить про значне навантаження вузла розрахунку за наявності трьох контролерів-касирів.
б. Відносна величина витрат за n = 3
З отн. = = 3 / 1,35 +3 ∙ 5,44 = 18,54.
Розрахуємо відносну величину витрат за інших значень п(Табл. 1).
Як очевидно з табл. 2, мінімальні витратиотримані за n = n опт. = 5 контролерах-касирах.
Визначимо характеристики обслуговування вузла розрахунку за n = n опт. =5. Отримаємо P оч. = 0,091; L оч. = 0,198; Т оч. = 0,146 (хв); L сист. = 2,90; T снст. = 2,15 (хв); k = 2,7; k 3 = 0,54.
Як бачимо, при n = 5 в порівнянні з n = 3 суттєво зменшилися ймовірність виникнення черги P оч. , довжина черги L оч. та середній час перебування у черзі T оч. і відповідно середня кількість покупців L сист. і середнє час перебування у вузлі розрахунку T сист., і навіть частка зайнятих обслуговуванням контролерів k 3. Але середнє число зайнятих обслуговуванням контролерів-касирів k і абсолютна пропускна спроможність вузла розрахунку А звичайно змінилися.
в. Імовірність того, що в черзі буде не більше 3 покупців, визначиться як
= 1-P оч. + p 5+1 + p 5+2 + p 5+3 , де кожен доданок знайдемо за формулами (45) – (48). Отримаємо при n=5:
Зауважимо, що у разі n=3 контролерів-касирів та сама ймовірність істотно менша: P(r ≤ 3) =0,464.
Розглянутий у попередній лекції марківський випадковий процес з дискретними станами та безперервним часом має місце у системах масового обслуговування(СМО).
Системи масового обслуговування – це такі системи, в які у випадкові моменти часу надходять заявки на обслуговування, при цьому заявки, що надійшли, обслуговуються за допомогою наявних у розпорядженні системи каналів обслуговування.
Прикладами систем масового обслуговування можуть бути:
- розрахунково-касові вузли у банках, на підприємствах;
- персональні комп'ютери, що обслуговують заявки, що надходять, або вимоги на вирішення тих чи інших завдань;
- станції технічне обслуговуванняавтомобілів; АЗС;
- аудиторські фірми;
- відділи податкових інспекцій, що займаються прийманням та перевіркою поточної звітності підприємств;
- телефонні станції тощо.
Вузли |
Вимоги |
|
Лікарня |
Санітари |
Пацієнти |
Виробництво |
||
Аеропорт |
Виходи на злітно-посадкові смуги Пункти реєстрації |
Пасажири |
Розглянемо схему роботи СМО (рис. 1). Система складається з генератора заявок, диспетчера та вузла обслуговування, вузла обліку відмов (термінатора, знищувача заявок). Вузол обслуговування у випадку може мати кілька каналів обслуговування.
Мал. 1
- Генератор заявок - Об'єкт, що породжує заявки: вулиця, цех із встановленими агрегатами. На вхід надходить потік заявок(Потік покупців у магазин, потік агрегатів, що зламалися (машин, верстатів) на ремонт, потік відвідувачів у гардероб, потік машин на АЗС і т. д.).
- Диспетчер – людина або пристрій, який знає, що робити із заявкою. Вузол, що регулює та направляє заявки до каналів обслуговування. Диспетчер:
- приймає заявки;
- формує чергу, якщо всі канали зайняті;
- спрямовує їх до каналів обслуговування, якщо є вільні;
- дає заявкам відмову (з різних причин);
- приймає інформацію від вузла обслуговування про вільні канали;
- стежить за часом роботи системи.
- Черга - Накопичувач заявок. Черга може бути відсутня.
- Вузол обслуговування складається із кінцевого числа каналів обслуговування. Кожен канал має 3 стани: вільний, зайнятий, не працює. Якщо всі канали зайняті, можна придумати стратегію, кому передавати заявку.
- Відмова від обслуговування настає, якщо всі канали зайняті (деякі навіть можуть працювати).
Крім цих основних елементів СМО в деяких джерелах виділяються також такі складові:
термінатор – знищувач трансактів;
склад – накопичувач ресурсів та готової продукції;
рахунок бухгалтерського обліку – до виконання операцій типу «проводка»;
менеджер – розпорядник ресурсів;
Класифікація СМО
Перший поділ (за наявності черг):
- СМО із відмовими;
- СМО із чергою.
У СМО з відмовамизаявка, що надійшла в момент, коли всі канали зайняті, отримує відмову, залишає СМО і надалі не обслуговується.
У СМО з чергоюзаявка, що прийшла в момент, коли всі канали зайняті, не йде, а стає в чергу і чекає на можливість бути обслуженою.
СМО із чергамиподіляються на різні видизалежно від того, як організовано чергу, – обмежена або не обмежена. Обмеження можуть стосуватися як довжини черги, так і часу очікування, дисципліни обслуговування.
Отже, наприклад, розглядаються такі СМО:
- СМО з нетерплячими заявками (довжина черги та час обслуговування обмежений);
- СМО з обслуговуванням з пріоритетом, тобто деякі заявки обслуговуються позачергово і т.д.
Типи обмеження черги можуть бути комбінованими.
Інша класифікація поділяє СМО за джерелом заявок. Породжувати заявки (вимоги) може сама система чи якась зовнішнє середовище, що існує незалежно від системи.
Природно, потік заявок, породжений системою, залежатиме від системи та її стану.
Крім цього СМО діляться на відкритіСМО та замкнутіСМО.
У відкритій СМО характеристики потоку заявок не залежить від того, в якому стані сама СМО (скільки каналів зайнято). У замкнутій СМО – залежать. Наприклад, якщо один робітник обслуговує групу верстатів, іноді потребують налагодження, то інтенсивність потоку «вимог» з боку верстатів залежить від того, скільки на них вже справно і чекає налагодження.
Приклад замкнутої системи: видача касиром зарплати для підприємства.
За кількістю каналів СМО поділяються на:
- одноканальні;
- багатоканальні.
Характеристики системи масового обслуговування
Основними характеристиками системи масового обслуговування будь-якого виду є:
- вхідний потік вимог чи заявок на обслуговування;
- дисципліна черги;
- Механізм обслуговування.
Вхідний потік вимог
Для опису вхідного потоку потрібно задати ймовірнісний закон, що визначає послідовність моментів надходження вимог на обслуговування,та вказати кількість таких вимог у кожному черговому надходженні. У цьому, зазвичай, оперують поняттям «імовірнісний розподіл моментів надходження вимог». Тут можуть діяти як поодинокі, і групові вимоги (кількість таких вимог у кожному черговому вступі). В останньому випадку зазвичай мова йдепро систему обслуговування із паралельно-груповим обслуговуванням.
А і– час надходження між вимогами – незалежні однаково розподілені випадкові величини;
E(A)- Середнє (МО) час надходження;
λ=1/E(A)- Інтенсивність надходження вимог;
Характеристики вхідного потоку:
- Імовірнісний закон, визначальний послідовність моментів надходження вимог обслуговування.
- Кількість вимог у кожному черговому надходженні для групових потоків.
Дисципліна черги
Черга - Сукупність вимог, що очікують обслуговування.
Черга має ім'я.
Дисципліна черги визначає принцип, відповідно до якого вимоги, що надходять на вхід обслуговуючої системи, підключаються з черги до процедури обслуговування. Найчастіше використовуються дисципліни черги, що визначаються такими правилами:
- першим прийшов – перший обслуговуєшся;
First in First out (FIFO)
найпоширеніший тип черги.
Яка структура даних підійде для опису такої черги? Масив поганий (обмежений). Можна використовувати структуру типу СПИСОК.
Список має початок та кінець. Список складається із записів. Запис – це осередок списку. Заявка надходить до кінця списку, а вибирається обслуговування з початку списку. Запис складається з характеристики заявки та посилання (покажчик, за ким стоїть). Крім цього, якщо черга з обмеженням на час очікування, то ще має бути вказано граничний час очікування.
Ви, як програмісти, повинні вміти робити списки двосторонні, односторонні.
Дії зі списком:
- вставити у хвіст;
- взяти із початку;
- видалити зі списку після закінчення часу очікування.
- прийшов останнім - обслуговуєшся першим LIFO (обойма для патронів, глухий кут на залізничній станції, зайшов у набитий вагон).
Структура відома як СТЕК. Може бути описаний структурою масив чи список;
- випадковий відбір заявок;
- відбір заявок за критерієм пріоритетності
Кожна заявка характеризується також рівнем пріоритету і під час вступу міститься над хвіст черги, а кінець своєї пріоритетної групи. Диспетчер здійснює сортування за пріоритетом.
Характеристики черги
- обмеженнячасу очікуваннямоменту настання обслуговування (має місце черга з обмеженим часомочікування обслуговування, що асоціюється з поняттям "допустима довжина черги");
- довжина черги.
Механізм обслуговування
Механізм обслуговування визначається характеристиками самої процедури обслуговування та структурою обслуговуючої системи. До характеристик процедури обслуговування належать:
- кількість каналів обслуговування ( N);
- тривалість процедури обслуговування (імовірнісний розподіл часу обслуговування вимог);
- кількість вимог, що задовольняються внаслідок виконання кожної такої процедури (для групових заявок);
- можливість виходу з ладу обслуговуючого каналу;
- структура обслуговуючої системи
Для аналітичного опису характеристик процедури обслуговування оперують поняттям «імовірнісне розподілення часу обслуговування вимог».
S i- Час обслуговування i-го вимоги;
E(S)- Середній час обслуговування;
μ=1/E(S)- Швидкість обслуговування вимог.
Слід зазначити, що час обслуговування заявки залежить від характеру самої заявки чи вимог клієнта та стану і можливостей обслуговуючої системи. У ряді випадків доводиться також враховувати ймовірність виходу з ладу обслуговуючого каналупісля закінчення деякого обмеженого інтервалу часу. Цю характеристику можна моделювати як потік відмов, що надходить до СМО та має пріоритет перед усіма іншими заявками.
Коефіцієнт використання СМО
N·μ - швидкість обслуговування в системі, коли зайняті всі пристрої обслуговування.
ρ=λ/( Nμ) – називається коефіцієнтом використання СМО показує, наскільки задіяні ресурси системи.
Структура обслуговуючої системи
Структура обслуговуючої системи визначається кількістю та взаємним розташуванням каналів обслуговування (механізмів, приладів тощо). Насамперед слід підкреслити, що система обслуговування може мати не один канал обслуговування, а кілька; система такого роду здатна обслуговувати одночасно кілька вимог. У цьому випадку всі канали обслуговування пропонують ті самі послуги, і, отже, можна стверджувати, що має місце паралельне обслуговування .
приклад. Каси у магазині.
Система обслуговування може складатися з декількох різнотипних каналів обслуговування, через які має пройти кожна вимога, що обслуговується, тобто в обслуговуючій системі процедури обслуговування вимог реалізуються послідовно . Механізм обслуговування визначає характеристики вихідного (обслуговуваного) потоку вимог.
приклад. Медична коміссія.
Комбіноване обслуговування - Обслуговування вкладів в ощадкасі: спочатку контролер, потім касир. Як правило, 2 контролери на одного касира.
Отже, функціональні можливості будь-якої системи масового обслуговування визначаються такими основними факторами :
- імовірнісним розподілом моментів надходжень заявок на обслуговування (поодиноких чи групових);
- потужністю джерела вимог;
- імовірнісним розподілом часу тривалості обслуговування;
- конфігурацією обслуговуючої системи (паралельне, послідовне або паралельно-послідовне обслуговування);
- кількістю та продуктивністю обслуговуючих каналів;
- дисципліною черги.
Основні критерії ефективності функціонування СМО
В якості основних критеріїв ефективності функціонування систем масового обслуговування в залежності від характеру розв'язуваної задачі можуть виступати:
- ймовірність негайного обслуговування заявки, що надійшла (Р обсл = До обс / До пост);
- ймовірність відмови в обслуговуванні заявки, що надійшла (P отк = До отк / До пост);
Вочевидь, що Р обсл + P отк =1.
Потоки, затримки, сервіс. Формула Поллачека-Хінчина
Затримка – один із критеріїв обслуговування СМО, час проведений заявкою в очікуванні обслуговування.
D i– затримка у черзі вимоги i;
W i = D i + S i– час перебування у системі вимоги i.
(з ймовірністю 1) – середня затримка вимоги в черзі, що встановилася;
(з ймовірністю 1) - середній час знаходження вимоги в СМО (waiting).
Q(t) -кількість вимог у черзі на момент часу t;
L(t)– кількість вимог у системі в момент часу t(Q(t)плюс кількість вимог, що знаходяться на обслуговуванні на момент часу t.
Тоді показники (якщо існують)
(з ймовірністю 1) – середнє за часом кількість вимог у черзі;
(з ймовірністю 1) – середня кількість часу, що встановилася серед часу, в системі.
Зауважимо, що ρ<1 – обязательное условие существования d, w, Qі Lу системі масового обслуговування.
Якщо згадати, що ρ= λ/( Nμ), то видно, що якщо інтенсивність надходження заявок більша, ніж Nμ, то ρ>1 і природно, що система не зможе впоратися з таким потоком заявок, а отже, не можна говорити про величини d, w, Qі L.
До найбільш загальних та необхідних результатів для систем масового обслуговування відносяться рівняння збереження
Слід звернути увагу на те, що згадані вище критерії оцінки роботи системи можуть бути аналітично обчислені для систем масового обслуговування M/M/N(N>1), т. е. систем з Марківськими потоками заявок та обслуговування. Для М/G/ l за будь-якого розподілу Gта для деяких інших систем. Взагалі, розподіл часу між надходженнями, розподіл часу обслуговування або обох цих величин має бути експоненціальним (або різновидом експоненційного розподілу Ерланга k-го порядку), щоб аналітичне рішення стало можливим.
Крім цього можна також говорити про такі характеристики, як:
- абсолютна пропускна здатність системи - А = Р обсл *λ;
- відносна пропускна здатність системи –
Ще один цікавий (і наочний) приклад аналітичного рішення – обчислення середньої затримки, що встановилася, в черзі для системи масового обслуговування M/G/ 1 за формулою:
.
У Росії ця формула відома як формула Поллачека – Хінчина, там ця формула пов'язується з ім'ям Росса (Ross).
Таким чином, якщо E(S)має більше значення, тоді перевантаження (у даному випадку вимірюється як d) буде більшою; чого й слід було чекати. За формулою можна знайти і менш очевидний факт: перевантаження також збільшується, коли мінливість розподілу часу обслуговування зростає, навіть якщо середній час обслуговування залишається незмінним. Інтуїтивно це можна пояснити так: дисперсія випадкової величини часу обслуговування може прийняти велике значення (оскільки вона має бути позитивною), тобто єдиний пристрій обслуговування буде зайнятий довгий часщо призведе до збільшення черги.
Предметом теорії масового обслуговуванняє встановлення залежності між факторами, що визначають функціональні можливості системи масового обслуговування, та ефективністю її функціонування. У більшості випадків усі параметри, що описують системи масового обслуговування, є випадковими величинами або функціями, тому ці системи належать до стохастичних систем.
Випадковий характер потоку заявок (вимог), а також, у випадку, і тривалості обслуговування призводить до того, що у системі масового обслуговування відбувається випадковий процес. За характером випадкового процесу , що відбувається в системі масового обслуговування (СМО), розрізняють системи марківські та немарківські . У марківських системах вхідний потік вимог і потік обслуговуваних вимог (заявок) є пуассонівськими. Пуассонівські потоки дозволяють легко описати та побудувати математичну модель системи масового обслуговування. Ці моделі мають досить прості рішення, тому більшість відомих додатків теорії масового обслуговування використовують марківську схему. У разі немарківських процесів завдання дослідження систем масового обслуговування значно ускладнюються та вимагають застосування статистичного моделювання, чисельних методів з використанням ЕОМ.
Курсова робота
"Імітаційне моделювання системи масового обслуговування"
за курсом «Дослідження операцій»
Вступ
При дослідженні операцій часто доводиться стикатися із системами, призначеними для багаторазового використання під час вирішення однотипних завдань. Виникаючі у своїй процеси отримали назву процесів обслуговування, а системи – систем масового обслуговування (СМО). Кожна СМО складається з певної кількості обслуговуючих одиниць (приладів, пристроїв, пунктів, станцій), які називаються каналами обслуговування. Каналами можуть бути лінії зв'язку, робочі точки, обчислювальні машини, продавці та ін. За кількістю каналів СМО поділяють на одноканальні та багатоканальні.
Заявки надходять у СМО зазвичай не регулярно, а випадково, утворюючи так званий випадковий потік заявок (вимог). Обслуговування заявок також триває якийсь випадковий час. Випадковий характер потоку заявок та часу обслуговування призводить до того, що СМО виявляється завантаженою нерівномірно: у якісь періоди часу накопичується дуже велика кількістьзаявок (вони або стають у чергу, або залишають СМО не обслуженими), в інші періоди СМО працює з недовантаженням або простоює.
Предметом теорії масового обслуговування є побудова математичних моделей, що пов'язують задані умови роботи СМО (кількість каналів, їх продуктивність, характер потоку заявок тощо) з показниками ефективності СМО, що описують її здатність справлятися з потоком заявок. Як показники ефективності СМО використовуються:
- Абсолютна пропускна здатність системи ( А
Q
– ймовірність відмовлення обслуговування заявки ();
k);
– середня кількість заявок у черзі ();
СМО ділять на 2 основних типи: СМО з відмовами та СМО з очікуванням (чергою). У СМО з відмовими заявка, що надійшла в момент, коли всі канали зайняті, отримує відмову, залишає СМО і в подальшому процесі обслуговування не бере участі (наприклад, заявка на телефонна розмовау момент, коли всі канали зайняті, отримує відмову та залишає СМО не обслуженою). У СМО з очікуванням заявка, яка прийшла в момент, коли всі канали зайняті, не йде, а стає на чергу на обслуговування.
Одним із методів розрахунку показників ефективності СМО є метод імітаційного моделювання. Практичне використаннякомп'ютерного імітаційного моделювання передбачає побудову відповідної математичної моделі, що враховує фактори невизначеності, динамічні характеристики та весь комплекс взаємозв'язків між елементами системи, що вивчається. Імітаційне моделювання роботи системи починається з деякого конкретного початкового стану. Внаслідок реалізації різних подій випадкового характеру модель системи переходить у наступні моменти часу в інші свої можливі стани. Цей еволюційний процес триває остаточного моменту планового періоду, тобто. до кінцевого моменту моделювання.
1. Основні характеристики CМО та показники їх ефективності
1.1 Поняття марковського випадкового процесу
Нехай є деяка система, яка з часом змінює свій стан випадковим чином. І тут кажуть, що у системі протікає випадковий процес.
Процес називається процесом з дискретними станами, якщо його стану можна заздалегідь перерахувати і перехід системи з одного стану до іншого відбувається стрибком. Процес називається процесом з безперервним часом, якщо переходи системи зі стану на стан відбуваються миттєво.
Процес роботи СМО – це випадковий процес із дискретними станами та безперервним часом.
Випадковий процес називають марківським або випадковим процесом без післядії, якщо для будь-якого моменту часу ймовірнісні характеристики процесу в майбутньому залежать тільки від його стану Наразіі не залежить від того, коли і як система прийшла в цей стан.
При аналізі процесів роботи СМО зручно користуватися геометричною схемою графом станів. Зазвичай стани системи зображуються прямокутниками, а можливі переходизі стану у стан – стрілками. Приклад графа станів наведено на рис. 1.
Потік подій – послідовність однорідних подій, наступних одне одним у випадкові моменти часу.
Потік характеризується інтенсивністю λ – частотою появи подій чи середнім числом подій, які у СМО в одиницю часу.
Потік подій називається регулярним, якщо події йдуть одна одною через певні рівні проміжки часу.
Потік подій називається стаціонарним, якщо його ймовірні характеристики не залежать від часу. Зокрема, інтенсивність стаціонарного потокуІснує величина стала: .
Потік подій називається ординарним, якщо ймовірність попадання на малу ділянку часу двох і більше подій мала в порівнянні з ймовірністю попадання однієї події, тобто якщо події з'являються в ньому поодинці, а не групами.
Потік подій називається потоком без післядії, якщо для будь-яких двох ділянок часу, що не перетинаються, і кількість подій, що потрапляють на одну з них, не залежить від числа подій, що потрапляють на інші.
Потік подій називається найпростішим (або стаціонарним пуассонівським), якщо він одночасно стаціонарний, ординарен і не має післядії.
1.2 Рівняння Колмогорова
Усі переходи в системі зі стану до стану відбуваються під деяким потоком подій. Нехай система перебуває у певному стані , з якого можливий перехід у стан , тоді вважатимуться, що у систему впливає найпростіший потік з інтенсивністю , переводящий її із стану . Як тільки з'являється перша подія потоку, відбувається її перехід. Для наочності на графі станів кожної стрілки, відповідної переходу, вказується інтенсивність . Такий розмічений граф станів дозволяє збудувати математичну модель процесу, тобто. знайти ймовірність усіх станів як функції часу. Їх складаються диференціальні рівняння, звані рівняннями Колмогорова.
Правило складання рівнянь Колмогорова:У лівій частині кожного з рівнянь стоїть похідна за часом від ймовірності цього стану. У правій частині стоїть сума творів усіх станів, у тому числі можливий перехід у цей стан, на інтенсивності відповідних потоків подій мінус сумарна інтенсивність всіх потоків, які виводять систему з цього стану, помножена на ймовірність цього стану.
Наприклад, для графа станів, наведеного на рис. 1, рівняння Колмогорова мають вигляд:
Т.к. у правій частині системи кожне доданок входить 1 раз зі знаком і 1 раз зі знаком , то, складаючи всі рівняння, отримаємо, що
,
,
Отже, одне із рівнянь системи можна відкинути та замінити рівнянням (1.2.1).
Щоб отримати конкретне рішення треба знати початкові умови, тобто. значення ймовірностей у початковий час.
1.3 Фінальні ймовірності та граф станів СМО
При досить великому часі перебігу процесів у системі (при ) можуть встановлюватися ймовірності станів, які від часу, які називаються фінальними ймовірностями, тобто. у системі встановлюється стаціонарний режим. Якщо кількість станів системи звісно, і з кожного їх за кінцеве число кроків м. перейти у будь-який інший стан, то фінальні ймовірності існують, тобто.
Сенс фінальних ймовірностей у тому, що вони рівні середньому відносному часу перебування системи у цьому стані.
Т.к. у стаціонарному стані похідні за часом дорівнюють нулю, то рівняння для фінальних ймовірностей виходять із рівнянь Колмогорова шляхом прирівнювання нулю їхніх правих частин.
Графи станів, що використовуються в моделях систем масового обслуговування, називаються схемою загибелі та розмноження. Така назва обумовлена тим, що ця схема використовується в біологічних задачах, пов'язаних із вивченням чисельності популяції. Його особливість полягає в тому, що всі стани системи можна подати у вигляді ланцюжка, в якому кожен із станів пов'язаний з попереднім і наступним (рис 2).
Мал. 2. Граф станів у моделях СМО
Припустимо, що всі потоки, що переводять систему з одного стану до іншого, найпростіші. За графом, представленим на рис. 2, складемо рівняння для фінальних ймовірностей системи. Вони мають вигляд:
 |
Виходить система з ( n +1) рівняння, що вирішується методом виключення. Цей метод полягає в тому, що послідовно всі можливості системи виражаються через можливість .
,
.
Підставляючи ці висловлювання останнє рівняння системи, знаходимо , потім знаходимо інші ймовірності станів СМО.
1.4 Показники ефективності СМО
Мета моделювання СМО полягає в тому, щоб розрахувати показники ефективності системи через її характеристики. Як показники ефективності СМО використовуються:
- Абсолютна пропускна здатність системи ( А), тобто. середня кількість заявок, що обслуговуються в одиницю часу;
- Відносна пропускна здатність ( Q), тобто. середня частка заявок, що надійшли, обслуговуються системою;
- Імовірність відмови (), тобто. ймовірність того, що заявка залишить СМО не обслуженою;
- Середня кількість зайнятих каналів ( k);
– середня кількість заявок до СМО ();
– середній час перебування заявки у системі ();
– середня кількість заявок у черзі () – довжина черги;
– середня кількість заявок у системі ();
– середній час перебування заявки у черзі ();
– середній час перебування заявки у системі ()
- Ступінь завантаження каналу (), тобто. ймовірність того, що канал зайнятий;
- Середня кількість заявок, що обслуговуються в одиницю часу;
- Середній час очікування обслуговування;
– ймовірність того, що кількість заявок у черзі перевищить певне значення тощо.
Доведено, що з будь-якому характері потоку заявок, за будь-якого розподілі часу обслуговування, за будь-якої дисципліни обслуговування, середній час перебування заявки у системі (черги) дорівнює середній кількості заявок у системі (черги), поділеному на інтенсивність потоку заявок, тобто.
(1.4.1)
Формули (1.4.1) та (1.4.2) називаються формулами Літтла. Вони випливають речей, що у граничному стаціонарному режимі середнє число заявок, які прибувають у систему, дорівнює середньому числу заявок, що залишають її, тобто. обидва потоки заявок мають однакову інтенсивність .
Формули для обчислення показників ефективності наведені у таблиці. 1.
Таблиця 1.
| Показники | Одноканальна СМО з |
Багатоканальна СМО з обмеженою чергою |
Фінальні ймовірності |
|
|
Ймовірність |
 |
 |
Абсолютна пропускна здатність |
 |
|
Відносна пропускна здатність |
 |
|
Середня кількість заявок у |
 |
 |
Середня кількість заявок під обслуговуванням |
 |
|
| Середня кількість заявок у системі |  |
1.5 Основні поняття імітаційного моделювання
Основна мета імітаційного моделювання полягає у відтворенні поведінки системи, що вивчається, на основі аналізу найбільш істотних взаємозв'язків її елементів.
Комп'ютерне імітаційне моделювання слід як статичний експеримент.
З теорії функцій випадкових величин відомо, що для моделювання випадкової величини з будь-якою безперервною та монотонно зростаючою функцією розподілу достатньо вміти моделювати випадкову величину, рівномірно розподілену на відрізку. Отримавши реалізацію випадкової величини, можна знайти відповідну їй реалізацію випадкової величини, оскільки вони пов'язані рівністю
Припустимо, що у деякій системі масового обслуговування час обслуговування однієї заявки розподілено за експоненційним законом з параметром , де – інтенсивність потоку обслуговування. Тоді функція розподілу часу обслуговування має вигляд
Нехай - реалізація випадкової величини , рівномірно розподіленої на відрізку , а відповідна їй реалізація випадкового часу обслуговування однієї заявки. Тоді, згідно (1.5.1)
1.6 Побудова імітаційних моделей
Перший етап створення будь-якої імітаційної моделі – етап опису реально існуючої системиу термінах характеристик основних подій. Ці події, як правило, пов'язані з переходами системи, що вивчається, з одного можливого стану в інший і позначаються як точки на тимчасовій осі. Для досягнення основної мети моделювання достатньо спостерігати систему у моменти реалізації основних подій.
Розглянемо приклад одноканальної системи масового обслуговування. Метою імітаційного моделювання подібної системи є визначення оцінок її основних характеристик, таких як середній час перебування заявки у черзі, середня довжина черги та частка часу простою системи.
Характеристики самого процесу масового обслуговування можуть змінювати свої значення або в момент надходження нової заявки на обслуговування, або після завершення обслуговування чергової заявки. До обслуговування чергової заявки СМО може розпочатись негайно (канал обслуговування вільний), але не виключена необхідність очікування, коли заявці доведеться зайняти місце в черзі (СМО з чергою, канал обслуговування зайнятий). Після завершення обслуговування чергової заявки СМО може відразу приступити до обслуговування наступної заявки, якщо вона є, але може простоювати, якщо така відсутня. Необхідну інформацію можна отримати, спостерігаючи різні ситуації, що виникають під час реалізації основних подій. Так, при надходженні заявки до СМО з чергою при зайнятому каналі обслуговування довжина черги збільшується на 1. Аналогічно довжина черги зменшується на 1, якщо завершено обслуговування чергової заявки та безліч заявок у черзі не порожнє.
Для експлуатації будь-якої імітаційної моделі потрібно вибрати одиницю часу. Залежно від природи моделюється такою одиницею може бути мікросекунда, година, рік і т.д.
Так як по своїй суті комп'ютерне імітаційне моделювання є обчислювальним експериментом, то його результати, що спостерігаються, в сукупності повинні володіти властивостями реалізації випадкової вибірки. Лише в цьому випадку буде забезпечена коректна статистична інтерпретація системи, що моделюється.
При комп'ютерному імітаційному моделюванні основний інтерес становлять спостереження, отримані після досягнення системою стаціонарного режиму функціонування, що вивчається, оскільки в цьому випадку різко зменшується вибіркова дисперсія.
Час, необхідне досягнення системою стаціонарного режиму функціонування, визначається значеннями її параметрів і початковим станом.
Оскільки основною метою є отримання даних спостережень із можливо меншою помилкою, то для досягнення цієї мети можна:
1) збільшити тривалість часу імітаційного моделювання процесу функціонування системи, що вивчається. У цьому випадку не тільки збільшується ймовірність досягнення системою стаціонарного режиму функціонування, а й зростає число псевдовипадкових чисел, що використовуються, що також позитивно впливає на якість одержуваних результатів.
2) при фіксованій тривалості часу Тімітаційного моделювання провести Nобчислювальних експериментів, званих ще прогонами моделі, з різними наборами псевдовипадкових чисел, кожен із яких дає одне спостереження. Всі прогони починаються при одному і тому ж початковому стані системи, що моделюється, але з використанням різних наборів псевдовипадкових чисел. Перевагою цього є незалежність одержуваних спостережень , показників ефективності системи. Якщо число Nмоделі досить велике, то межі симетричного довірчого інтервалудля параметра визначаються так:
, 
, тобто. 
, де
Виправлена дисперсія, 
,
N- Число прогонів програми, - надійність, .
2. Аналітичне моделювання СМО
2.1 Граф станів системи та рівняння Колмогорова
Розглянемо двоканальну систему масового обслуговування (n = 2) з обмеженою чергою, що дорівнює шести (m = 4). У СМО надходить найпростіший потік заявок із середньою інтенсивністю λ = 4,8 та показовим законом розподілу часу між надходженням заявок. Потік заявок, що обслуговуються в системі, є найпростішим із середньою інтенсивністю μ = 2 і показовим законом розподілу часом обслуговування.
Ця система має 7 станів, позначимо їх:
S 0 - Система вільна, немає заявок;
S 1 – 1 заявка на обслуговування, черга порожня;
S 2 – 2 заявки на обслуговуванні, черга порожня;
S 3 – 2 заявки на обслуговування, 1 заявка у черзі;
S 4 – 2 заявки на обслуговування, 2 заявки у черзі;
S 5 – 2 заявки на обслуговуванні, 3 заявки у черзі;
S 6 – 2 заявки на обслуговування, 4 заявки у черзі;
Імовірності приходу системи стану S 0 , S 1 , S 2 , …, S 6 відповідно рівні Р 0 , Р 1 , Р 2 , …, Р 6 .
Граф станів системи масового обслуговування є схемою загибелі та розмноження. Усі стани системи можна у вигляді ланцюжка, у якому кожен із станів пов'язані з попереднім і наступним.
Мал. 3. Граф станів двоканальної СМО
Для збудованого графа запишемо рівняння Колмогорова:
Для того щоб вирішити цю системупоставимо початкові умови:
Систему рівнянь Колмогорова (систему диференціальних рівнянь) Вирішимо чисельним методом Ейлера за допомогою програмного пакета Maple 11 (див. Додаток 1).
Метод Ейлера
де 
- у разі, це праві частини рівнянь Колмогорова, n=6.
Виберемо крок за часом. Припустимо, де Т- Це час, за який система виходить на стаціонарний режим. Звідси отримуємо кількість кроків 
. Послідовно Nраз обчислюючи за такою формулою (1) отримаємо залежності ймовірностей станів системи від часу, наведеної на рис. 4.
Значення ймовірностей СМО при рівні:
Мал. 4. Залежність ймовірностей станів системи від часу
|
|
|
|
|
|
При досить великому часі перебігу процесів у системі () можуть встановлюватися ймовірності станів, які від часу, які називаються фінальними ймовірностями, тобто. у системі встановлюється стаціонарний режим. Якщо кількість станів системи звичайно, і з кожного з них за кінцеве число кроків можна перейти в будь-яке інше стан, то фінальні ймовірності існують, тобто. 
Т.к. у стаціонарному стані похідні за часом дорівнюють 0, то рівняння для фінальних ймовірностей виходять із рівнянь Колмогорова шляхом прирівнювання правих частин 0. Запишемо рівняння для фінальних ймовірностей для нашої СМО.
Вирішимо цю систему лінійних рівнянь за допомогою програмного пакета Maple 11 (див. Додаток 1).
Отримаємо фінальні можливості системи:
Порівняння ймовірностей, отриманих із системи рівнянь Колмогорова при , з фінальними ймовірностями показує, що помилки 
рівні:
Тобто. досить малі. Це підтверджує правильність одержаних результатів.
2.3 Розрахунок показників ефективності системи за фінальнимі ймовірностями
Знайдемо показники ефективності системи обслуговування.
Спочатку обчислимо наведену інтенсивність потоку заявок:
1) Ймовірність відмовивши у обслуговуванні заявки, тобто. ймовірність того, що заявка залишає систему не обслуженою. У нашому випадку заявці відмовляється в обслуговуванні, якщо всі 2 канали зайняті, і черга максимально заповнена (тобто 4 особи в черзі), це відповідає стану системи S 6 . Т.к. ймовірність приходу системи стан S 6 дорівнює Р 6 , то
4) Середня довжина черги, тобто. середня кількість заявок у черзі, що дорівнює сумі творів числа заявок у черзі на ймовірність відповідного стану.
5) Середній час перебування заявки у черзі визначається формулою Літтла:
3. Імітаційне моделювання СМО
3.1 Алгоритм методу імітаційного моделювання СМО (покроковий підхід)
Розглянемо двоканальну систему масового обслуговування (n = 2) із максимальною довжиною черги рівною шести (m = 4). У СМО надходить найпростіший потік заявок із середньою інтенсивністю λ = 4,8 та показовим законом розподілу часу між надходженням заявок. Потік заявок, що обслуговуються в системі, є найпростішим із середньою інтенсивністю μ = 2 і показовим законом розподілу часом обслуговування.
Для імітації СМО скористаємося одним із методів статистичного моделювання – імітаційним моделюванням. Будемо використовувати покроковий підхід. Суть цього підходу в тому, що стан системи розглядаються в наступні моменти часу, крок між якими є досить малим, щоб за його час відбулося не більше однієї події.
Виберемо крок за часом (). Він може бути набагато менше середнього часу надходження заявки () і середнього часу її обслуговування (), тобто.
Де (3.1.1)
Виходячи з умови (3.1.1) визначимо крок за часом.
Час надходження заявки до СМО та час її обслуговування є випадковими величинами. Тому при імітаційному моделюванні СМО їх обчислення проводиться за допомогою випадкових чисел.
Розглянемо надходження заявки до СМО. Імовірність того, що на інтервалі до СМО надійде заявка, дорівнює: 
. Згенеруємо випадкове число , і якщо 
, то вважатимемо, що заявка цьому етапі до системи надійшла, якщо 
, то не вчинила.
У програмі це здійснює isRequested () . Інтервал часу приймемо постійним і рівним 0,0001, тоді відношення дорівнюватиме 10000. Якщо заявка надійшла, вона приймає значення «істина», інакше значення «брехня».
bool isRequested()
double r = R. NextDouble();
if (r< (timeStep * lambda))
Розглянемо тепер обслуговування заявки до СМО. Час обслуговування заявки у системі визначається виразом 
, де - Довільне число. У програмі час обслуговування визначається за допомогою функції GetServiceTime
()
.
double GetServiceTime()
double r = R. NextDouble();
return (-1/mu*Math. Log (1-r, Math.E));
Алгоритм методу імітаційного моделювання можна сформулювати в такий спосіб. Час роботи СМО ( Т) розбивається на кроки за часом dtна кожному з них виконується ряд дій. Спочатку визначаються стани системи (зайнятість каналів, довжина черги), потім за допомогою функції isRequested () , визначається, чи надійшла на цьому кроці заявка чи ні.
Якщо надійшла, і при цьому є вільні канали, то за допомогою функції GetServiceTime () генеруємо час обробки заявки та ставимо її на обслуговування. Якщо всі канали зайняті, а довжина черги менше 4, то поміщаємо заявку в чергу, якщо довжина черги дорівнює 4, то заявці буде відмовлено в обслуговуванні.
У разі, коли на цьому кроці заявка не надходила, а канал обслуговування звільнився, перевіряємо, чи є черга. Якщо є, то з черги заявку ставимо на обслуговування вільний канал. Після виконаних операцій час обслуговування для зайнятих каналів зменшуємо на величину кроку dt .
По закінченню часу Т, тобто після моделювання роботи СМО, обчислюються показники ефективності роботи системи і результати виводяться на екран.
3.2 Блок-схема програми
Блок-схема програми, що реалізує описаний алгоритм, наведено на рис. 5.
Мал. 5. Блок-схема програми
Розпишемо деякі блоки докладніше.
Блок 1. Встановлення початкових значень параметрів.
Random R; // Генератор випадкових чисел
public uint maxQueueLength; // Максимальна довжина черги
public uint channelCount; // Число каналів у системі
public double lambda; // Інтенсивність потоку надходження заявок
public double mu; // Інтенсивність потоку обслуговування заявок
public double timeStep; // Крокучасу
public double timeOfFinishProcessingReq; // Час закінчення обслуговування заявки у всіх каналах
public double timeInQueue; // Час перебування СМО у станах з чергою
public double processingTime; // Час роботисистеми
public double totalProcessingTime; // Сумарний час обслуговування заявок
public uint requestEntryCount; //Заявок, що надійшли
public uint declinedRequestCount; // Число відмовлених заявок
public uint acceptedRequestCount; // Числообслуговуваних заявок
uint queueLength; // Довжина черги //
Тип, що описує стани СМО
enum SysCondition (S0, S1, S2, S3, S4, S5, S6);
SysCondition currentSystemCondition; // Поточний стан системи
Завдання станів системи.Виділимо у цієї 2-х канальної системи 7 різних станів: S 0 , S 1 . S 6 . СМО перебуває у стані S 0 коли система вільна; S 1 – хоча один канал вільний; в стані S 2 коли всі канали зайняті, і є місце в черзі; у стані S 6 - всі канали зайняті, і черга досягла максимальної довжини (queueLength = 4).
Визначаємо поточний стан системи за допомогою функції GetCondition()
SysCondition GetCondition()
SysCondition p_currentCondit = SysCondition.S0;
int busyChannelCount = 0;
for (int i = 0; i< channelCount; i++)
if (timeOfFinishProcessingReq[i] > 0)
busyChannelCount++;
p_currentCondit + = k * (i + 1);
if (busyChannelCount > 1)
(p_currentCondit++;)
return p_currentCondit + (int) QueueLength;
Зміна часу перебування СМО у станах із довжиною черги 1, 2,3,4.Це реалізується наступним програмним кодом:
if (queueLength > 0)
timeInQueue += timeStep;
if (queueLength > 1)
(timeInQueue += timeStep;)
Є така операція, як розміщення заявки на обслуговування у вільний канал. Проглядаються, починаючи з першого, всі канали, коли виконується умовачасузакінченнямперіодингу Req [ i ] <= 0 (канал вільний), до нього подається заявка, тобто. генерується час закінчення обслуговування заявки.
for (int i = 0; i< channelCount; i++)
if (timeOfFinishProcessingReq [i]<= 0)
timeOfFinishProcessingReq [i] = GetServiceTime();
totalProcessingTime+= timeOfFinishProcessingReq [i];
Обслуговування заявок в каналах моделюється кодом:
for (int i = 0; i< channelCount; i++)
if (timeOfFinishProcessingReq [i] > 0)
timeOfFinishProcessingReq [i] -= timeStep;
Алгоритм методу імітаційного моделювання реалізовано мовою програмування C#.
3.3 Розрахунок показників ефективності СМО на основі результатів її імітаційного моделювання
Найбільш важливими є такі показники, як:
1) Ймовірність відмови у обслуговуванні заявки, тобто. ймовірність того, що заявка залишає систему не обслуженою. У нашому випадку заявці відмовляється в обслуговуванні, якщо всі 2 канали зайняті, і черга максимально заповнена (тобто 4 особи в черзі). Для знаходження ймовірності відмови розділимо час перебування СМО у стані з чергою 4 загальний час роботи системи.
2) Відносна пропускна здатність – це середня частка заявок, що надійшли, обслуговуються системою.
3) Абсолютна пропускна спроможність - це середня кількість заявок, що обслуговуються в одиницю часу.
4) Довжина черги, тобто. середня кількість заявок у черзі. Довжина черги дорівнює сумі творів числа осіб у черзі на ймовірність відповідного стану. Імовірності станів знайдемо як відношення часу знаходження СМО у цьому стані до загального часу роботи системи.
5) Середній час перебування заявки у черзі визначається формулою Літтла
6) Середня кількість зайнятих каналів визначається наступним чином:
7) Відсоток заявок, яким було відмовлено в обслуговуванні, перебуває за формулою
8) Відсоток обслужених заявок знаходиться за формулою
3.4 Статистична обробка результатів та їх порівняння з результатами аналітичного моделювання
Т.к. показники ефективності виходять у результаті моделювання СМО протягом кінцевого часу, вони містять випадкову компоненту. Тому для отримання більш надійних результатів потрібно провести їх статистичну обробку. З цією метою оцінимо довірчий інтервал для них за результатами 20 прогонів програми.
Величина потрапляє у довірчий інтервал, якщо виконується нерівність
, де
математичне очікування (середнє значення), що знаходиться за формулою
Виправлена дисперсія,
,
N =20 - Число прогонів,
- Надійність. При і N =20 .
Результат роботи програми представлено на рис. 6.
Мал. 6. Вид програми
Для зручності порівняння результатів, отриманих різними методами моделювання, представимо їх у вигляді таблиці.
Таблиця 2.
Показники ефективності СМО |
Результати аналітичного моделювання |
Результати імітаційного моделювання (послід. крок) |
Результати імітаційного моделювання | |
Нижня границя довірчого інтервалу |
Верхня межа довірчого інтервалу |
|||
| Ймовірність відмови | 0,174698253017626 | 0,158495148639101 |
0,246483801571923 | |
| Відносна пропускна спроможність | 0,825301746982374 | 0,753516198428077 | 0,841504851360899 | |
| Абсолютна пропускна спроможність | 3,96144838551539 | 3,61687775245477 | 4,03922328653232 | |
| Середня довжина черги | 1,68655313447018 | 1,62655862750852 | 2,10148609204869 | |
| Середній час перебування заявки у черзі | 0,4242558575 | 0,351365236347954 | 0,338866380730942 | 0,437809602510145 |
| Середня кількість зайнятих каналів | 1,9807241927577 | 1,80843887622738 | 2,01961164326616 | |
З табл. 2 видно, що результати, одержані при аналітичному моделюванні СМО, потрапляють у довірчий інтервал, одержаний за результатами імітаційного моделювання. Тобто результати, отримані різними методами, узгоджуються.
Висновок
У цій роботі розглянуто основні методи моделювання СМО та розрахунку показників їхньої ефективності.
Проведено моделювання двоканальної СМО з максимальною довжиною черги рівною 4 за допомогою рівнянь Колмогорова, а також знайдено фінальні ймовірності станів системи. Розраховано показники її ефективності.
Проведено імітаційне моделювання роботи такої СМО. На мові програмування C# складено програму, що імітує її роботу. Проведено серію розрахунків, за результатами яких знайдено значення показників ефективності системи та виконано їх статистичну обробку.
Отримані під час імітаційного моделювання результати узгоджуються з результатами аналітичного моделювання.
Література
1. Вентцель Є.С. Дослідження операцій. - М.: Дрофа, 2004. - 208 с.
2. Волков І.К., Загоруйко О.О. Дослідження операцій. - М.: Вид.-во МДТУ ім. н.е. Баумана, 2002. - 435 с.
3. Волков І.К., Зуєв С.М., Цвєткова Г.М. Випадкові процеси. - М.: Вид.-во МДТУ ім. н.е. Баумана, 2000. - 447 с.
4. Гмурман В.Є. Керівництво до вирішення завдань з теорії ймовірностей та математичної статистики. - М.: Вища школа, 1979. - 400 с.
5. Івницький В.Л. Теорія мереж масового обслуговування. - М.: Фізматліт, 2004. - 772 с.
6. Дослідження операцій на економіці/ під ред. Н.Ш. Кремер. - М.: Юніті, 2004. - 407 с.
7. Таха Х.А. Введення у дослідження операцій. - М.: ВД «Вільямс», 2005. - 902 с.
8. Харін Ю.С., Малюгін В.І., Кирлиця В.П. та ін. Основи імітаційного та статистичного моделювання. - Мінськ: Дизайн ПРО, 1997. - 288 с.
Розрахунок показників ефективності відкритої одноканальної СМО з відмовами. Розрахунок показників ефективності відкритої багатоканальної СМО з відмовами. Розрахунок показників ефективності багатоканальної СМО з обмеженням на довжину черги. Розрахунок показників ефективності багатоканальної СМО очікуванням.
1. Потоки заявок до СМО
2. Закони обслуговування
3. Критерії якості роботи СМО
4.
5. Параметри моделей черг. При аналізі систем масового
6. I. Модель А – модель одноканальної системи масового обслуговування з Пуассонівським вхідним потоком заявок та Експоненційним часом обслуговування.
7. ІІ. Модель – багатоканальна система обслуговування.
8. ІІІ. Модель С – модель із постійним часом обслуговування.
9. IV. Модель D – модель із обмеженою популяцією.
Потоки заявок до СМО
Потоки заявок бувають вхідні та вихідні.
Вхідний потік заявок – це тимчасова послідовність подій на вході СМО, на яку поява події (заявки) підпорядковується імовірнісним (або детермінованим) законам. Якщо вимоги обслуговування приходять у відповідність, з яким – чи графіком (наприклад, автомобілі приїжджають на АЗС кожні 3 хвилини) такий потік підпорядковується детермінованим (певним) законам. Але, зазвичай, надходження заявок підпорядковується випадковим законам.
Для опису випадкових законів теорії масового обслуговування вводиться на розгляд модель потоків подій. Потоком подій називається послідовність подій, що йдуть одна за одною у випадкові моменти часу.
Як події можуть фігурувати надходження заявок на вхід СМО (на вхід блоку черги), поява заявок на вході приладу обслуговування (на виході блоку черги) та поява обслужених заявок на виході СМО.
Потоки подій мають різні властивості, які дозволяють розрізняти різні типи потоків. Насамперед, потоки можуть бути однорідними і неоднорідними.
Однорідні потоки – такі потоки, у яких потік вимог має однакові властивості: мають пріоритет першим прийшов – першим обслужений, оброблювані вимоги мають однакові фізичні властивості.
Неоднорідні потоки – такі потоки, у яких вимоги мають неоднаковими властивостями: вимоги задовольняються за принципом пріоритетності (приклад, карта переривань в ЕОМ), оброблювані вимоги мають різні фізичні властивості.
Схематично неоднорідний потік подій може бути зображений таким чином
Відповідно, можна використовувати кілька моделей СМО для обслуговування неоднорідних потоків: одноканальна СМО з дисципліною черги, що враховує пріоритети неоднорідних заявок, і багатоканальна СМО з індивідуальним каналом для кожного типу заявок.
Регулярним потоком називається потік, у якому події слідують одна одною через однакові проміжки часу. Якщо позначити через – моменти появи подій, причому через інтервали між подіями, то для регулярного потоку
Рекурентний потік відповідно визначається як потік, для якого всі функції розподілу інтервалів між заявками
збігаються, тобто
Фізично рекурентний потік є таку послідовність подій, на яку всі інтервали між подіями хіба що " ведуть себе " однаково, тобто. підкоряються одному й тому закону розподілу. Таким чином, можна дослідити лише один якийсь інтервал і отримати статистичні характеристики, які будуть справедливі для решти інших інтервалів.
Для характеристики потоків часто вводять у розгляд ймовірність розподілу числа подій у заданому інтервалі часу , яка визначається так:
де - Число подій, що з'являються на інтервалі .
Потік без післядії характеризується тим властивістю, що з двох неперетинних інтервалів часу і , де , , , ймовірність появи числа подій другому інтервалі залежить від кількості появи подій першому інтервалі.
Відсутність післядії означає відсутність імовірнісної залежності подальшого перебігу процесу від попереднього. Якщо є одноканальна СМО з часом обслуговування, то при потоці заявок без післядії на вході системи вихідний потік буде з післядією, оскільки заявки на виході СМО не з'являються частіше, ніж інтервал. У регулярному потоці, в якому події йдуть одна за одною через певні проміжки часу, є найжорсткіша післядія.
Потоком з обмеженою післядією називається такий потік, для якого інтервали між подіями є незалежними.
Потік називається стаціонарним, якщо можливість появи якогось числа подій на інтервалі часу залежить тільки від довжини цього інтервалу і не залежить від його розташування на осі часу. Для стаціонарного потоку подій середня кількість подій за одиницю часу постійно.
Ординарним потоком називається такий потік, для якого ймовірність попадання на даний малий відрізок часу dt двох і більше вимог зневажливо мала порівняно з ймовірністю попадання однієї вимоги.
Потік, який має властивості стаціонарності, відсутності післядії та ординарності називають пуассонівським (найпростішим). Цей потік займає центральне місце серед всього різноманіття потоків, так само як випадкові величини або процеси з нормальним законом розподілу прикладної теорії ймовірності.
Пуасонівський потік описується такою формулою:
,
де - ймовірність появи подій за час, - Інтенсивність потоку.
Інтенсивністю потоку називають середню кількість подій, які виникають за одиницю часу.
Для пуасонівського потоку інтервали часу між заявками розподілені за експоненційним законом
Потоком з обмеженою післядією, для якого інтервали часу між заявками розподілені за нормальним законом, називається нормальним потоком.
Закони обслуговування
Режим обслуговування (час обслуговування), як і режим надходження заявок, може бути або постійним, або випадковим. У багатьох випадках час обслуговування підпорядковується експоненційному розподілу.
Імовірність того, що обслуговування закінчиться до моменту t, дорівнює:
де – щільність потоку заявок
Звідки щільність розподілу часу обслуговування
Подальшим узагальненням експоненційного закону обслуговування може бути закон розподілу Ерланга, коли кожен інтервал обслуговування підпорядковується закону:
де - Інтенсивність вихідного пуассонівського потоку, k - Порядок потоку Ерланга.
Критерії якості роботи СМО
Ефективність роботи СМО оцінюється різними показниками залежно від ланцюга та типу СМО. Найбільшого поширення набули такі:
Абсолютна пропускна здатність СМО з відмовами (продуктивність системи) – середня кількість вимог, які може опрацювати система.
Відносна пропускна здатність СМО - відношення середньої кількості вимог, оброблених системою, до середньої кількості вимог, що надійшли на вхід СМО.
Середня тривалість простою системи.
Для СМО з чергою додаються такі характеристики:
Довжина черги, яка залежить від низки факторів: від того, коли і скільки вимог надійшло до системи, скільки часу витрачено на обслуговування вимог, що надійшли. Довжина черги є випадковою величиною. Від довжини черги залежить ефективність роботи системи обслуговування.
Для СМО з обмеженим очікуванням у черзі важливі всі перелічені характеристики, а систем з необмеженим очікуванням абсолютна і відносна пропускна здатність СМО втрачають сенс.
На рис. 1 наведено системи обслуговування різної конфігурації.
Параметри моделей черг. При аналізі систем масовогоДля обслуговування використовуються технічні та економічні характеристики.
Найчастіше використовуються такі Технічні характеристики:
1) середній час, який клієнт проводить у черзі;
2) середня довжина черги;
3) середній час, який клієнт проводить у системі обслуговування (час очікування плюс час обслуговування);
4) середня кількість клієнтів у системі обслуговування;
5) ймовірність того, що система обслуговування виявиться незайнятою;
6) ймовірність певної кількості клієнтів у системі.
Серед економічних характеристик найбільший інтерес становлять такі:
1) витрати очікування у черзі;
2) витрати очікування у системі;
3) Витрати обслуговування.
Моделі систем масового обслуговування. Залежно від поєднання наведених характеристик можуть розглядатися різні моделі систем масового обслуговування.
Тут ми ознайомимося з декількома найвідомішими моделями. Усі вони мають такі загальні характеристики:
А) пуассонівський розподіл ймовірностей надходження заявок;
Б) стандартне поведінка клієнтів;
В) правило обслуговування FIFO (першим прийшов – першим обслужений);
г) єдина фаза обслуговування.
I. Модель А – модель одноканальної системи масового обслуговування М/М/1 з Пуассонівським вхідним потоком заявок та Експоненційним часом обслуговування.
Найчастіше зустрічаються завдання масового обслуговування з єдиним каналом. І тут клієнти формують одну чергу до єдиного пункту обслуговування. Припустимо, що з систем цього виконуються такі условия:
1. Заявки обслуговуються за принципом «першим прийшов – першим обслужений» (FIFO), причому кожен клієнт чекає своєї черги до кінця незалежно від довжини черги.
2. Появи заявок є незалежними подіями, однак середня кількість заявок, що надходять в одиницю часу, є незмінною.
3. Процес надходження заявок описується пуасонівським розподілом, причому заявки надходять з необмеженої множини.
4. Час обслуговування описується експонентним розподілом ймовірностей.
5. Темп обслуговування вищий за темп надходження заявок.
Нехай - число заявок в одиницю часу;
μ – кількість клієнтів, які обслуговуються в одиницю часу;
n – кількість заявок у системі.
Тоді система масового обслуговування описується рівняннями, наведеними нижче.
Формули для опису системи М/М/1:
Середній час обслуговування одного клієнта у системі (час очікування плюс час обслуговування);
Середня кількість клієнтів у черзі;
Середній час очікування клієнта у черзі;
Характеристика завантаженості системи (частка часу, протягом якого система зайнята обслуговуванням);
Ймовірність відсутності заявок у системі;
Імовірність того, що в системі знаходиться більш ніж K заявок.
ІІ. Модель - багатоканальна система обслуговування M/M/S.У багатоканальній системі для обслуговування відкрито два канали або більше. Передбачається, що клієнти очікують у загальній черзі і звертаються до першого звільненого каналу обслуговування.
Приклад такої багатоканальної однофазової системи можна побачити в багатьох банках: із загальної черги клієнти звертаються в перше віконце для обслуговування, що звільнилося.
У багатоканальній системі потік заявок підпорядковується Пуассонівському закону, а час обслуговування - Експонентному. Той, хто приходить першим, обслуговується першим, і всі канали обслуговування працюють в однаковому темпі. Формули, що описують модель, досить складні для використання. Для розрахунку параметрів багатоканальної системи обслуговування зручно використати відповідне програмне забезпечення.
Час перебування заявки у черзі;
Час перебування заявки у системі.
ІІІ. Модель С – модель з постійним часом обслуговування M/D/1.
Деякі системи мають постійний, а не експоненційно розподілений час обслуговування. У таких системах клієнти обслуговуються протягом фіксованого періоду часу, як, наприклад, автоматичного миття автомобілів. Для моделі З постійним темпом обслуговування значення величин Lq і Wq Вдвічі менше, ніж відповідні значення моделі А, що має змінний темп обслуговування.
Формули, що описують модель С:
Середня довжина черги;
Середній час очікування у черзі;
Середня кількість клієнтів у системі;
Середній час очікування у системі.
IV. Модель D – модель з обмеженою популяцією.
Якщо кількість потенційних клієнтів системи обслуговування обмежена, ми маємо справу зі спеціальною моделлю. Таке завдання може виникнути, наприклад, якщо йдеться про обслуговування обладнання фабрики, що має п'ять верстатів.
Особливість цієї моделі в порівнянні з трьома розглянутими раніше в тому, що існує взаємозалежність між довжиною черги і темпом надходження заявок.
V. Модель Е – модель з обмеженою чергою. Модель відрізняється від попередніх тим, що кількість місць у черзі обмежується. У цьому випадку заявка, яка прибула в систему, коли всі канали та місця у черзі зайняті, залишає систему необслуженою, тобто отримує відмову.
Як окремий випадок моделі з обмеженою чергою можна розглядати Модель з відмовами, якщо кількість місць у черзі скоротити до нуля.
1. Показники ефективності використання СМО:
Абсолютна пропускна спроможність СМО – середня кількість заявок, що смо-
е обслужити СМО в одиницю часу.
Відносна пропускна здатність СМО – відношення середньої кількості заявок,
обслуговуваних СМО в одиницю часу, до середнього числа надійшли за це ж
час заявок.
Середня тривалість періоду зайнятості СМО.
Коефіцієнт використання СМО - середня частка часу, протягом якого
СМО зайнята обслуговуванням заявок тощо.
2. Показники якості обслуговування заявок:
Середній час очікування заявки у черзі.
Середній час перебування заявки до СМО.
Можливість відмови заявці в обслуговуванні без очікування.
Імовірність того, що заявка, що знову надійшла, негайно буде прийнята до обслуговування.
Закон розподілу часу очікування заявки у черзі.
Закон розподілу часу перебування заявки до СМО.
Середня кількість заявок, які перебувають у черзі.
Середня кількість заявок, що перебувають у СМО, тощо.
3. Показники ефективності функціонування пари «СМО – клієнт», де під «клієнтом» розуміють всю сукупність заявок чи їхнє джерело. До таких показників належить, наприклад, середній дохід, який приносить СМО в одиницю часу
Класифікація систем масового обслуговування
За кількістю каналів СМО:
одноканальні(Коли є один канал обслуговування)
багатоканальніточніше n-канальні (коли кількість каналів n≥ 2).
З дисципліни обслуговування:
1. СМО з відмовами, в яких заявка, що надійшла на вхід СМО у момент, коли всі
канали зайняті, отримує «відмову» та залишає СМО («зникає»). Щоб ця заявка все ж
була обслужена, вона повинна знову надійти на вхід СМО і розглядатись при цьому як заявка, яка надійшла вперше. Прикладом СМО з відмовами може бути робота АТС: якщо набраний телефонний номер (заявка, що надійшла на вхід) зайнятий, то заявка отримує відмову, і, щоб додзвонитися за цим номером, його слід набрати ще раз.
2. СМО з очікуванням(необмеженим очікуваннямабо чергою). У таких системах
заявка, що надійшла в момент зайнятості всіх каналів, стає в чергу і чекає на звільнення каналу, який прийме її до обслуговування. Кожна заявка, яка надійшла на вхід, зрештою буде обслужена. Такі СМО часто зустрічаються у торгівлі, у сфері побутового та медичного обслуговування, на підприємствах (наприклад, обслуговування верстатів бригадою наладчиків).
3. СМО змішаного типу(з обмеженим очікуванням). Це такі системи, де на перебування заявки в черзі накладаються деякі обмеження.
Ці обмеження можуть накладатися на довжину черги, тобто. максимально можливе
кількість заявок, які одночасно можуть перебувати у черзі. Як приклад такої системи можна навести майстерню з ремонту автомобілів, що має обмежену за розмірами стоянку для несправних машин, що чекають на ремонт.
Обмеження очікування можуть стосуватися часу перебування заявки у черзі, за істи-
ченню якого вона виходить із черги і залишає систему).
У СМО з очікуванням і СМО змішаного типу застосовуються різні схеми про-
служіння заявок із черги. Обслуговування може бути упорядкованим, коли заявки з черги обслуговуються в порядку їх надходження до системи, та невпорядкованим, у якому заявки з черги обслуговуються у випадковому порядку. Іноді застосовується обслуговування з пріоритетомколи деякі заявки з черги вважаються пріоритетними і тому обслуговуються в першу чергу.
По обмеженню потоку заявок:
замкнутіі відкриті.
Якщо потік заявок обмежений і заявки, що залишили систему, можуть до неї повертати-
ся, то СМО є замкненою, в іншому випадку - відкритою.
За кількістю етапів обслуговування:
однофазніі багатофазні
Якщо канали СМО однорідні, тобто. виконують одну і ту ж операцію обслугову-
ня, то такі СМО називаються однофазними. Якщо канали обслуговування розташовані послідовно і вони неоднорідні, оскільки виконують різні операції обслуговування (тобто обслуговування складається з кількох послідовних етапів чи фаз), то СМО називається багатофазний. Приклад роботи багатофазної СМО є обслуговування автомобілів на станції технічного обслуговування (мийка, діагностування і т.д.).
