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

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

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

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

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

Система масового обслуговування (СМО)– це модель, що включає: 1) випадковий потік вимог, викликів або клієнтів, які потребують обслуговування; 2) алгоритм здійснення цього обслуговування; 3) канали (прилади) обслуговування.

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

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

Головна особливість завдань даного класу- явна залежність результатів аналіз та одержуваних рекомендацій від двох зовнішніх факторів: частоти надходження та складності замовлень (а значить і часу їх виконання).

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

В якості характеристик СМОрозглядаються:

• середній відсоток заявок, які отримують відмову та залишають систему не обслуженими;
• середній час «простою» окремих каналів та системи в цілому;
• середній час очікування у черзі;
• ймовірність того, що заявка, що надійшла, буде негайно обслужена;
• закон розподілу довжини черги та інші.

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

3.1. Моделі систем масового обслуговування.

Кожну СМО може характеризувати виразом: (a / b / c) : (d / e / f) , де

a - розподіл вхідного потоку заявок;

b - Розподіл вихідного потоку заявок;

c - Конфігурація обслуговуючого механізму;

d – дисципліна черги;

e – блок очікування;

f - Ємність джерела.

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

Вхідний потік заявок– кількість заявок, що надійшли в систему. Характеризується інтенсивністю вхідного потоку l.

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

Конфігурація системимає на увазі загальне числоканалів та вузлів обслуговування. СМО може містити:

1. один каналобслуговування (одна злітно-посадкова смуга, один продавець);
2. один канал обслуговування, що включає кілька послідовних вузлів(їдальня, поліклініка, конвеєр);
3. кілька однотипних каналівобслуговування, з'єднаних паралельно (АЗС, Довідкова служба, Залізничний вокзал).

Таким чином, можна виділити одно-і багатоканальні СМО.

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

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

Дисципліна черги– це правило обслуговування заявок із черги. До основних типів черги можна віднести такі:

1. ПЕРППО (першим прийшов – першим обслуговуєшся) – найпоширеніший тип;
2. ПОСППО (останнім прийшов – першим обслуговуєшся);
3. СОЗ (випадковий відбір заявок) – із банку даних.
4. ПР – обслуговування із пріоритетом.

Довжина чергиможе бути

• необмежена – тоді говорять про систему із чистим очікуванням;
• дорівнює нулю - тоді говорять про систему з відмовами;
• обмежена за довжиною (система змішаного типу).

Блок очікування- «Місткість» системи - загальна кількість заявок, що знаходяться в системі (у черзі та на обслуговуванні). Таким чином, е=з+d.

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

Кількість моделей СМО відповідає числу всіляких поєднань цих компонентів.

3.2 Вхідний потік вимог.

З кожним відрізком часу [ a, a+ T ], зв'яжемо випадкову величину Х, що дорівнює кількості вимог, що надійшли в систему за час Т.

Потік вимог називається стаціонарнимякщо закон розподілу не залежить від початкової точки проміжку а, а залежить тільки від довжини цього проміжку Т. Наприклад, потік заявок на телефонну станцію протягом доби ( Т= 24 години) не можна вважати стаціонарним, а ось з 13 до 14 годин ( Т= 60 хвилин) – можна.

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

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

Потік називається найпростішимякщо він стаціонарний, без післядії і ординарний.

Основна теорема.Якщо потік найпростіший, то с.в. Х [a. a + T] розподілено згідно із законом Пуассона, тобто. .

Наслідок 1. Найпростіший потік також називається пуассонівським.

Наслідок 2. M(X)= M(Х [ a , a + T ] )= lT, тобто. за час Т lTзаявок. Отже, за одну одиницю часу в систему надходить у середньому lзаявок. Ця величина і називається інтенсивністювхідного потоку.

Розглянемо ПРИКЛАД .

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

Рішення.

За умовою завдання, l=3, Т=2 дні, вхідний потік пуасонівський, n ³5. при рішенні зручно ввести протилежну подію, яка полягає в тому, що за час Тнадійде менше 5 заявок. Отже, за формулою Пуассона, отримаємо

^

3.3 Стан системи. Матриця та графік переходів.

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

Е 0 - Всі канали вільні;

Е 1 – зайнятий один канал;

Е n– зайняті всі канали;

Е n +1 – зайняті всі канали та одна заявка у черзі;

Е n + m– зайняті всі канали та всі місця в черзі.

Аналогічна система з відмовами може перебувати у станах E 0 – E n .

Для СМО з чистим очікуванням існує безліч станів. Таким чином, стан E n СМО на момент часу t – це кількість n заявок (вимог), що у системі на даний час, тобто. n= n(t) - випадкова величина, E n (t) – результати цієї випадкової величини, а P n (t) - Імовірність перебування системи в стані E n .

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

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

Малюнок 3.1 – граф переходів

Упоряд.	Е 0	Е 1	Е 2
Е 0	Р 0,0	Р 0,1	Р 0,2
Е 1	Р 1,0	Р 1,1	Р 1,2
Е 2	Р 2,0	Р 2,2	Р 2,2

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

Оскільки система обов'язково перейде з одного

стану в інше, то сума ймовірностей у кожному рядку завжди дорівнює одиниці.

3.4 Одноканальні СМО.

3.4.1 Одноканальні СМО з відмовами.

Розглянемо системи, що задовольняють вимогам:

(Р/Е/1):(–/1/¥) . Припустимо також, що час обслуговування вимоги не залежить від кількості вимог, що надійшли до системи. Тут і далі «Р» означає, що вхідний потік розподілено згідно із законом Пуассона, тобто. Найпростіший «Е» означає, що вихідний потік розподілений за експоненційним законом. Також тут і надалі основні формули даються без доказів.

Для такої системи можливі два стани: Е 0 – система вільна та Е 1 - Система зайнята. Складемо матрицю переходів. Візьмемо Dt- Безмежно малий проміжок часу. Нехай подія А полягає в тому, що в систему за час Dtнадійшла одна вимога. Подія полягає в тому, що за час Dtобслуговано одну вимогу. Подія А i , k- за час Dtсистема перейде зі стану E iу стан E k. Так як l- Інтенсивність вхідного потоку, то за час Dtу систему в середньому надходить l*Dtвимог. Тобто, ймовірність надходження однієї вимоги Р(А)=l* Dt, а ймовірність протилежної події Р(?)=1-l*Dt.Р(В)=F(Dt)= P(b< D t)=1- e - m D t = m Dt– можливість обслуговування заявки за час Dt. Тоді А 00 – заявка не надійде чи надійде, але буде обслужена. А 00 = + А * Ст Р 00 =1 - l*Dt. (ми врахували, що (Dt) 2 – нескінченно мала величина)

А 01 – заявка надійде, але не буде обслуговано. А 01 = А * . Р 01 = l*Dt.

А 10 – заявку буде обслуговано і новою не буде. А 10 = * Ā. Р 10 = m*Dt.

А 11 – заявка не буде обслужена або надійде нова, яка ще не обслуговується. А 11 = +У * А. Р 01 = 1- m*Dt.

Таким чином, отримаємо матрицю переходів:

Упоряд.	Е 0	Е 1
Е 0	1-l * Dt	l * Dt
Е 1	m * Dt	1-m * Dt

Імовірність простою та відмови системи.

Знайдемо тепер можливість знаходження системи в стані Е 0 у будь-який момент часу t(Тобто. р 0 ( t) ). Графік функції
зображено малюнку 3.2.

Асимптотою графіка є пряма
.

Очевидно, починаючи з певного моменту t,

1

Малюнок 3.2

Остаточно отримаємо, що
і
, де р 1 (t) - Імовірність того, що в момент часу t система зайнята (тобто перебуває в стані Е 1 ).

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

Стаціонарний режим роботи та коефіцієнт завантаження системи.

Якщо ймовірність знаходження системи може Е k, тобто. Р k (t), не залежить від часу t, то кажуть, що в СМО встановився стаціонарний режимроботи. При цьому величина
називається коефіцієнтом завантаження системи(або наведеною густиною потоку заявок). Тоді для ймовірностей р 0 (t) і р 1 (t) отримуємо такі формули:
,
. Можна також зробити висновок: що більше коефіцієнт завантаження системи, то більше ймовірність відмови системи (тобто. ймовірність те, що система зайнята).

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

Рішення.За умовою завдання, l=5, m y =5/6. Потрібно знайти ймовірність р 1 - Імовірність відмови системи.
.

3.4.2 Одноканальні СМО з необмеженою довжиною черги.

Розглянемо системи, що задовольняють вимогам: (Р/Е/1):(d/¥/¥). Система може бути в одному зі станів E 0 , …, E k, … Аналіз показує, що через деякий час така система починає працювати в стаціонарному режимі, якщо інтенсивність вихідного потоку перевищує інтенсивність вхідного потоку (тобто коефіцієнт завантаження системи менше одиниці). Враховуючи цю умову, отримаємо систему рівнянь

вирішуючи яку знайдемо, що . Таким чином, за умови, що y<1, получим
Звісно,
і
- Імовірність знаходження СМО в стані Е kу випадковий час.

Середні показники системи.

За рахунок нерівномірного надходження вимог до системи та коливання часу обслуговування, у системі утворюється черга. Для такої системи можна досліджувати:

• n – кількість вимог, які перебувають у СМО (у черзі та на обслуговуванні);
• v - Довжину черги;
• w - Час очікування початку обслуговування;
• w 0 – загальний час перебування у системі.

Нас цікавитимуть середні характеристики(Тобто беремо математичне очікуваннявід аналізованих випадкових величин, і пам'ятаємо, що y<1).

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

- Середня довжина черги.

– середній час очікування початку обслуговування, тобто. час очікування у черзі.

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

На автомийці є один блок для обслуговування і є місце для черги. Автомобілі прибувають за пуассонівським розподілом з інтенсивністю 5 авто/год. Середній час обслуговування однієї машини – 10 хвилин. Знайти усі середні характеристики СМО.

Рішення. l=5, m= 60хв/10хв = 6. Коефіцієнт завантаження y =5/6. Тоді середня кількість автомобілів у системі
, середня довжина черги
, середній час очікування початку обслуговування
години = 50 хв, і, нарешті, середній час перебування у системі
година.

3.4.3 Одноканальні СМО змішаного типу.

Припустимо, що довжина черги становить mвимог. Тоді для будь-кого s£ m, ймовірність перебування СМО може Е 1+ s, обчислюється за формулою
, тобто. одна заявка обслуговується та ще sзаявок – у черзі.

Імовірність простою системи дорівнює
,

а ймовірність відмови системи -
.

Дано три одноканальні системи, для кожної l=5, m =6. Але перша система – з відмовами, друга – з чистим очікуванням, а третя – з обмеженою довжиною черги, m=2. Знайти та порівняти ймовірності простою цих трьох систем.

Рішення.Для всіх систем коефіцієнт завантаження y=5/6. Для системи з відмовами
. Для системи з чистим очікуванням
. Для системи з обмеженою довжиною черги
. Висновок очевидний: чим більше заявок перебуває в черзі, тим менша ймовірність простою системи.

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

3.5.1 Багатоканальні СМО з відмовами.

Розглянемо системи (Р/Е/s):(-/s/¥) у припущенні, що час обслуговування не залежить від вхідного потоку і всі лінії працюють незалежно. Багатоканальні системи, крім коефіцієнта завантаження, можна також характеризувати коефіцієнтом
, де s- Число каналів обслуговування. Досліджуючи багатоканальні СМО, отримаємо такі формули (формули Ерланга) для ймовірності знаходження системи в стані Е kу випадковий момент часу:

, k = 0, 1, …

функція вартості.

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

Для пошуку оптимального варіанта треба знайти (і це можна зробити) мінімальне значення функції вартості: С(s) = с 1* l * p s +с 2*, графік якої представлений малюнку 3.3:

Малюнок 3.3

Пошук мінімального значення функції вартості полягає в тому, що ми знаходимо її значення спочатку для s =1, потім для s =2, потім для s =3, і т.д. до тих пір, поки на якомусь кроці значення функції С( s) не стане більше попереднього. Це означає, що функція досягла свого мінімуму і почала зростати. Відповіддю буде те число каналів обслуговування (значення s), для якого функція вартості мінімальна.

ПРИКЛАД .

Скільки ліній обслуговування має містити СМО з відмовами, якщо l= 2треб / год, m=1треб/час, штраф за кожну відмову становить 7 тис.руб., вартість простою однієї лінії – 2 тис.руб. в годину?

Рішення. y = 2/1=2. з 1 =7, з 2 =2.

Припустимо, що СМО має два канали обслуговування, тобто. s =2. Тоді
. Отже, С(2) = с 1 *l*p 2 +с 2 *(2- y*(1-р 2 )) = =7*2*0.4+2*(2-2*0.6)=7.2.

Припустимо, що s =3. Тоді
, С(3) = с 1 *l*p 3 +с 2 *
=5.79.

Припустимо, що є чотири канали, тобто. s =4. Тоді
,
, С(4) = с 1 *l*p 4 +с 2 *
=5.71.

Припустимо, що СМО має п'ять каналів обслуговування, тобто. s =5. Тоді
, С(5) = 6.7 – більше за попереднє значення. Отже, оптимальна кількість каналів обслуговування – чотири.

3.5.2 Багатоканальні СМО з чергою.

Розглянемо системи (Р/Е/s):(d/d+s/¥) у припущенні, що час обслуговування не залежить від вхідного потоку і всі лінії працюють незалежно. Говоритимемо, що в системі встановився стаціонарний режим роботи, Якщо середня кількість вимог, що надходять менше середнього числа вимог, обслуговуваних на всіх лініях системи, тобто. l

P(w>0) - Імовірність очікування початку обслуговування,
.

Остання характеристика дозволяє вирішувати задачу про визначення оптимального числа каналів обслуговування з таким розрахунком, щоб ймовірність очікування початку обслуговування була меншою від заданого числа. Для цього достатньо прорахувати ймовірність очікування послідовно при s =1, s =2, s=3 тощо.

ПРИКЛАД .

СМО – станція швидкої допомоги невеликого мікрорайону. l=3 виклику на годину, а m= 4 виклики на годину для однієї бригади. Скільки бригад необхідно мати на станції, щоб ймовірність очікування виїзду була меншою за 0.01?

Рішення.Коефіцієнт завантаження системи y =0.75. Припустимо, що є дві бригади. Знайдемо ймовірність очікування початку обслуговування при s =2.
,
.

Припустимо наявність трьох бригад, тобто. s=3. За формулами отримаємо, що р 0 =8/17, Р(w>0)=0.04>0.01 .

Припустимо, що у станції чотири бригади, тобто. s=4. Тоді отримаємо, що р 0 =416/881, Р(w>0)=0.0077<0.01 . Отже, на станції має бути чотири бригади.

3.6 Запитання для самоконтролю

1. Предмет та завдання теорії масового обслуговування.
2. СМО, їх моделі та позначення.
3. Вхідний потік вимог. Інтенсивність вхідного потоку.
4. Стан системи. Матриця та графік переходів.
5. Одноканальні СМО з відмовами.
6. Одноканальні СМО з чергою. Характеристики.
7. Стаціонарний режим роботи. Коефіцієнт завантаження системи.
8. Багатоканальні СМО з відмовами.
9. Оптимізація функції вартості.
10. Багатоканальні СМО із чергою. Характеристики.

3.7 Вправи для самостійної роботи

1. Закусочна на АЗС має один прилавок. Автомобілі прибувають відповідно до пуассонівського розподілу, в середньому 2 автомобілі за 5 хвилин. Для виконання замовлення в середньому достатньо 1.5 хвилин, хоча тривалість обслуговування розподілена за експонентним законом. Знайти: а) можливість простою прилавка; b) середні показники; c) ймовірність того, що кількість автомобілів, що прибули, буде не менше 10.
2. Рентгенівський апарат дозволяє обстежити в середньому 7 осіб на годину. Інтенсивність відвідувачів становить 5 осіб на годину. Припускаючи стаціонарний режим роботи, визначити середні показники.
3. Час обслуговування в СМО підпорядковується експоненційному закону,
   m = 7вимог на годину. Знайти ймовірність того, що: а) час обслуговування знаходиться в інтервалі від 3 до 30 хвилин; b) вимога буде обслужена протягом однієї години. Скористайтеся таблицею значень функції е х .
4. У річковому порту один причал, інтенсивність вхідного потоку – 5 суден щодня. Інтенсивність вантажно-розвантажувальних робіт – 6 суден на день. Маючи на увазі стаціонарний режим роботи, визначити усі середні характеристики системи.
5. l=3, m=2, штраф за кожну відмову дорівнює 5, а вартість простою однієї лінії дорівнює 2?
6. Яка оптимальна кількість каналів обслуговування повинна мати СМО, якщо l=3, m =1, штраф за кожну відмову дорівнює 7, а вартість простою однієї лінії дорівнює 3?
7. Яка оптимальна кількість каналів обслуговування повинна мати СМО, якщо l=4, m=2, штраф за кожну відмову дорівнює 5, а вартість простою однієї лінії дорівнює 1?
8. Визначити кількість злітно-посадкових смуг для літаків з урахуванням вимоги, що ймовірність очікування має бути меншою, ніж 0.05. При цьому інтенсивність вхідного потоку 27 літаків на добу, а інтенсивність їхнього обслуговування – 30 літаків на добу.
9. Скільки рівноцінних незалежних конвеєрних ліній повинен мати цех, щоб забезпечити ритм роботи, при якому ймовірність очікування обробки виробів повинна бути меншою за 0.03 (кожний виріб випускається однією лінією). Відомо, що інтенсивність надходження замовлень 30 виробів за годину, а інтенсивність обробки виробу однією лінією – 36 виробів за годину.
10. Безперервна випадкова величина Х розподілена за показовим законом із параметром l=5. Знайти функцію розподілу, характеристики та ймовірність влучення с.в. Х інтервал від 0.17 до 0.28.
11. Середня кількість викликів, що надходять на АТС за одну хвилину, дорівнює 3. Вважаючи потік пуассонівським, знайти ймовірність того, що за 2 хвилини надійде: а) два виклики; б) менше двох дзвінків; в) не менше двох дзвінків.
12. У ящику 17 деталей, із яких 4 – браковані. Складальник навмання витягує 5 деталей. Знайти ймовірність того, що а) усі витягнуті деталі – якісні; б) серед вилучених деталей 3 браковані.
13. Скільки каналів повинна мати СМО з відмовами, якщо l= 2треб / год, m=1треб/час, штраф за кожну відмову становить 8т.руб., вартість простою однієї лінії – 2т.руб. в годину?

Малюнок 0 - 2 Потоки подій (а) та найпростіший потік (б)

10.5.2.1. Стаціонарність

Потік називається стаціонарним , якщо ймовірність попадання тієї чи іншої кількості подій на елементарну ділянку часу довжиною τ (

Малюнок 0-2 , а)залежить тільки від довжини ділянки та не залежить від того, де саме на осі t розташована ця ділянка.

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

На практиці часто зустрічаються потоки подій, які (принаймні на обмеженій ділянці часу) можуть розглядатися як стаціонарні. Наприклад, потік викликів, що надходять на телефонну станцію, скажімо, на інтервалі від 12 до 13 години може вважатися стаціонарним. Той самий потік протягом цілої доби вже не буде стаціонарним (вночі інтенсивність потоку викликів набагато менша, ніж удень). Зауважимо, що так само і з більшістю фізичних процесів, які ми називаємо «стаціонарними» насправді вони стаціонарні тільки на обмеженій ділянці часу, а поширення цієї ділянки до нескінченності лише зручний прийом, що застосовується з метою спрощення.

10.5.2.2. Відсутність післядії

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

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

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

Малюнок 0 - 3 Розподіл Пуассона

Розглянемо осі t найпростіший потік подій з інтенсивністю? (Малюнок 0-2 б) . Нас цікавитиме випадковий інтервал часу Т між сусідніми подіями у цьому потоці; знайдемо його закон розподілу. Спочатку знайдемо функцію розподілу:

F(t) = P(T ( 0-2)

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

F(t) = 1 - Р 0

Ймовірність Р 0знайдемо за формулою (1), вважаючиm = 0:

звідки функція розподілу величини Т буде:

(0-3)

Щоб знайти щільність розподілу f (t) випадкової величини Т,необхідно продиференціювати вираз (0-1) заt:

0-4)

Закон розподілу із щільністю (0‑4) називається показовим (або експоненційним ). Розмір λ називається параметром показового закону.

Малюнок 0 - 4 Експонентний розподіл

Знайдемо числові характеристики випадкової величини Т- математичне очікування (середнє значення) M [t] = mt , та дисперсію D t . Маємо

( 0-5)

(інтегруючи частинами).

Дисперсія величини Т становить:

(0-6)

Виймаючи корінь квадратний із дисперсії, знайдемо середнє квадратичне відхиленнявипадкової величини Т.

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

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

Приклад СМО-1 .

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

Розрахуємо ймовірність Р ( m) появи m повідомлень в 1 с. Оскільки λ = 2, то з попередньої формули маємо

Підставляючи m = 0, 1, 2, 3, отримаємо такі величини (з точністю до чотирьохдесяткових знаків):

Малюнок 0 – 5 Приклад найпростішого потоку

Можливо надходження і більше 9 повідомлень в 1 с, але ймовірність цього дуже мала (близько 0,000046).

Отриманий розподіл може бути представлений у вигляді гістограми (показана на малюнку).

Приклад СМО-2.

Прилад (сервер), що обробляє три повідомлення 1с.

Нехай є обладнання, яке може обробляти три повідомлення на 1 с (µ=3). Надходить у середньому два повідомлення в 1с, причому відповідно c розподілом Пуассона. Яка частина цих повідомлень оброблятиметься відразу ж після надходження?

Імовірність того, що швидкість надходження буде меншою або дорівнює 3 с визначається виразом

Якщо система може обробляти максимум 3 повідомлення в 1 с, то ймовірність того, що вона не буде перевантажена, дорівнює

Іншими словами, 85,71% повідомлень обслуговуватимуться негайно, а 14,29% з деякою затримкою. Як бачимо, затримка в обробці одного повідомлення на час більше часу обробки 3 повідомлень буде зустрічатися рідко. Час обробки 1 повідомлення становить середньому 1/3 з. Отже, затримка більше 1с буде рідкісним явищем, що є цілком прийнятним для більшості систем.

Приклад СМО- 3

· Якщо касир банку зайнятий протягом 80% свого робочого дня, а решта часу він витрачає очікування клієнтів, його можна як пристрій з коефіцієнтом використання 0,8.

· Якщо канал зв'язку використовується для передачі 8-бітових символів зі швидкістю 2400 біт/с, тобто передається максимум 2400/8 символів в 1 с, і ми будуємо систему, в якій сумарний обсяг даних становить 12000 символів, що посилаються від різних пристроїв через канал зв'язку за хвилину найбільшого навантаження (включаючи синхронізацію, символи кінця повідомлень, керуючі тощо), то коефіцієнт використання обладнання каналу зв'язку протягом цієї хвилини дорівнює

· Якщо механізм доступу до файлу в годину найбільшого навантаження здійснює 9000 звернень до файлу, а час одного звернення дорівнює в середньому 300 мс, коефіцієнт використання обладнання механізму доступу в годину найбільшого навантаження становить

Поняття коефіцієнта використання устаткування використовуватиметься досить часто. Чим ближче коефіцієнт використання обладнання до 100%, тим більша затримка і довша черга.

Використовуючи попередню формулу, можна скласти таблиці значень функції Пуассона, якими можна визначити ймовірність надходженняm або більше повідомлень у цей час. Наприклад, якщо в середньому надходить 3,1 повідомлення на секунду [т. е. λ = 3,1], то ймовірність надходження 5 і більше повідомлень у цю секунду дорівнює 0,2018 (дляm = 5 у таблиці). Або в аналітичному вигляді

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

Часто початкові розрахунки можуть бути здійснені для значень завантаження обладнання

ρ ≤ 0,9

Ці значення можна одержати за допомогою таблиць Пуассона.

Нехай знову середня швидкість надходження повідомлень λ = 3,1 повідомлення/с. З таблиць випливає, що ймовірність надходження 6 або більше повідомлень в 1 дорівнює 0,0943. Отже, це число можна взяти як критерій навантаження щодо початкових розрахунків.

10.6.2. Завдання проектування

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

Чим більший коефіцієнт використання обладнання, тим довші черги, що виникають. Як показано нижче, можна спроектувати задовільно працюючу систему з коефіцієнтом використання ρ =0,7 але коефіцієнт, що перевищує ρ > 0,9, може призвести до погіршення якості обслуговування. Іншими словами, якщо канал пересилання масиву даних має завантаження 20%, навряд чи виникне черга. Якщо ж завантаження; складає 0,9, то, як правило, утворюватимуться черги, іноді дуже великі.

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

При проектуванні системи зазвичай робиться оцінка коефіцієнта використання різних видів устаткування; відповідні приклади будуть наведені у наступних розділах. Знання цих коефіцієнтів дозволяє розрахувати черги до відповідного обладнання.

· Яка довжина черги?

· Скільки часу на неї витрачатиметься?

На питання такого типу можна відповісти за допомогою теорії черг.

10.6.3. Системи масового обслуговування, їх класи та основні характеристики

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

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

СМО класифікуються на системи з:

· Відмовами (З втратами). У таких системах заявка, що надійшла в момент, коли всі канали зайняті, отримує «відмову», залишає СМО і надалі обслуговування не бере участі.

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

Обслуговування (дисципліна черги) у системі з очікуванням може бути

· Упорядкованим (заявки обслуговуються у порядку надходження),

· невпорядкованим(заявки обслуговуються у випадковому порядку) або

· Стиковим (Першою з черги вибирається остання заявка).

· Пріоритетним

o зі статичним пріоритетом

o з динамічним пріоритетом

(в останньому випадку пріорі ет може, наприклад, збільшуватися з тривалістю очікування заявки).

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

· з необмеженим очікуванням та

· з обмеженим очікуванням.

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

У системах з обмеженим очікуванням перебування заявки у черзі накладаються ті чи інші обмеження. Ці обмеження можуть стосуватися

· довжини черги (числа заявок, що одночасно перебувають у черзі система з обмеженою довжиною черги),

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

· загального часу перебування заявки до СМО

і т.д.

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

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

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

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

· середній відносний час простою системи в цілому та окремого каналу

і т.д.

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

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

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

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

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

а також інші характеристики очікування.

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

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

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

10.6.4. Формули розрахунку характеристик СМО для випадку обслуговування з одним приладом

Малюнок 0 - 6 Модель системи масового обслуговування з чергою

Такі черги можуть створюватися повідомленнями на вході процесора, що очікують початку обробки. Вони можуть бути під час роботи абонентських пунктів, підключених до многопунктовому каналу зв'язку. Аналогічно утворюються черги з автомобілів на заправних станціях. Однак за наявності більше одного входу на обслуговування ми маємо чергу з багатьма приладами та аналіз ускладнюється.

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

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

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

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

Формула Хінчина-Полачека використовується для обчислення довжин черг під час проектування інформаційних систем. Вона застосовується у разі експоненційного розподілу часу надходження за будь-якого розподілу часу обслуговування і дисципліни управління, аби вибір чергового повідомлення обслуговування не залежав від часу обслуговування.

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

Більшість значень часу обслуговування в інформаційних системах лежить десь між цими двома випадками. Часи обслуговування, рівні постійній величині, трапляються рідко. Навіть час доступу до жорсткого диска непостійно через різне положення масивів з даними на поверхні. Одним із прикладів, що ілюструють випадок постійного часу обслуговування може бути заняття лінії зв'язку для передачі повідомлень фіксованої довжини.

З іншого боку, розкид часу обслуговування негаразд великий, як у разі довільного чи експоненційного його розподілу, тобто.,σ s рідко досягає значеньt s. Цей випадок іноді вважають "найгіршим і тому користуються формулами, що належать до експоненційного розподілу часів обслуговування. Такий розрахунок може дати дещо завищені розміри черг і часів очікування в них, але ця помилка принаймні не є небезпечною.

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

Розглянемо такий приклад. Є шість типів повідомлень з часом обслуговування 15, 20, 25, 30, 35 та 300. Кількість повідомлень кожного типу однакова. Стандартне відхилення зазначених часів дещо вище за їхнє середнє. Значення останнього часу обслуговування набагато більше від інших. Це призведе до того, що повідомлення будуть перебувати в черзі значно довше, ніж коли б часи обслуговування були одного порядку. У такому разі при проектуванні доцільно вжити заходів для зменшення довжини черги. Наприклад, якщо ці цифри пов'язані з довжинами повідомлень, то, можливо, дуже довгі повідомлення варто розділити на частини.

10.6.6. Приклад розрахунку

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

Час відповіді системи та її стандартне відхилення розраховані з урахуванням часу введення даних з АРМу, друку та оформлення документа.

Дії касира були прохронометровані. Час обслуговування ts дорівнює загальному часу, що витрачається касиром на клієнта. Коефіцієнт використання касира ρ пропорційний часу його зайнятості. Якщо число клієнтів у години пік, то для касира дорівнює

Припустимо, що в години пік приходить 30 клієнтів на годину. У середньому касир витрачає 1,5 хвилини на клієнта. Тоді

ρ = (1,5 * 30) / 60 = 0,75

тобто касир використовується на 75%.

Число людей у ​​черзі можна швидко оцінити за допомогою графіків. З них випливає, що якщо ρ = 0,75, то середня кількість nq людейу черзі у каси лежить між 1,88 і 3,0 залежно від стандартного відхилення для t s .

Припустимо, що вимір стандартного відхилення для ts дало величину 0,5 хв. Тоді

σ s = 0,33 t s

З графіка першому малюнку знаходимо, що nq = 2,0, т. е. у середньому у каси чекатиму два клієнта.

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

t ∑ = t q + t s = 2,5 хв + 1,5 хв = 4хв

де t s обчислюється за допомогою формули Хінчина-Полачека.

10.6.7. Чинник посилення

Аналізуючи криві, зображені на малюнках, бачимо, що, коли устаткування, обслуговуюче чергу, використовується більш ніж 80%, криві починають зростати з загрозливою швидкістю. Цей факт дуже важливий під час проектування систем передачі. Якщо ми проектуємо систему, в якій обладнання використовується більш ніж на 80%, то незначне збільшення трафіку може призвести до різкого спаду продуктивності системи або змусити її працювати в аварійному режимі.

Збільшення вхідного трафіку на невелику кількість х%. призводить до збільшення розмірів черги приблизно на

Якщо коефіцієнт використання устаткування дорівнює 50%, це збільшення дорівнює 4ts % для експоненційного закону розподілу часу обслуговування. Але якщо коефіцієнт використання обладнання дорівнює 90%, то збільшення розміру черги дорівнює 100ts%, що у 25 разів більше. Незначне збільшення навантаження при 90% використання обладнання призводить до 25-кратного збільшення розмірів черги в порівнянні з випадком 50% використання обладнання.

Аналогічно час перебування у черзі збільшується на

При експоненційно розподіленому часі обслуговування ця величина має значення 4 t s 2 для коефіцієнта використання обладнання, що дорівнює 50%, та 100 t s 2 для коефіцієнта 90%, тобто знову в 25 разів гірше.

Крім того, для малих коефіцієнтів використання обладнання вплив змін σs на розмір черги незначний. Однак для великих коефіцієнтів зміна σ s сильно позначається розмірі черги. Тому при проектуванні систем з високим коефіцієнтом використання обладнання бажано отримати точні відомості про параметрσ s. Неточність припущення щодо експоненційності розподілу tsнайбільш відчутна при великих значеннях? Більше того, якщо раптом час обслуговування зросте, що можливо в каналах зв'язку під час передачі довгих повідомлень, то у разі великого утворюється значна черга.

Математичний (абстрактний) об'єкт, елементами якого є (рис. 2.1):

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

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

Мал. 2.1.

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

Обслуговування- Затримка заявки в обслуговуючому приладі на деякий час.

Тривалість обслуговування- час затримки (обслуговування) заявки у приладі.

Накопичувач(Буфер, вхідний буфер, вихідний буфер) - сукупність місць для очікування заявок перед обслуговуючим приладом. Кількість місць для очікування - ємність накопичувача.

Заявка, що надійшла до СМО, може перебувати у двох станах:

• 1) обслуговування(У приладі);
• 2) очікування(у накопичувачі), якщо всі прилади зайняті обслуговуванням інших заявок.

Заявки, що знаходяться в накопичувачі та очікують на обслуговування, утворюють чергазаявок. Кількість заявок у накопичувачі, що очікують на обслуговування, - довжина черги.

Дисципліна буферизації(дисципліна постановки в чергу) - правило занесення заявок, що надходять, у накопичувач (буфер).

Дисципліна обслуговування- правило вибору заявок із черги для обслуговування у приладі.

Пріоритет- Переважне право (захоплення ресурсів) на занесення в накопичувач або вибір з черги для обслуговування в приладі заявок одного класу по відношенню до заявок інших класів.

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

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

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

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

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

Зупинимося на деяких елементах СМО докладніше.

Вхідний (вхідний) потік заявок. Потоком подійназивається послідовність однорідних подій, що йдуть одна за одною і відбуваються в якісь, взагалі кажучи, випадковімоменти часу. Якщо подія полягає у появі заявок, маємо потік заявок.Для опису потоку заявок загальному випадкунеобхідно задати інтервали часу т = t k - t k-1між сусідніми моментами t k _ kі t kнадходження заявок із порядковими номерами до - 1 та довідповідно (до - 1, 2, ...; t 0 - 0 – початковий момент часу).

Основною характеристикою потоку заявок є його інтенсивність X- Середня кількість заявок, що надходять на вхід СМО за одиницю часу. Величина т = 1/Хвизначає середній інтервал між двома послідовними заявками.

Потік називається детермінованим,якщо інтервали часу т доміж сусідніми заявками набувають певних заздалегідь відомих значень. Якщо при цьому інтервали однакові (х до= т для всіх до = 1, 2, ...), то потік називається регулярним.Для повного опису регулярного потоку заявок достатньо встановити інтенсивність потоку Xабо значення інтервалу т = 1/Х.

Потік, у якому інтервали часу х доміж сусідніми заявками є випадкові величини, називається випадковим.Для повного опису випадкового потоку заявок у загальному випадку необхідно задати закони розподілу F fc (x fc) кожного з інтервалів часу х до, к = 1,2,....

Випадковий потік, у якому всі інтервали часу х ь х 2... між сусідніми послідовними заявками є незалежні випадкові величини, що описуються функціями розподілів FjCij), F 2 (x 2), ... відповідно, називається потоком з обмеженою післядією.

Випадковий потік називається рекурентним,якщо всі інтервали часу х ьт 2 ... між заявками розподілені за одним і тим самим законом F(t). Рекурентних потоків багато. Кожен закон розподілу породжує свій рекурентний потік. Рекурентні потоки інакше називають потоками Пальма.

Якщо інтенсивність Xі закон розподілу F(t) інтервалів між послідовними заявками не змінюються з часом, то потік заявок називається стаціонарний.В іншому випадку потік заявок є нестаціонарним.

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

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

Стаціонарний ординарний потік без післядії називається найпростішим.

Інтервали часу т між заявками в найпростішому потоці розподілені по експонентному (показовому) закону:з функцією розподілу F(t) = 1 - е~ м;щільністю розподілу/(f) = Хе~" л,де X > 0 – параметр розподілу – інтенсивність потоку заявок.

Найпростіший потік часто називають пуассонівським.Назва походить від того, що для цього потоку ймовірність P fc (At) появи рівно дозаявок за деякий інтервал часу At визначається законом Пуассона:

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

• стаціонарним,якщо інтенсивність Xне змінюється з часом;
• нестаціонарним,якщо інтенсивність потоку залежить від часу: X= >.(t).

У той самий час найпростіший потік, за визначенням, завжди стаціонарним.

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

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

Сума Nнезалежних стаціонарних ординарних потоків з інтенсивностями Х ь Х 2 ,..., X Nутворює найпростіший потік з інтенсивністю

X=Y,^iза умови, що потоки, що складаються, надають більше або

менш однаково малий впливом геть сумарний потік. Насправді сумарний потік близький до найпростішого при N > 5. Значить, при сумуванні незалежних найпростіших потоків сумарний потік буде найпростішимза будь-якого значення N.

• 2. Імовірнісне розрідження потоку. Вірогідне(але не детерміноване) розрідження найпростішого потокузаявок, при якому будь-яка заявка випадково з деякою ймовірністю рвиключається із потоку незалежно від того, виключені інші заявки чи ні, призводить до освіти найпростішого потокуз інтенсивністю X* = рХ,де X- Інтенсивність вихідного потоку. Потік виключених заявок з інтенсивністю X** = (1 - р) Х- теж найпростішийпотік.
• 3. Ефективність. Якщо обслуговуючі канали (прилади) розраховані на найпростіший потік заявок з інтенсивністю X,то обслуговування інших типів потоків (з тією самою інтенсивністю) буде забезпечено не меншою ефективністю.
• 4. Простота. Припущення про найпростіший потік заявок дозволяє багатьом математичних моделей отримати у явному вигляді залежності показників СМО від параметрів. Найбільша кількістьаналітичних результатів одержано для найпростішого потоку заявок.

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

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

Важливою характеристикою вхідного потоку є коефіцієнт варіації

де т інт – математичне очікування довжини інтервалу; про- Середнє квадратичне відхилення довжини інтервалу х інт (випадкової величини).

Для найпростішого потоку (а =-, т = -) маємо v = 1. Для більшості

реальних потоків 0

Канали (прилади) обслуговування. Основна характеристика каналу – тривалість обслуговування.

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

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

де ц - інтенсивність обслуговування,тут р = _--; т 0 бсл - матема-

тичне очікування часу обслуговування.

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

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

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

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

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

• буферизації;
• обслуговування.

Дисципліни буферизації та обслуговування можуть бути класифіковані за такими ознаками:

• наявність пріоритетів між заявками різних класів;
• спосіб витіснення заявок із черги (для дисциплін буферизації) та призначення заявок на обслуговування (для дисциплін обслуговування);
• правило витіснення чи вибору заявок обслуговування;
• можливість зміни пріоритетів.

Варіант класифікації дисциплін буферизації (постановки у чергу) відповідно до перелічених ознак представлений на рис. 2.2.

Залежно від наявностіабо відсутності пріоритетівміж заявками різних класів всі дисципліни буферизації можуть бути розбиті на дві групи: безпріоритетні та пріоритетні.

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

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

Мал. 2.2.

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

• випадкове витіснення;
• витіснення останньої заявки, тобто. що надійшла до системи пізніше за всіх;
• витіснення «довгої» заявки, тобто. що знаходиться в накопичувачі довше всіх заявок, що надійшли раніше.

На рис. 2.3 представлено класифікацію дисциплін обслуговування заявок відповідно до тих самих ознак, що й для дисциплін буферизації.

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

Залежно від наявностіабо відсутності пріоритетівміж заявками різних класів усі дисципліни обслуговування, як і дисципліни буферизації, можуть бути розбиті на дві групи: безпріоритетні та пріоритетні.

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

• одиночного режиму;
• групового режиму;
• комбінованого режиму.

Мал. 2.3.

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

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

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

Дисципліни обслуговування можуть використовувати наступні правилавибору заявок обслуговування.

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

• обслуговування у порядку надходження FIFO (перший в -First out,перший увійшов – перший вийшов);
• обслуговування у зворотному порядку- заявка вибирається із черги в режимі LIFO (last in - first out,останній увійшов – перший вийшов);
• обслуговування у випадковому порядку- заявка вибирається із черги в режимі RAND (random- випадковим чином);
• обслуговування у циклічному порядку- заявки вибираються в процесі циклічного опитування накопичувачів у послідовності 1, 2, НЗ Н- кількість накопичувачів), після чого вказана послідовність повторюється;

Пріоритетні(Заявки мають привілеї на дострокове обслуговування – захоплення ресурсів):

• з відносними пріоритетами- якщо у процесі поточного обслуговуваннязаявки до системи надходять заявки з вищими пріоритетами, то обслуговування поточної навіть безпріоритетної заявки не переривається, а заявки, що надійшли, направляються в чергу; відносні пріоритети відіграють роль лише в момент закінчення поточного обслуговування заявки при виборі з черги нової заявки на обслуговування.
• з абсолютними пріоритетами- при надходженні заявки з високим пріоритетом обслуговування заявки з низьким пріоритетом переривається і на обслуговування надсилається заявка, що надійшла; перервана заявка може бути повернена в чергу або видалена із системи; якщо заявку повернуто в чергу, то її подальше обслуговування може бути виконане з перерваного місця або заново;
• зі змішаними пріоритетами- суворі обмеження на час очікування у черзі обслуговування окремих заявок вимагають присвоєння їм абсолютних пріоритетів; внаслідок цього час очікування заявок із низькими пріоритетами може виявитися неприпустимо великим, хоча окремі заявки мають запас за часом очікування; для виконання обмежень за всіма видами заявок можна поряд з абсолютними пріоритетами деяким заявкам присвоїти відносні пріоритети, а решту обслуговувати у безпріоритетному режимі;
• з пріоритетами, що чергуються- аналогом відносних пріоритетів, пріоритет враховується лише у моменти завершення поточного обслуговування групи заявок однієї черги та призначення нової групи на обслуговування;
• обслуговування за розкладом- заявки різних класів (що знаходяться в різних накопичувачах) вибираються на обслуговування згідно з деяким розкладом, що задає послідовність опитування черг заявок, наприклад, у разі трьох класів заявок (накопичувачів) розклад може мати вигляд (2, 1, 3, 3, 1, 2) або (1, 2, 3, 3, 2, 1).

У комп'ютерних системах ІМ, як правило, за умовчанням реалізується дисципліна FIFO.Однак вони мають інструментальні засоби, які надають користувачеві можливість організувати необхідні йому дисципліни обслуговування, у тому числі і за розкладом.

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

• тривалістю обслуговування;
• пріоритетами.

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

Для математичного опису дисциплін обслуговування із змішаними пріоритетами використовується матриця пріоритетів, представляє собою квадратну матрицю Q = (q, ;), i,j - 1,..., Я, Я - число класів заявок, що у систему.

Елемент q (jматриці задає пріоритет заявок класу iстосовно заявок класу; і може приймати такі значення:

• 0 – немає пріоритету;
• 1 – пріоритет відносний;
• 2 – пріоритет абсолютний.

Елементи матриці пріоритетів повинні відповідати наступним вимогам:

• q n= 0, оскільки між заявками одного й того класу неможливо знайти встановлені пріоритети;
• якщо q (j = 1 або 2, то q^ = 0, тому що якщо заявки класу iмають пріоритет до заявок класу j,то останні не можуть мати пріоритет до заявок класу i (i,j = 1, …, Я).

Залежно від можливості зміни пріоритетіву процесі функціонування системи пріоритетні дисципліни буферизації та обслуговування діляться на два класи:

• 1) зі статичними пріоритетами,які не змінюються з часом;
• 2) з динамічними пріоритетами,які можуть змінюватися в процесі функціонування системи залежно від різних факторів, наприклад, при досягненні деякого критичного значення довжини черги заявок будь-якого класу, що не має пріоритету або має низький пріоритет, йому може бути надано більш високий пріоритет.

У комп'ютерних системах ІМ обов'язково є єдиний елемент (об'єкт), через який і тільки через нього вводяться заявки в модель. За замовчуванням всі заявки, що вводяться, безпріоритетні. Але є можливості присвоєння пріоритетів у послідовності 1, 2, ..., зокрема і під час виконання моделі, тобто. у динаміці.

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

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

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

У СМО крім вихідного потоку обслужених заявок може бути і потік необслужених заявок.Якщо таку СМО надходить рекурентний потік, а обслуговування - експоненційне, те й потік необслужених заявок - рекурентний.

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

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

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

Мал. 2.4.

СеМО називають також багатофазними СМО.

Приклад побудови ІМ СеМО ми розглянемо пізніше.

Основними елементами СеМО є вузли (У) та джерела (генератори) заявок (Г).

Вузолмережі – це система масового обслуговування.

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

Для спрощеного зображення СЕМО використовується граф.

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

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

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

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

Одноканальна смо з відмовами

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

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

Система за будь-якого t> 0 може бути у двох станах: S 0 – канал вільний; S 1 – канал зайнятий. Перехід із S 0 в S 1 пов'язаний з появою заявки та негайним початком її обслуговування. Перехід із S 1 в S 0 здійснюється, коли чергове обслуговування завершиться (рис.4).

Рис.4. Граф станів одноканальної СМО із відмовами

Вихідні характеристики (характеристики ефективності) цієї та інших СМО будуть надаватися без висновків та доказів.

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

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

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

Відносна пропускна спроможність(Середня частка заявок, що обслуговуються системою):

Ймовірність відмови(ймовірність того, що заявка залишить СМО необслуженою):

Очевидні такі співвідношення: і.

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

Тобто. в середньому приблизно 46% деталей обробляються на цьому верстаті.

.

Тобто. в середньому приблизно 54% ​​деталей прямують на обробку на інші верстати.

N - канальна смо з відмовами (завдання Ерланга)

Це з перших завдань теорії масового обслуговування. Вона виникла з практичних потреб телефонії та була вирішена на початку 20 століття датським математиком Ерлангом.

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

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

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

S 0 – у СМО немає жодної заявки;

S 1 - у СМО знаходиться одна заявка (один канал зайнятий, інші вільні);

S 2 - у СМО знаходиться дві заявки (два канали зайняті, інші вільні);

S n – у СМО знаходиться n- Заявок (усі n– каналів зайняті).

Граф станів СМО подано на рис. 5

Рис.5 Граф станів для n - канальної СМО з відмовами

Чому граф станів розмічено саме так? Зі стану S 0 у стан S 1 систему переводить потік заявок з інтенсивністю (як тільки надходить заявка, система переходить з S 0 в S 1). Якщо система перебувала в стані S 1 і прийшла ще одна заявка, то вона переходить у стан S 2 і т.д.

Чому такі інтенсивності у нижніх стрілок (дуг графа)? Нехай система перебуває в стані S 1 (працює один канал). Він здійснює обслуговування в одиницю часу. Тому дуга переходу зі стану S 1 у стан S 0 навантажена інтенсивністю. Нехай тепер система перебуває в стані S 2 (працюють два канали). Щоб їй перейти до S 1 потрібно, щоб закінчив обслуговування перший канал, або другий. Сумарна інтенсивність їх потоків дорівнює і т.д.

Вихідні характеристики (характеристики ефективності) цієї СМО визначаються в такий спосіб.

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

де n– кількість каналів СМО;

-імовірність знаходження СМО в початковому стані, коли всі канали вільні (фінальна ймовірність знаходження СМО в стані S 0);

Рис.6. Граф станів для схеми «загибелі та розмноження»

Для того щоб написати формулу для визначення , розглянемо рис.6

Граф, представлений цьому малюнку, називають ще графом станів для схеми «загибелі і розмноження». Напишемо спочатку на загальну формулу (без підтвердження):

До речі, решта фінальних ймовірностей станів СМО запишуться наступним чином.

S 1 коли один канал зайнятий:

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

Імовірність того, що СМО перебуває в стані S n, тобто. коли всі канали зайняті.

Тепер для n – канальної СМО із відмовами

Відносна пропускна спроможність:

Нагадаємо, що це середня частка заявок, які обслуговує система. При цьому

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

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

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