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

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

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

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

Мал. 6.2.

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

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

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

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

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

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

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

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

• 1) системи з обмеженим потоком вимог;
• 2) системи з необмеженим потоком вимог.

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

• 1) системи із упорядкованим обслуговуванням;
• 2) системи із невпорядкованим обслуговуванням.

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

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

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

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

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

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

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

Але всі ці системи об'єднані в один клас СМО, оскільки підхід до вивчення єдиний. Він полягає в тому, що, по-перше, за допомогою генератора випадкових чисел розігруються випадкові числа, які імітують ВИПАДКОВІ моменти появи заявок та час їхнього обслуговування в каналах. Але разом ці випадкові числа, звісно, ​​підпорядковані статистичнимзакономірностей.

Наприклад, нехай сказано: "заявки в середньому приходять у кількості 5 штук на годину". Це означає, що часи між приходом двох сусідніх заявок є випадковими, наприклад: 0.1; 0.3; 0.1; 0.4; 0.2, як показано на рис. 30.1, але в сумі вони дають у середньому 1 (зверніть увагу, що в прикладі це не точно 1, а 1.1 - зате в іншу годину ця сума, наприклад, може бути рівною 0.9); і тільки за досить великий чассереднє цих чисел стане близьким до однієї години.

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

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

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

Перелічимо деякі основні поняття СМО.

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

Черги характеризуються правилами стояння в черзі (дисципліною обслуговування), кількістю місць у черзі (скільки клієнтів максимум може перебувати у черзі), структурою черги (зв'язок між місцями у черзі). Бувають обмежені та необмежені черги. Перелічимо найважливіші дисципліни обслуговування. FIFO (First In, First Out – першим прийшов, першим пішов): якщо заявка першою прийшла в чергу, то вона першою піде на обслуговування. LIFO (Last In, First Out – останнім прийшов, першим пішов): якщо заявка останньої прийшла в чергу, то вона першою піде на обслуговування (приклад – патрони в ріжку автомата). SF (Short Forward - короткі вперед): в першу чергу обслуговуються заявки з черги, які мають менший час обслуговування.

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

Нехай є два магазини. У магазині № 1 обслуговування здійснюється у порядку черги, тобто тут реалізовано дисципліну обслуговування FIFO (див. рис. 30.3).

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

У магазині № 2 реалізовано дисципліну SF (див. рис. 30.4), що означає, що штучний товар можна купити позачергово, оскільки час обслуговування tобслуг. такої покупки невелика.

Як видно з обох малюнків, останній (п'ятий) покупець має намір придбати штучний товар, тому час його обслуговування невеликий – 0.5 хвилин. Якщо цей покупець прийде до магазину №1, він буде змушений вистояти в черзі цілих 8 хвилин, тоді як у магазині №2 його обслужать відразу ж, поза чергою. Таким чином, середній час обслуговування кожного з покупців у магазині з дисципліною обслуговування FIFO становитиме 4 хвилини, а у магазині з дисципліною обслуговування КВ – лише 2.8 хвилини. А загальна користь, економія часу становитиме: (1 – 2.8/4) · 100% = 30 відсотків! Отже, 30% заощадженого для суспільства часу – і це лише за рахунок правильного вибору дисципліни обслуговування.

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

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

Судити про результати роботи СМО можна за показниками. Найбільш популярні з них:

можливість обслуговування клієнта системою;

пропускна спроможність системи;

можливість відмови клієнту в обслуговуванні;

ймовірність зайнятості кожного з каналу та всіх разом;

середній час зайнятості кожного каналу;

можливість зайнятості всіх каналів;

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

ймовірність простою кожного каналу;

можливість простою всієї системи;

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

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

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

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

Судити про якість отриманої системи необхідно за сукупністю значень показників. При аналізі результатів моделювання (показників) важливо звертати увагу на інтереси клієнта та інтереси власника системи, тобто мінімізувати або максимізувати треба той чи інший показник, а також на ступінь їх виконання. Зауважимо, що найчастіше інтереси клієнта та власника між собою не збігаються або збігаються не завжди. Показники будемо позначати далі H = { h 1 , h 2 , …} .

Параметрами СМО можуть бути: інтенсивність потоку заявок, інтенсивність потоку обслуговування, середній час, протягом якого заявка готова чекати на обслуговування в черзі, кількість каналів обслуговування, дисципліна обслуговування тощо. Параметри – це те, що впливає на показники системи. Параметри будемо позначати далі як R = { r 1 , r 2 , …} .

приклад. Автозаправна станція (АЗС).

1. Постановка задачі. На рис. 30.5 наведено план АЗС. Розглянемо метод моделювання СМО на її прикладі та план її дослідження. Водії, проїжджаючи дорогою повз АЗС дорогою, можуть захотіти заправити свій автомобіль. Бажають обслужитися (заправити машину бензином) не всі автомобілісти поспіль; припустимо, що з усього потоку машин на заправку в середньому заїжджає 5 машин на годину.

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

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

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

Для створення часу приходу заявок використовуємо формулу обчислення інтервалу між моментами приходу двох випадкових подій (див. лекцію 28):

У цій формулі величина потоку λ має бути задана (до цього вона має бути визначена експериментально на об'єкті як статистичне середнє), r- випадкове рівномірно розподілене число від 0 до 1 із ГСЧ або таблиці, В якій випадкові числа потрібно брати поспіль (не вибираючи спеціально).

Завдання. Згенеруйте потік із 10 випадкових подій з інтенсивністю появи подій 5 шт/год.

Розв'язання задачі. Візьмемо випадкові числа, рівномірно розподілені в інтервалі від 0 до 1 (див. таблицю), та обчислимо їх натуральні логарифми (див. табл. 30.2).

Формула пуассонівського потоку визначає відстань між двома випадковими подіями наступним чином: t= -Ln (r рр) / λ . Тоді, враховуючи, що λ = 5 маємо відстані між двома випадковими сусідніми подіями: 0.68, 0.21, 0.31, 0.12 години. Тобто події наступають: перша - на момент часу t= 0 , друге - у момент часу t= 0.68 , третє - у момент часу t= 0.89 , четверте - на момент часу t= 1.20 , п'яте - на момент часу t= 1.32 тощо. Події - надходження заявок відобразимо на першій лінійці (див. рис. 30.7).

Береться перша заявка і, оскільки в цей момент вільні канали, встановлюється на обслуговування в перший канал. Заявка 1 переноситься на лінійку "1 канал".

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

де роль інтенсивності грає величина потоку обслуговування μ 1 або μ 2 залежно від того, який канал обслуговує заявку. Знаходимо на діаграмі момент закінчення обслуговування, відкладаючи згенерований час обслуговування від початку обслуговування, і опускаємо заявку на лінійку «Обслужені».

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

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

Якщо всі місця в черзі в момент, коли прийде чергова заявка, будуть зайняті, заявку слід відправити на лінійку «Відмовлені». На рис. 30.7 – це заявка з номером 6.

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

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

3.1.1 Загальні відомості про системи масового обслуговування

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

На рис 3.1 зображено схему СМО.

Основними елементами (ознаками) систем масового обслуговування є:

Обслуговуючий вузол (блок),

Потік заявок

Чергав очікуванні обслуговування (дисципліна черги).

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

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

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

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

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

1. Поява заявки (вимоги) обслуговування. Причиною випадковості цієї події часто є масовий характер потреби в обслуговуванні.

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. Неточність припущення щодо експоненційності розподілу tsнайбільш відчутна при великих значеннях? Більше того, якщо раптом час обслуговування зросте, що можливо в каналах зв'язку під час передачі довгих повідомлень, то у разі великого утворюється значна черга.

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

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

Прикладами систем масового обслуговування можуть бути:

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

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

Мал. 1

1. Генератор заявок - Об'єкт, що породжує заявки: вулиця, цех із встановленими агрегатами. На вхід надходить потік заявок(Потік покупців у магазин, потік агрегатів, що зламалися (машин, верстатів) на ремонт, потік відвідувачів у гардероб, потік машин на АЗС і т. д.).
2. Диспетчер – людина або пристрій, який знає, що робити із заявкою. Вузол, що регулює та направляє заявки до каналів обслуговування. Диспетчер:

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

1. Черга - Накопичувач заявок. Черга може бути відсутня.
2. Вузол обслуговування складається із кінцевого числа каналів обслуговування. Кожен канал має 3 стани: вільний, зайнятий, не працює. Якщо всі канали зайняті, можна придумати стратегію, кому передавати заявку.
3. Відмова від обслуговування настає, якщо всі канали зайняті (деякі навіть можуть працювати).

Крім цих основних елементів СМО в деяких джерелах виділяються також такі складові:

термінатор – знищувач трансактів;

склад – накопичувач ресурсів та готової продукції;

рахунок бухгалтерського обліку – до виконання операцій типу «проводка»;

менеджер – розпорядник ресурсів;

Класифікація СМО

Перший поділ (за наявності черг):

• СМО із відмовими;
• СМО із чергою.

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

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

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

Отже, наприклад, розглядаються такі СМО:

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

Типи обмеження черги можуть бути комбінованими.

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

Природно, потік заявок, породжений системою, залежатиме від системи та її стану.

Крім цього СМО діляться на відкритіСМО та замкнутіСМО.

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

Приклад замкнутої системи: видача касиром зарплати для підприємства.

За кількістю каналів СМО поділяються на:

• одноканальні;
• багатоканальні.

Характеристики системи масового обслуговування

Основними характеристиками системи масового обслуговування будь-якого виду є:

• вхідний потік вимог чи заявок на обслуговування;
• дисципліна черги;
• Механізм обслуговування.

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

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

А і– час надходження між вимогами – незалежні однаково розподілені випадкові величини;

E(A)- Середнє (МО) час надходження;

λ=1/E(A)- Інтенсивність надходження вимог;

Характеристики вхідного потоку:

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

Дисципліна черги

Черга - Сукупність вимог, що очікують обслуговування.

Черга має ім'я.

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

• першим прийшов – перший обслуговуєшся;

вперше в першу чергу (FIFO)

найпоширеніший тип черги.

Яка структура даних підійде для опису такої черги? Масив поганий (обмежений). Можна використовувати структуру типу СПИСОК.

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

Ви, як програмісти, повинні вміти робити списки двосторонні, односторонні.

Дії зі списком:

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

Структура відома як СТЕК. Може бути описаний структурою масив чи список;

• випадковий відбір заявок;
• відбір заявок за критерієм пріоритетності

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

Характеристики черги

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

Механізм обслуговування

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

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

Для аналітичного опису характеристик процедури обслуговування оперують поняттям «імовірнісне розподілення часу обслуговування вимог».

S i- Час обслуговування i-го вимоги;

E(S)- Середній час обслуговування;

μ=1/E(S)- Швидкість обслуговування вимог.

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

Коефіцієнт використання СМО

N·μ - швидкість обслуговування в системі, коли зайняті всі пристрої обслуговування.

ρ=λ/( Nμ) – називається коефіцієнтом використання СМО показує, наскільки задіяні ресурси системи.

Структура обслуговуючої системи

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

приклад. Каси у магазині.

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

приклад. Медична комісія.

Комбіноване обслуговування - Обслуговування вкладів в ощадкасі: спочатку контролер, потім касир. Як правило, 2 контролери на одного касира.

Отже, функціональні можливості будь-якої системи масового обслуговування визначаються такими основними факторами :

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

Основні критерії ефективності функціонування СМО

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

• ймовірність негайного обслуговування заявки, що надійшла (Р обсл = До обс / До пост);
• ймовірність відмови в обслуговуванні заявки, що надійшла (P отк = До отк / До пост);

Вочевидь, що Р обсл + P отк =1.

Потоки, затримки, сервіс. Формула Поллачека-Хінчина

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

D i– затримка у черзі вимоги i;

W i = D i + S i– час перебування у системі вимоги i.

(з ймовірністю 1) – середня затримка вимоги в черзі, що встановилася;

(з ймовірністю 1) - середній час знаходження вимоги в СМО (waiting).

Q(t) -кількість вимог у черзі на момент часу t;

L(t)– кількість вимог у системі в момент часу t(Q(t)плюс кількість вимог, що знаходяться на обслуговуванні на момент часу t.

Тоді показники (якщо існують)

(з ймовірністю 1) – середнє за часом кількість вимог у черзі;

(з ймовірністю 1) – середня кількість часу, що встановилася серед часу, в системі.

Зауважимо, що ρ<1 – обязательное условие существования d, w, Qі Lу системі масового обслуговування.

Якщо згадати, що ρ= λ/( Nμ), то видно, що якщо інтенсивність надходження заявок більша, ніж Nμ, то ρ>1 і природно, що система не зможе впоратися з таким потоком заявок, а отже, не можна говорити про величини d, w, Qі L.

До найбільш загальних та необхідних результатів для систем масового обслуговування відносяться рівняння збереження

Слід звернути увагу на те, що згадані вище критерії оцінки роботи системи можуть бути аналітично обчислені для систем масового обслуговування M/M/N(N>1), т. е. систем з Марківськими потоками заявок та обслуговування. Для М/G/ l за будь-якого розподілу Gта для деяких інших систем. Взагалі, розподіл часу між надходженнями, розподіл часу обслуговування або обох цих величин має бути експоненціальним (або різновидом експоненційного розподілу Ерланга k-го порядку), щоб аналітичне рішення стало можливим.

Крім цього можна також говорити про такі характеристики, як:

• абсолютна пропускна здатність системи - А = Р обсл *λ;
• відносна пропускна здатність системи –

Ще один цікавий (і наочний) приклад аналітичного рішення – обчислення середньої затримки, що встановилася, в черзі для системи масового обслуговування M/G/ 1 за формулою:

.

У Росії ця формула відома як формула Поллачека – Хінчина, там ця формула пов'язується з ім'ям Росса (Ross).

Таким чином, якщо E(S)має більше значення, тоді перевантаження (в даному випадку вимірюється як d) буде більшою; чого й слід було чекати. За формулою можна знайти і менш очевидний факт: перевантаження також збільшується, коли мінливість розподілу часу обслуговування зростає, навіть якщо середній час обслуговування залишається незмінним. Інтуїтивно це можна пояснити так: дисперсія випадкової величини часу обслуговування може прийняти велике значення (оскільки вона має бути позитивною), тобто єдиний пристрій обслуговування буде зайнятий тривалий час, що призведе до збільшення черги.

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

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