Реферат на тему:
Дослідження операцій. Основні поняття та види систем масового
обслуговування
План :
Основні поняття та класифікація систем масового обслуговування.
Області застосування систем масового обслуговування.
Особливості математичних моделей та операційні характеристики СМО.
Структура математичної моделі та класифікація СМО.
Характеристики якості та проблеми аналізу СМО.
КЛЮЧОВІ ПОНЯТТЯ ТА ТЕРМІНИ
система масового обслуговування
експоненційний закон розподілу
середній час очікування на обслуговування
середня довжина черги
канал
процес відновлення
модель
самообслу гову вання
вірогідність втрати
вимоги
завантаження обслуговуючих апаратів
вхідний потік вимог
послідовність рекурентних подій
модель чистої загибелі
черга на обслуговування
пуасонівський потік
післядія
обслуговуюча система
ординарність
вартісна модель СМО
дисципліна черги
стаціонарність
механізм обслуговування
Основні поняття та класифікація систем масового обслуговування.
Процеси утворення черг або затримок в обслуговуванні, які широко
розповсюджені, ефективно аналізуються методами дослідження операцій.
Практичне застосування моделей масового обслуговування економічно
вигідне при розв’язуванні задач проектування й експлуатації систем, що
складаються з великого числа тотожних або подібних елементів.
Системи масового обслуговування, подані кількісними моделями, видаються
на фоні реальних ситуацій сильно спрощеними. Але відносно прості моделі
можуть бути використані для одержання якісного або наближеного
кількісного уявлення про поведінку систем, що мають складнішу структуру.
Основну увагу звертають на операційні характеристики моделей, до яких
належать: середня довжина черги, середній час очікування на
обслуговування, вірогідність того, що всі компоненти обслуговуючої
системи виявляться зайнятими, а також інші показники функціональної
ефективності системи. Після оцінювання цих характеристик можна
переходити до побудови відповідної економічної моделі і до наступних
процедур пошуку оптимальних керуючих рішень.
У більшості випадків для розв’язання кожної конкретної задачі
застосовується метод оптимізації з вузькою цільовою настановою, а якщо ж
система виявляється занадто складною, застосовуються методи імітаційного
моделювання.
Області застосування систем масового обслуговування.
Основи теорії систем масового обслуговування були закладені в працях
датського математика, співробітника Копенгагенської телефонної компанії
А. К. Ерланга і отримали широкий розвиток у подальших дослідженнях.
Системи масового обслуговування (СМО) зустрічаються повсюди, і це
пояснюється широкою розповсюдженістю черг. Черги виникають у кав’ярні,
магазині, перукарні, бібліотеці, на бензозаправній станції тощо. До
числа менш очевидних прикладів належать такі ситуації, коли доводиться
затримуватися перед світлофором, очікувати одержання довідки по телефону
або, скажімо, чекати на прибуття ранкової пошти. Для всіх цих ситуацій
характерним є наявність індивідуумів або об’єктів, що потребують
обслуговування, і виникнення затримок у тих випадках, коли обслуговуючий
апарат зайнятий.
Такі процеси утворення черг або затримок в обслуговуванні ефективно
аналізуються методами дослідження операцій. Проте витрати, пов’язані з
науковим аналізом тієї чи іншої практичної задачі масового
обслуговування, вважаються (як і в будь-якій іншій галузі
організаційного управління) виправданими лише за умови, що економічні
наслідки керуючих рішень в сфері, яка аналізується, мають істотний
вплив. Як показує досвід, практичне застосування моделей масового
обслуговування є економічно вигідним при розв’язуванні двох типів задач,
між якими не можна провести чіткої межі, так що можуть існувати
різноманітні проміжні варіанти.
До першого типу належать задачі проектування й експлуатації систем, що
складаються з великого числа тотожних або подібних елементів.
Як приклади, що ілюструють характер таких задач, можна розглядати:
задачу визначення кількості касових апаратів у кожному з продовольчих
магазинів, що належать фірмі, яка має розгалужену торгову мережу;
задачу визначення кількості бензоколонок і чисельності обслуговуючого
персоналу на кожній бензозаправній станції великої нафтової компанії;
задачу визначення кількості магістральних ліній зв’язку на кожній
місцевій автоматичній телефонній станції.
Незважаючи на те, що умови функціонування різноманітних підсистем
великої операційної системи масового обслуговування можуть виявитися
неоднаковими, при аналізі, орієнтованому на оптимізацію кількісних
показників, що належать до різноманітних однотипних компонентів системи
(таких, як кількість вузлів обслуговування, чисельність обслуговуючого
персоналу і т.п.), можна використовувати цілком ідентичні процедури.
Отже, розроблені одноразово методологію дослідження і методи розв’язання
задачі можна застосовувати багаторазово, тому що в кожному конкретному
випадку фірмі потрібно лише врахувати відповідні чисельні значення
параметрів, які фігурують у моделі, що використовується.
До другого типу належать задачі параметричної оптимізації окремої
системи масового обслуговування.
Наприклад, визначення кількості і вантажопідіймальності швидкісних
ліфтів у багатоповерховому будинку, що проектується для адміністративних
підрозділів фірми, задачу пошуку оптимального комплекту устаткування для
великого сталеварного заводу, задачу визначення кількості і габаритних
характеристик злітно-посадкових смут у великому аеропорту і т.п.
Разом з тим існують задачі, у яких сполучаються елементи й особливості
як систем першого, так і систем другого типу.
Особливості математичних моделей та операційні характеристики СМО.
В теорії СМО розглядаються моделі масового обслуговування, що піддаються
кількісному аналізу. Системи масового обслуговування, подані цими
моделями, видаються на фоні реальних ситуацій сильно спрощеними. Але
відносно прості моделі можуть бути використані і для одержання якісного
або наближеного кількісного уявлення про поведінку систем, що мають
складнішу структуру.
Науковий аналіз процесів масового обслуговування в багатьох випадках є
складним, тому що при оцінці виливів на режим функціонування системи
таких показників, як частота надходження вимог на обслуговування, час
обслуговування вимог, що надходять, кількість і розміщення різноманітних
компонентів обслуговуючого комплексу і т.д., далеко не завжди можна
покладатися на одну лише інтуїцію.
Основну увагу звертатимемо на операційні характеристики моделей. До цих
характеристик належать: середня довжина черги, середній час очікування
на обслуговування, вірогідність того, що всі компоненти обслуговуючої
системи виявляться зайнятими, а також інші показники функціональної
ефективності системи. Після оцінювання цих характеристик можна
переходити до побудови відповідної економічної моделі і до наступних
процедур пошуку оптимальних керуючих рішень.
Ступінь складності задачі оптимізації залежить від структурних
особливостей самої системи масового обслуговування і від того, наскільки
широкий є діапазон альтернатив, які ми маємо намір проаналізувати. Так,
наприклад, якщо потрібно обрати один із двох конкретних варіантів
розв’язків, що визначають число касових апаратів у супермаркеті, то
оптимальний розв’язок знаходиться за допомогою простого порівняння
кількісних характеристик кожного з розглянутих варіантів. Проте, якщо
мова йде, скажемо, про розробку системи керування повітряним рухом для
центрального аеропорту, то для розв’язання задачі може знадобитися
складніший метод оптимізації в порівнянні з методом, що полягає в
розгляді кожного з припустимих варіантів, тому що число можливих
варіантів у цьому випадку може виявитися безмежно великим.
На даний час не існує єдиного підходу до розв’язання задач оптимізації в
сфері масового обслуговування. У більшості випадків для розв’язання
кожної конкретної задачі застосовується метод оптимізації з вузькою
цільовою настановою (тобто метод, придатний для розв’язання лише даного
класу задач). Якщо ж система виявляється занадто складною,
застосовуються методи імітаційного моделювання.
Структура математичної моделі та класифікація СМО.
Математична модель системи масового обслуговування (СМО) включає
наступні основні елементи: потік вимог, що надходять на вхід системи
(вхідний потік); чергу, що складається з вимог, які очікують на
обслуговування; систему обслуговування; вихідні потоки обслужених,
втрачених вимог та вимог, що надходять на повторне обслуговування;
характеристики якості системи; механізм (дисципліну) обслуговування
(рис.1).
Потік вимог на
повторне обслуговування
Потік втрачених вимог
Рис.1. Структура СМО
Вхідний потік.
Для описання вхідного потоку потрібно задати закон розподілу
вірогідностей, що керує послідовністю моментів надходження вимог на
обслуговування і зазначити кількість таких вимог у кожному черговому
надходженні. Так, наприклад, вимоги на обслуговування в перукарні або в
ресторані можуть надходити в середньому кожні 10 хв. При цьому в умовах
перукарні щоразу надходить одинична вимога (клієнти приходять у
перукарню по одному), а в умовах ресторану можуть надходити як одиничні,
так і групові вимоги (відвідувачі можуть входити в ресторан як по
одному, так і трупами). Системи, у яких вимоги можуть надходити
пакетами, що містять більш однієї вимоги, будемо називати системами з
груповим обслуговуванням). Тривалості інтервалів між послідовними
надходженнями вимог у багатьох випадках практично є статистично
незалежними і стаціонарними протягом тривалого періоду часу, хоча,
зрозуміло, можливі ситуації і цілком іншого характеру. Діаметрально
протилежними за своїм характером є, з одного боку, потоки, у яких
моменти надходження вимог строго визначені, і, з іншого боку, потоки, у
яких тривалості інтервалів між надходженнями вимог є цілком незалежними.
Джерело, що генерує вимоги, звичайно вважають невичерпним. Як приклад,
що ілюструє СМО з джерелом вимог необмеженої потужності, можна навести
велику залізничну станцію.
До числа СМО з джерелом вимог обмеженої потужності належать, наприклад,
парк верстатів певного підприємства, ремонт яких при їхній несправності
виконує спеціальна механічна майстерня.
У деяких випадках при наявності великої черги вимога може відмовитися
від чекання (тобто в чергу не стає або відмовляється від очікування,
простоявши певний час в черзі). У залежності від обставин вона може
надійти на вхід обслуговуючої системи пізніше (на повторне
обслуговування) або вибути назавжди (втрачена вимога). Так, у оптичному
виробництві цілком можливі і дозволяються технологією повернення на
попередні етапи (це є типовим явищем при шліфуванні великих лінз). У
ряді випадків вимога не може стати в чергу через відсутність вільних
місць у блоці чекання (черга з обмеженим числом місць). Таким чином,
характеристики вхідного потоку (тобто потоку заявок на обслуговування)
частково залежать від стану самої обслуговуючої системи.
Дисципліна черги.
Ця характеристика дозволяє описати порядок обслуговування вимог, що
надходять на вхід системи. Частіше всього використовується дисципліна
черги типу: першим прийшов – першим обслуговуєшся. Такий порядок
обслуговування з погляду математичного моделювання є найпростішим; слід
також зауважити, що він стосується лише таких ситуацій, коли вимоги в
чеканні обслуговування вибудовуються в послідовну чергу. Можливі
численні види дисципліни черги, що відрізняються від згаданої вище.
Іноді використовується дисципліна ”прийшов останнім – обслуговуєшся
першим” — це звичайний стек.
–
ph
&
&
–
”
X
Z
\
^
?
Ue
0\h??AEiueD
®
??
?????-
”
X
?
?
U
Ue
.0Z\fh????AeAEiiuue6
8
B
D
¬
®
E
E
????E
????
??
ph%У деяких випадках порядок обслуговування є фактично випадковим. Він
часто практикується, наприклад, шкільними вчителями при опитуванні
учнів. Іноді дисципліна черги будується за деякою системою пріоритетів
(так, наприклад, у випадку, коли приймаються заходи для порятунку
пасажирів потопаючого корабля, у рятувальні шлюпки першими садять жінок
і дітей). Нарешті, за тими чи іншими міркуваннями клієнт може
відмовитися від чекання і прийняти рішення покинути чергу до того, як
його встигнуть обслужити (тобто має місце черга з обмеженим часом
чекання вимог, що надходять).
Механізм обслуговування.
Обслуговуючий механізм характеризується тривалістю процедур
обслуговування і кількістю вимог, які обслужені в результаті виконання
кожної такої процедури. У наведеному вище прикладі, де мова йшла про
обслуговування клієнтів у перукарні або в ресторані, процедура
обслуговування вважається завершеною, коли клієнт (а у випадку
обслуговування в ресторані, можливо, і ціла група клієнтів) залишає
відповідний заклад після надання йому послуг. Тривалість інтервалу часу,
необхідного для реалізації процедури обслуговування, частково залежить
від запитів клієнта (або групи клієнтів). Але вона може залежати також і
від стану самої обслуговуючої системи: так, наприклад, обслуговуючий
персонал може форсувати процедури обслуговування, якщо обслуговування
очікує велике число клієнтів. Як і тривалості інтервалів між
надходженнями вимог, тривалості обслуговування в кожній з обслуговуючих
точок можуть (хоча це і не обов’язково) описуватися за допомогою
незалежних випадкових змінних з ідентичними розподілами вірогідностей
їхніх чисельних значень. У ряді випадків необхідно також враховувати
вірогідність виходу обслуговуючого приладу з ладу після закінчення
деякого обмеженого інтервалу часу.
Для описання механізму обслуговування потрібно також зазначити кількість
і взаємне розташування обслуговуючих приладів або каналів.
Так, наприклад, прилетівши з Нью-Йорка в аеропорт Лондона, пасажир
повинен пройти там паспортну перевірку. При цьому всі пасажири
вишиковуються в одну лінію і кожен із пасажирів, що дочекалися своєї
черги, скеровується до одного з чиновників, що звільнилися і виконують
перевірку паспорта (єдина черга).
Цілком інша картина спостерігається, наприклад, у години пік на вокзалі
біля білетних кас, коли черги утворюються до всіх без винятку касирів. У
цьому випадку відвідувач повинен обрати одну з черг і очікувати
обслуговування з боку цілком визначеного касира. Якщо Ваш вибір виявився
невдалим, перебування в черзі може забрати у Вас навіть більше часу, ніж
у деяких із тих, що прийшли після Вас, яким пощастило стати в „швидші”
черги. (Якщо черги не занадто великі, можна перейти від обраного
спочатку вікна до іншого, біля якого черга стала коротшою).
У кожному з наведених вище прикладів прилади (або канали) функціонують
паралельно. Існує також множина СМО, у яких прилади розташовані
послідовно, так що клієнт змушений переходити від одного приладу до
іншого, іноді простоюючи біля кожного з них у черзі. До таких систем
належать, наприклад, підприємство з дрібносерійним виробництвом, де для
виготовлення партії замовлених виробів вони повинні пройти послідовне
опрацювання в ряді цехів.
Ще одна ситуація, для котрої характерно послідовне розташування
обслуговуючих приладів, виникає при русі автомобіля по одній з міських
магістралей із великою кількістю регульованих перехресть, що викликає
кількаразові вимушені зупинки машини перед світлофорами.
СМО класифікуються за різноманітними ознаками в залежності від
характеристик перебування в черзі, вхідного потоку та дисципліни
обслуговування вимог.
За складом обслуговуючих пристроїв розрізняють одно – (з одним
обслуговуючим пристроєм) та багатоканальні (з багатьма обслуговуючими
пристроями, що паралельно можуть обслуговувати вимоги) СМО.
Якщо для обслуговування в СМО вимога повинна послідовно пройти через
декілька обслуговуючих пристроїв (фаз обслуговування), то така система є
багатофазною, якщо ж після проходження одного пристрою обслуговування
вимога вважається обслуженою то однофазною.
За характеристиками вхідного потоку розрізняються системи з пріоритетами
(вимоги з вищим пріоритетом мають переваги як при визначенні місця в
черзі, так і при обслуговуванні) та системи без пріоритетів (вимоги
рівноправні).
В залежності від наявності чи відсутності черги СМО поділяються на
системи без черг- з відмовами (якщо вимога, що надійшла на вхід СМО, не
може бути обслужена, вона покидає систему) та системи з чергами (вимога
має можливість стати в чергу і очікувати на обслуговування).
В залежності від довжини черги СМО можуть бути з обмеженою чергою
(кількість місць в черзі скінчена) та системи з необмеженою чергою.
В залежності від часу перебування в черзі розрізняються СМО з
необмеженим часом перебування в черзі (вимога, що погранила в чергу,
перебуває в ній до моменту початку обслуговування) та СМО з обмеженим
часом очікування (вимога, що перебуває в черзі, вибуває з неї і виходить
з системи після того, як час очікування перевищує певне критичне
значення).
В залежності від кількості черг системи поділяються на системи з однією
спільною чергою та системи з багатьма чергами.
В системах з багатьма чергами розглядаються підкласи систем без
переходів між чергами та системи з переходами між чергами.
СМО, з яких можуть вибувати необслужені вимоги, називаються системами з
втратами, а системи, в яких вибування вимог до завершення обслуговування
не передбачене – без втрат.
Якщо обслуговуючий пристрій перериває обслуговування вимоги з нижчим
пріоритетом, коли надходить вимога з вищим пріоритетом, то СМО є
системою з перериваннями , якщо ж вимога з вищим пріоритетом очікує
моменту найшвидшого звільнення обслуговуючого пристрою – системою без
переривань. Відмови в роботі обслуговуючого пристрою можна моделювати за
допомогою потоку вимог найвищого пріоритету, що переривають
обслуговування, і потребують для обслуговування певного часу (час
ліквідакції аварії – відмови обслуговуючого пристрою).
Характеристики якості та проблеми аналізу СМО.
До основних характеристик якості обслуговування належать:
1) вірогідність прямої або умовної втрати вимоги;
2) середній час обслуговування вимоги;
3) середня довжина черги;
4) вірогідність втрати вимоги, що надійшла;
5) завантаження обслуговуючих апаратів і ін.
Аналіз систем масового обслуговування.
Кожен із можливих варіантів СМО неважко описати точною математичного
моделлю, проте це часто майже нічого не дає, якщо оцінювати одержані на
основі такого типу описань результати із практичної точки зору. Тому при
аналізі СМО в більшості випадків практикується комбіноване застосування
наступних двох підходів до розв’язання таких задач.
Перший підхід полягає у використанні для наближених описань реальної
системи простих математичних моделей. Потім, керуючись результатами
аналізу первісних простих моделей і використовуючи ці результати як
певний орієнтир, операційник може розробити імітаційну модель, що
дозволить за допомогою комп’ютера врахувати ті аспекти задачі, які є
істотними, але у той же час важко піддаються аналізу на першому етапі
математичного моделювання.
Відповідь на питання про те, які операційні характеристики є
найважливішими для формування керуючих рішень, зрозуміло, може бути дана
лише з врахуванням конкретних умов задачі. Проте слід зазначити, що
операційиика, як правило, цікавлять розподіли вірогідностей для числа
вимог, що надійшли в систему, і для тривалостей їх очікування, або
принаймні середні значення випадкових змінних, що описують ці
характеристики на великому відтинку часу. Крім того, іноді потрібно
знати вірогідність того, що всі обслуговуючі прилади виявляться вільними
або зайнятими; розподіл вірогідностей для тривалості вільних або,
навпаки, зайнятих періодів; вірогідність того, що довжина черги (число
вимог, що очікують на обслуговування в черзі) перевищить деяке наперед
задане число, а також розподіл вірогідностей для інтервалу між
послідовними моментами завершення процедур обслуговування. Якщо модель
масового обслуговування не дуже складна, то для всіх згаданих вище
характеристик вдасться одержати точні, аналітичні вирази, зручні для
обчислень.
Операційні методи дослідження СМО орієнтовані на оптимізацію відповідних
керуючих рішень. При аналізі прикладів виявляється, що практично в
кожній із ситуацій керівник повинен брати до уваги всі три компоненти
системи масового обслуговування: вхідний потік вимог на обслуговування,
дисципліну черги і механізм обслуговування. Більш того, між
різноманітними варіантами керуючих рішень існує ряд складних
взаємозв’зків. Наприклад, середню тривалість очікування для вимоги на
обслуговування можна зменшити шляхом зміни частоти надходжень вимог на
вхід обслуговуючої системи, збільшенням кількості обслуговуючих
приладів, використанням більш швидкодіючих приладів, а також шляхом
скорочення розкиду часів обслуговування.
Результати дослідження системи обслуговування також можна
використовувати для оптимізації моделі з вартісними характеристиками, в
якій мінімізується сума витрат, пов’язаних з наданням послуг і втрат,
обумовлених затримками в їх наданні. На рис.2 зображена типова вартісна
модель системи обслуговування (в грошових одиницях за одиницю часу), де
витрати на обслуговування зростають із зростанням його рівня. В той же
час втрати, обумовлені затримками в наданні послуг, зменшуються зі
зростанням рівня обслуговування.
Загальні затрати
Затрати на обслуговування в
одиницях часу
Втрати клієнтів
Оптимальний рівень
від очікування в
обслуговування
одиницях часу
Рис.2. Вартісна модель СМО
Головною проблемою, пов’язаною із застосуванням вартісних моделей, є
складність оцінювання втрат в одиницю часу, обумовлених затримками в
наданні послуг. Зокрема, це особливо відчутно, коли послуги надаються
індивідууму, чия поведінка може не співпадати з інтересами
функціонування системи обслуговування.
При дослідженні СМО розв’язуються одна чи декілька наступних задач:
1) задачі аналізу СМО – визначення характеристик якості обслуговування в
залежності від параметрів і властивостей вхідного потоку вимог,
параметрів і структури системи обслуговування і дисципліни
обслуговування;
2) задачі параметричного синтезу – визначення параметрів системи
обслуговування при її заданій структурі залежно від параметрів і
властивостей потоку вимог, дисципліни і якості обслуговування.
3) задачі синтезу структури системи з оптимізацією її параметрів —
необхідно досягти того, щоб при заданих потоках, дисципліні і якості
обслуговування вартість СМО була мінімальною або були мінімальними
втрати викликів при заданих потоках, дисципліні і вартості системи.
Література
Карлин С. Математические методы в теории игр, программировании и
экономике. -М.: Мир, 1964.
Вентцель Е.С. Введение в исследование операций. Сов. радио, 1964.
Пономаренко О.І., Пономаренко В.О. Системні методи в економіці, бізнесі
й менеджменті. -К.: Либідь, 1995.
Пономаренко О.І., Перестюк М.О., Бурим В.М. Основи математичної
економіки. -К.: Інформтехніка, 1995.
Горелик В.А., Ушаков М.А. Исследование операций. -М.: Машиностроение,
1986.
PAGE
PAGE 8
Джерело
вимог
Вхідний потік вимог
Черга
(черги)
Обслуговуючий
пристрій
(пристрої)
Вихідний потік вимог
Затрати
Рівень обслуговування
Нашли опечатку? Выделите и нажмите CTRL+Enter
