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

Постановка задачі.На вхід n-канальної СМО надходить найпростіший потік заявок із щільністю? Щільність найпростішого потоку обслуговування кожного каналу дорівнює μ. Якщо заявка, що надійшла на обслуговування, застає всі канали вільними, то вона приймається на обслуговування та обслуговується одночасно l каналами ( l < n). При цьому потік обслуговування однієї заявки матиме інтенсивність l.

Якщо заявка, що надійшла на обслуговування, застає в системі одну заявку, то при n ≥ 2lзаявка, що знову прибула, буде прийнята до обслуговування і обслуговуватиметься одночасно lканалами.

Якщо заявка, що надійшла на обслуговування, застає в системі iзаявок ( i= 0,1, ...), при цьому ( i+ 1)l≤ n, то заявка, що надійшла, буде обслуговуватися lканалами із загальною продуктивністю l. Якщо заявка, що знову надійшла, застає в системі jзаявок і при цьому виконуються спільно дві нерівності: ( j + 1)l > nі j < n, то заявку буде прийнято на обслуговування. У цьому випадку частина заявок може обслуговуватись lканалами, інша частина менша, ніж l, числом каналів, але в обслуговуванні будуть зайняті всі nканалів, які розподілені між заявками довільним чином. Якщо заявка, що знову надійшла, застане в системі nзаявок, то вона отримує відмову та не обслуговуватимуться. Заявка, що потрапила на обслуговування, обслуговується до кінця (заявки «терплячі»).

Граф станів такої системи показано на рис. 3.8.

Мал. 3.8. Граф станів СМО з відмовами та частковою

взаємодопомогою між каналами

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

Отже,

(i = 0, 1, ..., h).

Граф станів системи, починаючи від стану x hі закінчуючи станом x n, збігається з точністю до позначень із графом станів СМО з повною взаємодопомогою, зображеним на рис. 3.7. Таким чином,

.

Введемо позначення λ / lμ = ρ l ; λ / nμ = χ, тоді

З урахуванням нормованої умови отримуємо

Для скорочення подальшого запису введемо позначення

Знайдемо параметри системи.

Можливість обслуговування заявки

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

Середня кількість зайнятих каналів

.

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

.

Імовірність зайнятості всіх каналів системи

3.4.4. Системи масового обслуговування з відмовами та неоднорідними потоками

Постановка задачі.На вхід n-канальної СМО надходить неоднорідний найпростіший потік із сумарною інтенсивністю λ Σ , причому

λ Σ = ,

де λ i- Інтенсивність заявок в i-му джерелі.

Так як потік заявок розглядається як суперпозиція вимог від різних джерел, то об'єднаний потік з достатньою для практики точністю можна вважати пуассонівським для N = 5...20 та λ i ≈ λ i +1 (i1,N). Інтенсивність обслуговування одного приладу розподілена за експоненційним законом і дорівнює μ = 1/ t. Прилади для обслуговування заявки, що обслуговують, з'єднуються послідовно, що рівносильно збільшенню часу обслуговування в стільки разів, скільки приладів об'єднується для обслуговування:

tобс = kt, μ обс = 1 / kt = μ/ k,

де tобс - час обслуговування заявки; k- Число обслуговуючих приладів; μ обс – інтенсивність обслуговування заявки.

У рамках прийнятих у розділі 2 припущень стан СМО представимо у вигляді вектора, де k m– кількість заявок у системі, кожна з яких обслуговується mприладами; L = q max – q min +1 – кількість вхідних потоків.

Тоді кількість зайнятих та вільних приладів ( nзан ( ),nсв ( )) в стані визначається так:

Зі стану система може перейти в будь-який інший стан . Оскільки в системі діє Lвхідних потоків, то з кожного стану потенційно можливо LПрямих переходів. Однак через обмеженість ресурсів системи не всі ці переходи можна здійснити. Нехай СМО перебуває в стані і надходить заявка, що вимагає mприладів. Якщо m≤ nсв ( ), то заявка приймається на обслуговування і система переходить у стан з інтенсивністю λ m. Якщо заявка вимагає приладів більше, ніж є вільних, то вона отримає відмову в обслуговуванні, а СМО залишиться в стані . Якщо може знаходяться заявки, які вимагають mприладів, кожна з них обслуговується з інтенсивністю  m, а загальна інтенсивність обслуговування таких заявок (μ m) визначається як μ m = k m μ / m. При завершенні обслуговування однієї із заявок система перейде у стан, у якому відповідна координата має значення, на одиницю меншу, ніж у стані ,=, тобто. відбудеться зворотний перехід. На рис. 3.9 представлений приклад векторної моделі СМО для n = 3, L = 3, q min = 1, q max = 3, P(m) = 1/3, λ Σ = λ, інтенсивність обслуговування приладу – μ.

Мал. 3.9. Приклад графа векторної моделі СМО із відмовами в обслуговуванні

Отже, кожен стан характеризується числом заявок, що обслуговуються, певного типу. Наприклад, у стані
обслуговується одна заявка одним приладом та одна заявка двома приладами. У цьому стані всі прилади зайняті, отже, можливі лише зворотні переходи (прихід будь-якої заявки у цьому стані призводить до відмови в обслуговуванні). Якщо раніше закінчилося обслуговування заявки першого типу, система перейде в стан (0,1,0) з інтенсивністю μ, якщо раніше закінчилося обслуговування заявки другого типу, то система перейде в стан (0,1,0) з інтенсивністю μ/2.

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

Розглянемо знаходження Рвідк (імовірність відмови в обслуговуванні).

,

де S- Число станів графа векторної моделі СМО; Р() - ймовірність знаходження системи в стані .

Число станів відповідно визначається таким чином:

, (3.22)

;

Визначимо число станів векторної моделі СМО (3.22) для прикладу, представленого на рис. 3.9.

.

Отже, S = 1 + 5 + 1 = 7.

Для реалізації реальних вимог до обслуговуючих приладів потрібна досить велика кількість n (40, ..., 50), а запити на кількість обслуговуючих приладів заявки практично лежать у межах 8–16. При такому співвідношенні приладів та запитів запропонований шлях знаходження ймовірностей стає надзвичайно громіздким, т.к. векторна модель СМО має велику кількість станів S(50) = 1790, S(60) = 4676, S(70) = = 11075, а розмір матриці коефіцієнтів системи рівнянь алгебри пропорційний квадрату Sщо вимагає великого обсягу пам'яті ЕОМ і значних витрат машинного часу. Прагнення знизити обсяг обчислень стимулювало пошук рекурентних можливостей розрахунку Р() на основі мультиплікативних форм подання ймовірностей станів. У роботі подано підхід до розрахунку Р():

(3.23)

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

- Здійснити розрахунок для будь-яких значень n;

– прискорити розрахунок та знизити витрати машинного часу.

Аналогічним чином можуть бути визначені інші характеристики системи.

Система рівнянь

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

СМО представимо у вигляді вектора, де k m– кількість заявок у системі, кожна з яких обслуговується mприладами; L= q max – q min +1 – кількість вхідних потоків.

Якщо заявка приймається на обслуговування та система переходить у стан з інтенсивністю λ m.

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

Приклад векторної моделі СМО для n = 3, L = 3, q min = 1, q max = 3, P(m) = 1/3, λ Σ = λ, інтенсивність обслуговування приладу – μ.

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

СМО із нескінченною чергою для пуасонівських потоків. Граф, система рівнянь, розрахункові співвідношення.

Граф системи

Де n- Число каналів обслуговування, l- Число взаємодопоміжних каналів

СМО з нескінченною чергою та частковою взаємодопомогою для довільних потоків. Граф, система рівнянь, розрахункові співвідношення.

Граф системи

Система рівнянь

–λ Р 0 + nμ Р 1 =0,

.………………

–(λ + nμ) Р k+ λ Р k –1 + nμ Р k +1 =0 (k = 1,2, ... , n–1),

……………....

-(λ+ nμ) P n+ λ Р n –1 + nμ Р n+1=0,

……………….

-(λ+ nμ) P n+j+ λ Р n+j –1 + nμ Р n+j+1=0, j=(1,2,….,∞)

СМО з нескінченною чергою та повною взаємодопомогою для довільних потоків. Граф, система рівнянь, розрахункові співвідношення.

Граф системи

Система рівнянь

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

Граф системи

Система рівнянь

Розрахункові співвідношення:

,

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

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

Розмір характеризує ступінь завантаження СМО.
приклад. Нехай n-канальна СМО є обчислювальний центр (ВЦ) з трьома ( n=3) взаємозамінними ПЕОМ на вирішення завдань. Потік завдань, що надходять на ПЦ, має інтенсивність λ=1 завдання на годину. Середня тривалість обслуговування t про = 1,8 год.
Потрібно обчислити значення:
- ймовірність числа зайнятих каналів ВЦ;
- ймовірність відмови в обслуговуванні заявки;
- Відносної пропускної здатності ВЦ;
- Абсолютна пропускна здатність ВЦ;
- середньої кількості зайнятих ПЕОМ на ПЦ.
Визначте, скільки додатково треба придбати ПЕОМ, щоб збільшити пропускну здатність ВЦ у 2 рази.
Рішення.
Визначимо параметр μ потоку обслуговування:
.
Наведена інтенсивність потоку заявок
.
Граничні ймовірності станів знайдемо за формулами Ерланга:

Ймовірність відмови в обслуговуванні заявки
.
Відносна пропускна здатність ВЦ
.
Абсолютна пропускна здатність ВЦ:
.
Середня кількість зайнятих каналів - ПЕОМ

Таким чином, при режимі СМО, що встановився, в середньому буде зайнято 1,5 комп'ютера з трьох - решта півтора простоюватиме. Роботу розглянутого ВЦ навряд можна вважати задовільною, оскільки центр не обслуговує заявки загалом у 18% випадків (Р 3 = 0,180). Очевидно, що пропускну здатність ВЦ при даних і μ можна збільшити тільки за рахунок збільшення числа ПЕОМ.
Визначимо, скільки необхідно використовувати ПЕОМ, щоб скоротити кількість не обслужених заявок, що надходять на ВЦ, вдесятеро, тобто. щоб ймовірність відмови у вирішенні завдань не перевищувала 0,0180. Для цього використовуємо формулу ймовірності відмови:

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

Аналізуючи дані таблиці, слід зазначити, що розширення числа каналів ВЦ при даних значеннях λ і μ до 6 одиниць ПЕОМ дозволить забезпечити задоволення заявок на вирішення завдань на 99,22%, так як n= 6 ймовірність відмови в обслуговуванні ( Р відк) становить 0,0078.

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

• S 0 - всі канали вільні;
• S 1 – зайнятий один канал;
• S 2 – зайнято два канали;
• Sk– зайнято kканалів;
• Sn- Усі канали зайняті.

Мал. 7.24
На малюнку 6.24 зображено граф станів, у якому Si- Номер каналу; λ – інтенсивність надходження заявок; μ – відповідно інтенсивність обслуговування заявок. Заявки надходять у систему масового обслуговування з постійною інтенсивністю та поступово займають один за одним канали; коли всі канали будуть зайняті, то чергова заявка, яка прибула до СМО, отримає відмову та залишить систему.
Визначимо інтенсивності потоків подій, які переводять систему зі стану в стан під час руху як зліва направо, так і праворуч наліво за графом станів.
Наприклад, нехай система перебуває в стані S 1, тобто один канал зайнятий, оскільки на його вході стоїть заявка. Як тільки обслуговування заявки закінчиться, система перейде у стан S 0 .
Наприклад, якщо зайняті два канали, то потік обслуговування, що переводить систему зі стану S 2 у стан S 1 буде вдвічі інтенсивнішим: 2-μ; відповідно, якщо зайнято kканалів, інтенсивність дорівнює k-?

Процес обслуговування є процесом загибелі та розмноження. Рівняння Колмогорова для цього окремого випадку матимуть такий вигляд:

(7.25)
Рівняння (7.25) називаються рівняннями Ерланга .
Для того щоб знайти значення ймовірностей станів Р 0 , Р 1 , …, Рnнеобхідно визначити початкові умови:
– Р 0(0) = 1, тобто на вході системи стоїть заявка;
– Р 1 (0) = Р 2 (0) = … = Рn(0) = 0, т. е. у початковий час система вільна.
Проінтегрувавши систему диференціальних рівнянь (7.25), отримаємо значення ймовірностей станів Р 0 (t), Р 1 (t), … Рn(t).
Але набагато більше за нас цікавлять граничні ймовірності станів. При t → ∞ і за формулою, отриманою при розгляді процесу загибелі та розмноження, отримаємо розв'язання системи рівнянь (7.25):

(7.26)
У цих формулах відношення інтенсивності λ / μ до потоку заявок зручно позначити ρ .Цю величину називають наведеною інтенсивністю потоку заявок,тобто середня кількість заявок, які надходять до СМО за середній час обслуговування однієї заявки.

З урахуванням зроблених позначень система рівнянь (7.26) набуде наступного вигляду:

(7.27)
Ці формули для обчислення граничних ймовірностей називаються формулами Ерланга .
Знаючи всі ймовірності станів СМО, знайдемо характеристики ефективності СМО, тобто абсолютну пропускну здатність А, відносну пропускну здатність Qта ймовірність відмови Рвідк.
Заявка, яка надійшла до системи, отримає відмову, якщо вона застане всі канали зайнятими:

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

Q = 1 – Рвідк,
де Q– середня частка заявок, що надійшли, обслуговуються системою, або середня кількість заявок обслужених СМОв одиницю часу, віднесене до середньої кількості заявок, що надійшли за цей час:

A=λ·Q=λ·(1-P відк)
Крім того, однією з найважливіших характеристик СМО з відмовами є середня кількість зайнятих каналів. У n-канальної СМО з відмовами це число збігається із середнім числом заявок, що перебувають у СМО.
Середня кількість заявок k можна обчислити безпосередньо через ймовірність станів Р 0 , Р 1 , … , Р n:

,
тобто знаходимо математичне очікування дискретної випадкової величини, яка набуває значення від 0 до nз ймовірностями Р 0 , Р 1 , …, Рn.
Ще простіше виразити величину через абсолютну пропускну здатність СМО, тобто. А. Величина А – середня кількість заявок, які обслуговуються системою за одиницю часу. Один зайнятий канал обслуговує за одиницю часу μ заявок, тоді середня кількість зайнятих каналів