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

1. Яке визначення марківського ланцюга «загибелі та розмноження».

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

Рекомендована література

1. Е.С. Вентцель. Исследование операций. «Сов. радио» М., 1972.

6Лекція 6.. Теорія масового обслуговування. Завдання теорії

План лекції

1. Термінологія та завдання теорії масового обслуговування.

2. Умовні позначення видів моделей масового обслуговування.

1. Термінологія та завдання теорії масового обслуговування.

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

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

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

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

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

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

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

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

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

• закон розподілу часу очікування;

• середня кількість заявок, що перебувають у черзі й ін.

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

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

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

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

Джерело заявок.Це пристрій або група пристроїв з яких заявки надходять у систему обслуговування. Розрізняють два типи джерела:

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

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

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

Якщо потоки заявок Пуассоновські - це істотно спрощує дослідження СМО.

Процес обслуговування. Нехай m_k – тривалість обслуговування k-й заявки. Припустимо, що m_k (k змінюється від 1 до n) – незалежні однаково розподілені випадкові величини з деякою функцією розподілу B_x. Якщо припустити, що B_x є експонентною функцією розподілу, процес дослідження СМО істотно спрощується.

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

Структура черги.Розрізняють два граничних випадки:

• перед обслуговуючим пристроєм неможливе утворення черги;

• перед обслуговуючим пристроєм можлива наявність нескінченної черги;

• системи з обмеженою чергою.

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

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

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

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

Існує множина дисциплін обслуговування. Наприклад, пряма (першим прийшов - першим обслужений), інверсна (останнім прийшов - першим обслужений), випадковий вибір, групове обслуговування, циклічне й т.п.

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

Найбільше поширення в пріоритетних системах одержали абсолютні й відносні пріоритети.

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

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