Як показники ефективності СМО з очікуванням, крім вже відомих показників - абсолютної А та відносної 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), сходится к сумме, равной . Поэтому
(33)
та з урахуванням співвідношень (17)

знайдемо граничні ймовірності інших станів
(34)
Граничні ймовірності p 0 , p 1 , p 2 , …, p k , … утворюють спадну геометричну професію зі знаменником р< 1, следовательно, вероятность р 0 - наибольшая. Это означает, что если СМО справляется с потоком заявок (при ρ < 1), то наиболее вероятным будет отсутствие заявок в системе.
Середня кількість заявок у системі L сист. визначимо за формулою математичного очікування, яка з урахуванням (34) набуде вигляду
(35)
(підсумовування від 1 до ∞, оскільки нульовий член 0p 0 =0).
Можна показати, що формула (35) перетворюється (при ρ< 1) к виду
(36)
Знайдемо середню кількість заявок у черзі L оч. Очевидно, що
(37)
де L про. - Середня кількість заявок, що знаходяться під обслуговуванням.
Середня кількість заявок під обслуговуванням визначимо за формулою математичного очікування числа заявок під обслуговуванням, що приймає значення 0 (якщо канал вільний) або 1 (якщо канал зайнятий):

тобто. середня кількість заявок під обслуговуванням дорівнює ймовірності того, що канал зайнятий:
(38)
В силу (33)
(39)
Тепер за формулою (37) з урахуванням (36) та (39)
(40)
Доведено, що за будь-якого характеру потоку заявок, за будь-якого розподілу часу обслуговування, за будь-якої дисципліни обслуговування середній час перебування заявки в системі (черги) дорівнює середній кількості заявок у системі (у черзі), поділеному на інтенсивність потоку заявок,тобто.
(41)
(42)
Формули (41) та (42) називаються формулами Літтла.Вони випливають із того, що в граничному, стаціонарному режимі середня кількість заявок, що прибувають до системи, дорівнює середній кількості заявок, що залишають її:обидва потоки заявок мають ту саму інтенсивність λ.
На підставі формул (41) та (42) з урахуванням (36) та (40) середній час перебування заявки в системі визначиться за формулою:
(43)
а середній час перебування заявки у черзі
(44)
Багатоканальна СМО з необмеженою чергою. Розглянемо завдання. Є 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.

Рис. 9
Можна показати, що за r/n< 1 предельные вероятности существуют. Если r/n >1, черга зростає до безкінечності. Використовуючи формули (16) і (17) для процесу загибелі та розмноження, можна отримати такі формули для граничних ймовірностей станів n-канальної СМО з необмеженою чергою
(45)
(46)
(47)
Імовірність того, що заявка опиниться в черзі,
(48)
Для n-канальної СМО з необмеженою чергою, використовуючи попередні прийоми, можна знайти:
середня кількість зайнятих каналів
(49)
середня кількість заявок у черзі
(50)
середня кількість заявок у системі
(51)
Середній час перебування заявки у черзі та середній час перебування заявки у системі, як і раніше, перебувають за формулами Літтла (42) та (41).
Зауваження.Для СМО з необмеженою чергою при r< 1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа P отк = 0, относительная пропускная способность Q = 1 а абсолютна пропускна здатність дорівнює інтенсивності вхідного потоку заявок, тобто. А = l.

СМО з обмеженою чергою

СМО з обмеженою чергою.СМО з обмеженою чергою відрізняються від розглянутих вище завдань лише тим, що кількість заявок у черзі обмежена (не може перевищувати певного заданого т).Якщо нова заявка надходить у момент, коли усі місця у черзі зайняті, вона залишає СМО необслуженной, тобто. отримує відмову.
Очевидно: для обчислення граничних ймовірностей станів та показників ефективності таких СМО може бути використаний той самий підхід, що й вище, з тією різницею, що підсумовувати треба не нескінченну прогресію (як, наприклад, ми робили при виведенні формули (33)), а кінцеву .
Середній час перебування заявки в черзі та в системі, як і раніше, визначаємо за формулами Літтла (44) та (43).
СМО з обмеженим часом очікування.Насправді часто зустрічаються СМО з про " нетерплячими " заявками. Такі заявки можуть піти з черги, якщо час очікування перевищує певну величину. Зокрема, такі заявки виникають у різних технологічних системах, у яких затримка з початком обслуговування може призвести до втрати якості продукції, в системах оперативного управління, коли термінові повідомлення втрачають цінність (або навіть сенс), якщо вони не надходять на обслуговування протягом певного часу.

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

На закінчення відзначимо, що на практиці часто зустрічаються замкнуті системи обслуговування, у яких вхідний потік заявок істотно залежить від стану самої СМО. Як приклад можна навести ситуацію, коли на ремонтну базу надходять з місць експлуатації деякі машини: зрозуміло, що чим більше машин перебуває в стані ремонту, тим менше їх продовжує експлуатуватися і тим менша інтенсивність потоку машин, що знову надходять на ремонт. Для замкнутих СМО характерною є обмежена кількість джерел заявок, причому кожне джерело "блокується" на час обслуговування його заявки (тобто він не видає нових заявок). У подібних системах при кінцевому числі станів СМО граничні ймовірності існуватимуть за будь-яких значень інтенсивностей потоків заявок та обслуговування. Вони можуть бути обчислені, якщо знову звернутися до процесу загибелі та розмноження.

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

регулярні системи, т. е. системи, у яких потоки поводяться передбачуваним чином (відомі величина потоку та його появи в каналі). У разі, коли канал один, розрахунок системи тривіальний. Очевидно, що між інтенсивністю потоку λ та швидкістю обслуговування зє співвідношення λ < c;

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

Цікавішим є випадок регулярного потоку, який розподіляється по мережі каналів. Очевидно, що умова λ < cзберігається для кожного каналу. При цьому виникає складне комбінаторне завдання.

Є сім доріг:

2. A→B→D→E→F

3. A→C→B→ E→F

   A→C→B→D→E→F

   A→C→B→ D→F

Необхідно перевезти вантаж із Ав F. Пропускна спроможність кожного каналу відома. Яка пропускна спроможність мережі та яким шляхом має слідувати потік? Вирішити це завдання можна за допомогою теореми про максимальному потоці, що ми розглядали раніше (рис.6).

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

У випадку система масового обслуговування то, можливо представлена ​​малюнку 7.

Рис. 7.

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

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

середня кількість заявок, які може обслужити СМО за одиницю часу;

середня кількість заявок, які отримують відмову та залишають СМО;

ймовірність того, що заявка, що надійшла, негайно буде обслужена;

середній час очікування у черзі;

середня кількість заявок у черзі;

середній дохід СМО в одиницю часу та інші економічні показники СМО.

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

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

Класифікація систем масового обслуговування

СМО можуть бути двох видів:

СМО із відмовими;

СМО з очікуванням (тобто з чергою).

Обслуговування в системах з чергою може мати різний характер:

обслуговування може бути впорядкованим;

обслуговування у випадковому порядку;

обслуговування з пріоритетом, причому пріоритет може бути з перериванням і без переривання.

Системи з чергою поділяються на:

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

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

Для СМО з відмовами використовуються такі показники ефективності:

абсолютна пропускна спроможність А- Середня кількість заявок, яка може бути обслуговується в одиницю часу;

відносна пропускна спроможність Q- Відносна середня кількість заявок. При цьому відносну пропускну здатність можна знайти за формулою

Де λ – це інтенсивність надходження заявок до СМО.

Для СМО з очікуванням абсолютна пропускна спроможність Аі відносна пропускна спроможність Qвтрачають сенс, але важливими стають інші характеристики:

одиниця часу очікування у черзі;

середня кількість заявок у черзі;

середній час перебування у системі.

Для СМО з обмеженою чергою цікаві обидві групи показників.

Більш складні завдання теорії масового обслуговування

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

До цих пір ми займалися лише найпростішими СМО, для яких усі потоки подій, що переводить їх зі стану в стан, були найпростішими. А як бути, якщо вони не найпростіші? Наскільки реальне це припущення? Наскільки значними є помилки, до яких воно призводить, коли воно порушується? На всі ці питання ми спробуємо відповісти тут.

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

1. n-канальна СМО з відмовами, з найпростішим потоком заявок та довільним розподілом часу обслуговування.У попередньому параграфі ми вивели формули Ерланга (20.4), (20.5) для фінальних ймовірностей станів СМО з відмовами. Порівняно недавно (1959 р.) Б. А. Севастьянов довів, що це формули справедливі як за показовому, а й за довільному розподілі часу обслуговування.

^ 2. Одноканальна СМО з необмеженою чергою, найпростішим потоком заявок та довільним розподілом часу обслуговування. Якщо на одноканальну СМО з необмеженою чергою надходить найпростіший потік заявок з інтенсивністю , а час обслуговування має довільний розподіл із математичним очікуванням tпро = 1/μ. та коефіцієнтом варіації vμ , то середня кількість заявок у черзі дорівнює

а середня кількість заявок у системі

(21.2)

Де, як і раніше, ρ = λ/μ ., a v μ -відношення середнього квадратичного відхиленнячасу обслуговування для його математичного очікування. Формули (21.1), (21.2) звуться формул Полячека - Хінчина.

Ділячи Lоч, і Lсист на λ, отримаємо, згідно з формулою Літтла, середній час перебування заявки у черзі та середній час перебування в системі:

(21.3)

(21.4)

Зауважимо, що в окремому випадку, коли час обслуговування - показовий, vμ = 1 і формули (21.1), (21.2) перетворюються на вже знайомі нам формули (20.16), (20.20) для найпростішої одноканальної СМО. Візьмемо інший окремий випадок - коли час обслуговування взагалі не випадковий і vμ = 0. Тоді середня кількість заявок у черзі зменшується вдвічі порівняно з найпростішим випадком. Це й природно: якщо обслуговування заявки протікає організованіше, «регулярніше», то СМО працює краще, ніж при погано організованому, безладному обслуговуванні.

^ 3. Одноканальна СМО з довільним потоком заявок та довільним розподілом часу обслуговування.Розглядається одноканальна СМО з необмеженою чергою, на яку надходить довільний рекурентний потік заявок з інтенсивністю λ та коефіцієнтом варіації vλ інтервалів між заявками, укладеними між нулем та одиницею: 0< v λ < 1. Час обслуговування Ттакож має довільний розподіл із середнім значенням tпро = 1/μ та коефіцієнтом варіації v μ,теж укладеним між нулем та одиницею. Для цього випадку точних аналітичних формул одержати не вдається;

можна лише приблизно оцінити середню довжину черги, обмежити її зверху і знизу.

Доведено, що у цьому випадку

Якщо вхідний потік – найпростіший, то обидві оцінки – верхня та нижня – збігаються, і виходить формула Полячека – Хінчина (21.1). Для грубо наближеної оцінки середньої довжини черги М. А. Файнбергом (див.) отримана дуже проста формула:

(21.6)

Середня кількість заявок у системі виходить з Lоч простим додатком ρ - середньої кількості заявок, що обслуговуються:

Lсист = Lоч + ρ. (21.7)

Що стосується середніх часів перебування заявки в черзі та в системі, то вони обчислюються через Lоч і Lсист за формулою Літтла розподілом на λ .

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

Виникає природне питання: а як же справа з багатоканальними немарківськими СМО? З усією відвертістю відповімо: погано. Точних аналітичних методів таких систем немає. Єдине, що ми завжди можемо знайти, це середня кількість зайнятих каналів k =ρ. Що стосується Lоч, Lсист, Wоч, Wсист, то їм таких загальних формул написати не вдається.

Щоправда, якщо каналів справді багато (4-5 чи більше), то непоказовий час обслуговування не страшний: був би вхідний потік найпростішим. Справді, загальний потік звільнень каналів складається з потоків звільнень окремих каналів, а в результаті такого накладання (суперпозиції) виходить, як ми знаємо, потік, близький до найпростішого. Тож у разі заміна непоказового розподілу часу обслуговування показовим призводить до порівняно малим помилкам. На щастя, вхідний потік заявок у багатьох завданнях практики близький до найпростішого.

Гірша справа, коли вхідний потік свідомо не найпростіший. Ну, у разі доводиться пускатися на хитрощі. Наприклад, підібрати дві одноканальні СМО, з яких одна за своєю ефективністю свідомо «краще» даної багатоканальної, а інша – свідомо «гірша» (черга більше, час очікування більше). А для одноканальної СМО ми сяк-так вже вміємо знаходити характеристики в будь-якому випадку.

Як же підібрати такі одноканальні СМО – «найкращу» та «найгіршу»? Це можна зробити по-різному. Виявляється, свідомо найгірший варіант можна отримати, якщо розчленувати дану n-канальну СМО на подноканальних, а загальний надходить на них найпростіший потік розподіляти між цими одноканальними СМО в порядку черги: першу заявку - в першу СМО, другу - в другу і т. д. Ми знаємо, що при цьому на кожну СМО надходитиме потік Ерланга n-го порядку, з коефіцієнтом варіації, рівним 1/. Що ж до коефіцієнта варіації часу обслуговування, він залишається незмінним. Для такої одноканальної СМО ми вже вміємо обчислювати час перебування заявки у системі Wсист; воно буде свідомо більше, ніж для вихідної n-канальної СМО. Знаючи цей час, можна дати «песимістичну» оцінку і для середньої кількості заявок у черзі, користуючись формулою Літтла і помножуючи середній час на інтенсивність загального потоку заявок. Оптимістичну оцінку можна отримати, замінюючи n-канальну СМО однієї одноканальної, але з інтенсивністю потоку обслуговування в nразів більшою, ніж у даної, рівної nμ. Природно, при цьому параметр ρ теж повинен бути, змінений, зменшений nразів. Для такої СМО часперебування заявки у системі Wсист зменшується за рахунок того, що обслуговування триває в nразів менше. Користуючись зміненим значенням, коефіцієнтом варіації вхідного потоку vλ та часу обслуговування v μ , ми можемо приблизно обчислити середню кількість заявок у системі . Віднімаючи з нього первісне (не змінене) значення ρ, ми отримаємо середню кількість заявок у черзі . Обидві характеристики будуть меншими, ніж для вихідної n-канальної СМО (являтимуть собою «оптимістичні» оцінки) Від них, поділяючи на λ , можна перейти до «оптимістичних» оцінок для часу перебування у СМО та в черзі.

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

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

немає черги:

Усі канали вільні;

Зайнятий один канал, інші вільні;

Зайняті каналів, решта немає;

Зайняті всі канали, вільних немає;

є черга:

Зайнято всі n каналів; одна заявка стоїть у черзі;

Зайняті всі n каналів, r заявок у черзі;

Зайнято всі n каналів, mзаявок у черзі.

ДСП наведено на рис. 5.9. У кожної стрілки проставлено відповідні інтенсивності потоків подій. За стрілками зліва направо систему переводить завжди той самий потік заявок з інтенсивністю , по стрілках праворуч наліво систему переводить потік обслуговування, інтенсивність якого дорівнює , помноженому на кількість зайнятих каналів.

Багатоканальна експоненційна СМОвідрізняється від одноканальної наступним. Число каналів у ній більше одного. Заявка, що надходить, стає в чергу, якщо всі канали зайняті. Інакше заявка займає вільний канал. (5.56)

Напишемо вирази для граничних ймовірностей станів, використовуючи позначення: (див.5.45)

Ймовірність відмови. Заявка, що надійшла, отримує відмову, якщо зайняті всі nканалів і все mмісць у черзі:

(5.57)

Відносна пропускна здатність доповнює можливість відмови до одиниці:

Абсолютна пропускна здатність СМО:

(5.58)

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

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

Середню кількість заявок у черзі можна обчислити безпосередньо як математичне очікування дискретної випадкової величини:

(5.59)

Тут знову (вираз у дужках) зустрічається похідна суми геометричній прогресії(див. вище (5.50), (5.51)-(5.53)), використовуючи співвідношення для неї, отримуємо:

Середня кількість заявок у системі:

Середній час очікування заявки у черзі. Розглянемо ряд ситуацій, що відрізняються тим, у якому стані застане систему знову прийшла заявка і скільки часу їй доведеться чекати на обслуговування.

Якщо заявка застане не всі канали зайнятими, їй взагалі не доведеться чекати (відповідні члени математичному очікуваннірівні нулю). Якщо заявка прийде в момент, коли всі зайняті пканалів, а черги немає, їй доведеться чекати в середньому час, рівний (бо «потік звільнень» каналів має інтенсивність). Якщо заявка застане всі канали зайнятими і одну заявку перед собою в черзі, їй доведеться в середньому чекати протягом часу (по кожну заявку, що стоїть попереду) і т. д. Якщо заявка застане в черзі заявок, їй доведеться чекати в середньому протягом часу . Якщо заявка, що знову прийшла, застане в черзі вже mзаявок, вона взагалі не чекатиме (але й не буде обслужена).

Середній час очікуваннязнайдемо, помножуючи кожне із цих значень на відповідні ймовірності:

(5.60)

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

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

Системи з необмеженою довжиною черги.

Ми розглянули канальну СМО з очікуванням, коли в черзі одночасно можуть бути не більше mзаявок.

Також, як і раніше, при аналізі систем без обмежень необхідно розглянути отримані співвідношення при .

Імовірність станів отримаємо з формул (5.56) граничним переходом (при ). Зауважимо, що сума відповідної геометричної прогресії сходиться за і розходиться за > 1. Припустивши, що< 1 и устремив в формулах (5.56) величину mдо нескінченності, отримаємо вирази для граничних ймовірностей станів:

(5.61)

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

Середню кількість заявок в черзі отримаємо при (5.59):

а середній час очікування – з (5.60):

Середня кількість зайнятих каналів, як і раніше, визначається через абсолютну пропускну здатність:

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

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

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

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

В теорії СеМОфундаментальним є поняття стану мережі. Найважливіша характеристика мереж МО− ймовірності їх станів. Для визначення ймовірностей станів СеМОдосліджують випадковий процес, що протікає в мережі. Як моделі протікають у СеМОпроцесів також найчастіше використовують марківські та напівмарківські.

3.3. Система масового обслуговування як модель

1.5. Мережі масового обслуговування

Марківським процесом з безперервним часом описують функціонування експоненційних СеМО.

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

Теорія експоненційних СеМОнайбільш розроблена, і її широко застосовують як для дослідження мереж ПД так і для дослідження мультипроцесорних обчислювальних систем (ВС).Розроблено практичні формули розрахунку імовірнісно-тимчасових характеристик (ВВХ) таких мереж та систем.

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

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

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

Аналітичні методиРозрахунок характеристик ІС базуються, як правило, на аналізі експоненційних СеMO. З використанням цього математичного апарату вдається отримати аналітичні моделі на вирішення широкого колазадач дослідження систем. CеМО - це, перш за все, сукупність взаємопов'язаних систем масового обслуговування. Тому слід згадати основні особливості цих систем.

Мережа масового обслуговуванняявляє собою сукупність кінцевого числа Nобслуговуючих вузлів, в якій циркулюють заявки, що переходять відповідно до маршрутної матриці з одного вузла до іншого. Вузол завжди є розімкнутою СМО (причому СМО може бути будь-якого класу). При цьому окремі СМОвідображають функціонально самостійні частини реальної системи, зв'язки між СМО- структуру системи, а вимоги, що циркулюють по СеМО,- складові матеріальних потоків (повідомлення (пакети) у комунікаційній мережі, завдання у мультипроцесорних системах, контейнери вантажопотоків тощо).

Для наочного уявлення СеМОвикористовується граф, вершини якого (вузли) відповідають окремим СМОдуги відображають зв'язки між вузлами.

Перехід заявок між вузлами відбувається миттєво відповідно до перехідних ймовірностей , p ij- ймовірність того, що заявка після обслуговування у вузлі iперейде у вузол j. Звичайно, якщо вузли безпосередньо не пов'язані між собою, то p ij= 0. Якщо з i-го вузла перехід тільки в один якийсь вузол j, то p ij= 1.

СеМОкласифікують за декількома ознаками (рис. 4).

Мережа називається лінійної, якщо інтенсивності потоків заявок у вузлах пов'язані між собою лінійною залежністю

l j= a ij l i,

де a ij- коефіцієнт пропорційності, або щодо джерела

l j= a j l 0 ,.

Коефіцієнт a jназивають коефіцієнтом передачі, він характеризує частку заявок, що надходять у j-й вузол від джерела заявок, або - середня кількість проходжень заявкою через даний вузол під час перебування заявки у мережі.

Якщо інтенсивність потоків заявок у вузлах мережі пов'язана нелінійною залежністю (наприклад, ), то мережа називається нелінійною..

Мережа завжди лінійна, якщо заявки не губляться і не розмножуються.

Розімкненамережа – це така відрита мережа, до якої заявки надходять із довкілля та йдуть після обслуговування з мережі у зовнішнє середовище. Іншими словами, особливістю розімкнутої СеМО(РСеМО) є наявність одного або кількох незалежних зовнішніх джерел, які генерують заявки, що надходять до мережі, незалежно від того, скільки заявок вже знаходиться в мережі. У будь-який момент часу в РСеМОможе бути довільна кількість заявок (від 0 до ¥).

Рис. 4. Класифікація мереж масового обслуговування

У замкнутої СеМО (ЗСеМО)циркулює фіксовану кількість заявок, а зовнішнє незалежне джерело відсутнє. Виходячи з фізичних міркувань, ЗСеМПро вибирається зовнішня дуга, на якій відзначається псевдонульоваточка, щодо якої можуть вимірюватись тимчасові характеристики.

Комбінованамережа – це мережа, у якій постійно циркулює певна кількістьзаявок і є заявки, які від зовнішніх незалежних джерел.

У однорідниймережі циркулюють заявки одного класу І, навпаки, в неоднорідниймережі можуть бути заявки кількох класів. Заявки відносяться до різним класамякщо вони відрізняються хоча б одним з наступних атрибутів:

Законом розподілу тривалості обслуговування у вузлах;

Пріоритетами;

Маршрутами (шляхами руху заявок у мережі).

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

Якщо хоча в одному вузлі здійснюється пріоритетне обслуговування, то це – пріоритетнамережа. Пріоритет - це ознака, що визначає черговість обслуговування. Якщо обслуговування заявок у вузлах здійснюється у порядку надходження, то така мережа безпріоритетна.

Таким чином, експоненційною будемо називати СеМО, Що відповідає вимогам:

Вхідні потоки СеМОпуасонівські;

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

Перехід заявки з виходу i-й СМО на вхід j-й є незалежною випадковою подією, що має ймовірність p ij ; p i0- ймовірність відходу заявки з CeМО.

Якщо заявки приходять у мережу і йдуть з неї, то мережа називається розімкнутою. Якщо заявки не приходять до мережі та з неї не йдуть, мережа називається замкнутою. Число заявок у замкненій мережі постійне.