Системи масового обслуговування

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

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

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

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

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

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

Прикладом марківського процесу є, зокрема, система S - лічильників в таксі. Стан системи в момент t характеризуется числом кілометрів, пройдених автомобілем до даного моменту. Нехай в момент to лічильник показує So км. Імовірність того, що в момент t > to лічильник покаже те або інше число кілометрів Si, а, отже, відповідне число грн., залежить від So, але не залежить від того, в які моменти часу до моменту t змінювалися показання лічильника.

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

Потоки подій

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

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

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

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

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

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

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

Теорія розкладів

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

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

У процесі вирішення таких завдань, були вироблені спільні рекомендації, принципи і методики складання розкладів. Надалі подібні завдання стали досліджуватися в рамках спеціального розділу науки - теорії розкладів (далі ТР).

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

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

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

• На виробництві, коли потрібно впорядкувати окремі операції по виконавцях (цеху, верстати) і за часом;

• на транспорті при складанні розкладу руху поїздів, літаків, громадського міського транспорту;

• при плануванні занять в навчальних закладах;

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

• при виконанні складних тривалих проектів будівництва будівель, кораблів тощо;

• при плануванні проведення спортивних заходів;

• в комп'ютерних мережах при плануванні черговості передачі пакетів інформації і т.д.

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

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