Актуальність роботи
У багатьох областях практичної діяльності людини ми стикаємося з необхідністю перебування в стані очікування. Подібні ситуації виникають в чергах в квиткових касах, в крупних аеропортах, при очікуванні обслуговуючим персоналом літаків дозволу на зліт або посадку, на телефонних станціях в очікуванні звільнення лінії абонента, в ремонтних цехах в очікуванні ремонту верстатів і устаткування, на складах постачальницько-збутових організацій в очікуванні розвантаження або вантаження транспортних засобів. У всіх перерахованих випадках маємо справу з масовістю і обслуговуванням. Вивченням таких ситуацій займається теорія масового обслуговування. Випадковий характер потоку заявок, а в загальному випадку і тривалості обслуговування приводить до того, що в системі масового обслуговування відбуватиметься якийсь випадковий процес. Щоб дати рекомендації по раціональній організації цього процесу і пред'явити розумні вимоги до СМО, необхідно вивчити випадковий процес, що протікає в системі, описати його математично. Цим і займається теорія масового обслуговування. Звичайно, об'єм даної роботи не дозволяє детально вивчити цю теорію, але основні, базові її елементи були представлені. На їх основі можливий подальший розгляд цій досить актуальної на сучасному світі теми.
Практична цінність результатів роботи
Результати, отримані в ході виконання цієї роботи, можуть бути використані для оптимізації роботи будь-якоі системи массового обслуговування.
Наукова значущість роботи
По теорії масового обслуговування є декілька спеціальних монографій отдельнве розділи теорії викладені у ряді монографій і підручників по теорії вірогідності і теорії випадкових процесів, але окремі монографії складні для первинного вивчення теорії, а окремі розділи не дають загального уявлення про теорію в цілому. Дана ж робота дає базові знання про теорію масового обслуговування зокрема присвячена її розгляду з погляду марківської теорії
Теорія масового обслуговування як розділ теорії вірогідності виникла порівняно недавно. Перші роботи з'явилися на початку минулого сторіччя і були викликані потребами практики, в частковості широким розвитком телефонних мереж. Тому і зараз в роботах по СМО широко використовується термінологія, запозичена з телефонії: вимоги, виклики заявки, канали зв'язку, тривалість обслуговування і тому подібне Декілька пізніше було обернено увага, що загальні математичні моделі, досліджувані як моделі телефонії, можуть описувати і інші життєві явища. В даний час методи і результати теорії масового обслуговування з успіхом використовуються при вирішенні проблем теорії надійності аналізі процесів функціонування сложныхсистем, розробці автоматизованих систем управління різних видів і в багатьох інших технічних, економічних і соціальних областях. Математичну теорію масового обслуговування можна охарактеризувати двома способами: вказівкою області практичних завдань, до вирішення яких вона застосовується, і вказівкою класу що вивчаються нею випадкових процесів.Практичні завдання теорії масового обслуговування зв'язані з дослідженням будь-яких операцій, що складаються з багатьох однорідних елементарних операцій на здійснення яких впливають випадкові чинники. Прикладом може служити магазин продовольчих товарів.
При дослідженні операцій дуже часто доводиться зустрічатися з аналізом роботи своєрідних систем, званих системами масового обслуговування (СМО). Прикладами таких систем можуть слугувати: телефонні станції, ремонтні майстерні, квиткові каси, довідкові бюро, магазини, перукарні і тому подібне.
Кожна СМО складається з якогось числа обслуговуючих одиниць, які ми називатимемо каналами обслуговування. Як «канали» можуть фігурувати: лінії зв'язку, робочі точки, прилади, залізничні колії, ліфти, автомашини і так далі
Системи масового обслуговування можуть бути одноканальними або багатоканальними.
Кожна СМО призначена для обслуговування (виконання) якогось потоку заявок (або «вимог»), що поступають на СМО в якісь, взагалі кажучи, випадкові моменти часу. Обслугування заявки, що поступила, триває якийсь час, після чого канал звільняється і готовий до принятття наступної заявки. Випадковий характер потоку заявок призводить до того, що в якісь проміжки часу на вході СМО накопичується надмірно велика кількість заявок (вони або утворюють чергу, або покидають СМО необслуженими); у інші ж періоди СМО працюватиме з недовантаженням або взагалі простоювати.
Кожна система масового обслуговування, залежно від числа каналів і їх продуктивності, а також від характеру потоку заявок, володіє якоюсь пропускною спроможністю, що дозволяє їй більш менш успішно справлятися з потоком заявок. Предмет теорії масового обслуговування — встановлення залежності між характером потоку заявок, кількістю каналів, їх производи-тельностью, правилами роботи СМО і успішністю (ефективністю) обслуговування.
Як характеристики ефективності обслуговування, в зависимости від умов завдання і цілей дослідження, можуть застосовуватися різні величини і функції, наприклад:
Випадковий характер потоку заявок, а в загальному випадку і тривалості обслуговування призводить до того, що в системі масового обслуговування відбуватиметься якийсь випадковий процес. Щоб дати рекомендації по раціональній організації цього процесса і пред'явити розумні вимоги до СМО, необхідно вивчити випадковий процес, що протікає в системі, описати його математично. Цим і займається теорія масового обслуговування.
Відмітимо, що за останні роки сфера застосування математических методів теорії масового обслуговування безперервно розширяется і все більше виходить за межі завдань, пов'язаних з «обслуговуючими організаціями» в буквальному розумінні слова. Як своєрідні системи масового обслуговування можуть розглядатися: електронні цифрові обчислювальні машини; системи збору і обробки інформації; автоматизовані виробничі цехи, потокові лінії; транспортні системи; системи протиповітряної оборони і тому подібне
Близькими до завдань теорії масового обслуговування є багато завдань, що виникають при аналізі надійності технічних пристроїв.
1. ЗВ'ЯЗОК СИСТЕМ МАСОВОГО ОБСЛУГОВУВАННЯ І МАРКОВСЬКОЙ ТЕОРІЇ
Математичний аналіз роботи СМО дуже полегшується, якщо випадковий процес, що протікає в системі, є марківським. Тоді вдається порівняно просто описати роботу СМО за допомогою аппарату звичайних диференціальних (у граничному випадку — линейных алгебраїчних) рівнянь і виразити в явному вигляді основні характеристики ефективності обслуговування через параметри СМО і потоку заявок.
Ми знаємо, що для того, щоб процес, що протікає в системі, був марківським, потрібно, щоб всі потоки подій,що переводять систему із стану в стан, були пуассоновскими (потоками без післядії). Для СМО потоки подій — це потоки заявок, потоки «обслуговування» заявок і так далі Якщо ці потоки не є пуассоновскими, математичний опис процесів, що відбуваються в СМО, стає незрівнянно складнішим і вимагає більш загромоздкого апарату, доведення якого до явних, аналітичних формул вдається тільки в окремих, простих випадках. Проте, все ж таки апарат «марківської» теорії масового обслуговування може стати в нагоді і у тому випадку, коли процес, що протікає в СМО, відмінний від марковского — з його допомогою характеристики ефективності СМО можуть бути оцінені приблизно. Слід відмітити, що чим складніше СМО, чим більше в ній каналів обслуговування, тим точніше виявляються приближенні формули, отримані за допомогою марківської теорії. Слід також відмітити, що у ряді випадків для ухвалення обгрунтованих рішень по управлінню роботою СМО зовсім і не потрібно точного знания всіх її характеристик — достатньо і наближеного, орієнтування.
У даній роботі будуть викладені елементи теорії масового обслуговування, головним чином в тій простій формі, якої вони набувають в рамках марківської теорії.
2. КЛАСИФІКАЦІЯ СИСТЕМ МАСОВОГО ОБСЛУГОВУВАННЯ І ЇХ ОСНОВНІ ХАРАКТЕРИСТИКИ
2.1 Класифікація СМО
Системи масового обслуговування взагалі можуть бути двох типів.
Системи з відмовами. У таких системах заявка, що поступила в мить, коли всі канали зайняті, дістає «відмову», покидає СМО і надалі процесі обслуговування не бере участь.
Системи з очікуванням (з чергою). У таких системах заявка, що поступила в мить, коли всі канали зайняті, стає в чергу і чекає, поки не звільниться один з каналів. Як тільки освободится канал, приймається до обслуговування одна із заявок, що стоять в черзі.
Обслуговування в системі з очікуванням може бути «впорядкованим» (заявки обслуговуються в порядку надходження) і «неврегульованим» (заявки обслуговуються у випадковому порядку). Крім того, в некоторых СМО застосовується так зване «обслуговування з пріоритетом», коли деякі заявки обслуговуються насамперед, предпочтительно перед іншими.
Системи с-очередью діляться на системи з необмеженим ожиданием і системами з обмеженим очікуванням.
У системах з необмеженим очікуванням кожна заявка, поступившая в мить, коли немає вільних каналів, стає в чергу і «терпляче» чекає звільнення каналу, який прийме її до обслуживанию. Будь-яка заявка, що поступила в СМО, рано чи пізно буде обслужена.
У системах з обмеженим очікуванням на перебування заявки в черзі накладаються ті або інші обмеження. Ці обмеження могут стосуватися довжини черги (числа заявок, одночасно перебуваючих в черзі), часу перебування заявки в черзі (після якогось терміну перебування в черзі заявка покидає чергу і йде), загального часу перебування заявки в СМО і так далі
Залежно від типу СМО, при оцінці її ефективності можуть застосовуватися ті або інші величини (показники ефективності). Наприклад, для СМО з відмовами однієї з найважливіших характеристик її продуктивності є так звана абсолютна пропускная здатність — середнє число заявок, яке може обслужити система за одиницю часу.
Разом з абсолютною, часто розглядається відносна пропускна спроможність СМО — середня частка заявок, що поступили, що обслуговується системою (відношення середнього числа заявок, що обслуговуються системою в одиницю часу, до среднему числа заявок, що поступають за цей час).
Окрім абсолютної і відносної пропускної здібностей, при аналізі СМО з відмовами нас можуть, залежно від завдання исследования, цікавити і інші характеристики, наприклад:
2.2. СМО з очікуванням.
Очевидно, для СМО з необмеженим очікуванням як абсолютная, так і відносна пропускна спроможність втрачають сенс, оскільки кожна заявка, що поступила, рано чи пізно буде обслужена. Зате для такої СМО вельми важливими характеристиками є:
Для СМО з обмеженим очікуванням інтерес представляють обидві групи характеристик: як абсолютна і відносна пропускна здатності, так і характеристики очікування.
Для аналізу процесу, що протікає в СМО, істотно знати основные параметри системи: число каналів п, інтенсивність потоку заявок X, продуктивність кожного каналу (середнє число заявок обслуговуване каналом в одиницю часу), умови образования черги (обмеження, якщо вони є).
Залежно від цих параметрів ми і будемо надалі выражать характеристики ефективності роботи СМО.
Рахуватимемо всі потоки подій, переводячі СМО із стану в стан, пуассоновскими. У тих окремих випадках, коли ми розглядатимемо не-марківські системи масового обслуживания, ми кожного разу обумовлюватимемо це спеціально.
Нагадаємо, що у разі, коли пуассоновский потік стаціонарний (простий потік), інтервал часу Т між подіями в цьому потоке є випадкова величина, розподілена по показовому закону:
У разі, коли з якогось стану St систему виводять відразу декілька простих потоків, величина Т — час перебування системы (підряд) в даному стані є випадкова величина, распределенная згідно з (2.1) законом, де ? — сумарна інтенсивність всіх потоков подій, що виводять систему з даного стану.
Для опису функціонування магазина продовольчих товарів найбільш підходить СМО з обмеженим часом очікування.
Розглянемо СМО подібного типу, залишаючись в рамках марківської схеми. Припустимо, що є –канальная СМО з очікуванням, в якій число місць в черзі не обмежене, але час перебування заявки в черзі обмежений деяким випадковим терміном Точ з середнім значенням Точ . Таким чином на кожну заявку діє як би «потік відходів» з інтенсивністю
Якщо цей потік пуассоновский, то процес, що протікає в СМО, буде марківським. Знайдемо для нього вірогідність станів. Знову нумеруватимемо стани системи по числу заявок, пов'язаних з системою, – як обслуговуваних, так і таких, що стоять в черзі
Граф станів системи показаний на мал. 2.1.
Розмітимо цей граф, тобто проставимо біля стрілок відповідні інтенсивності. Знову, як і раніше, у всіх стрілок, ведучих зліва направо, стоятиме інтенсивність потоку заявок ?. Для станів без черги у стрілок, ведучих з них справа наліво, буде, як і раньше, стояти сумарна інтенсивність потоку обслуговуванні всіх занятых каналів. Що стосується станів з чергою, то у стрілок, ведущих з них справа наліво стоятиме сумарна інтенсивність потока обслуговуванні всіх п каналів nµ плюс відповідна интенсивность потоку відходів з черги. Якщо в черзі коштують r заявок, то сумарна інтенсивність потоку відходів буде рівна rv.
Як видно з графа, перед нами знову схема загибелі і розмноження: застосовуючи загальні вирази для граничної вірогідності состояний в цій схемі, напишемо:
або, вводячи позначення
Відзначимо деякі особливості розглянутої СМО з «нетерпелячими» заявками в порівнянні з раніше розглянутою СМО з «терпелячими» заявками.
Якщо довжина черги не обмежена заздалегідь ніяким числом і заявки «терплячі» (не йдуть з черги), то стаціонарний предельный режим існує тільки у разі р
Для СМО з «нетерплячими» заявками поняття «Вірогідність відмови» не має сенсу — кожна заявка стає в чергу, але может і не дочекатися обслуговування, пішовши завчасно.
Відносну пропускну спроможність q такому СМО можна підрахувати таким чином. Очевидно, обслужені будуть всі заявки, окрім тих, які підуть з черги достроково. Підрахуємо, яке в середньому число заявок покидає черга достроково. Для цього обчислимо середнє число заявок в черзі:
r = 1* pn+1 + 2*pn+2+.+r*pn+r+.
.На кожну з цих заявок діє «потік відходів» з інтенсив ностью v. Значить, з середнього числа r заявок в черзі в середньому будет йти, не дочекавшись обслуговування, vr заявок в одиницю времени; всього в одиницю часу в середньому буде обслужено
заявок. Відносна пропускна спроможність СМО буде
Середнє число зайнятих каналів z як і раніше отримаємо, ділячи абсолютную пропускну спроможність на µ:
Це дозволяє обчислити середнє число заявок в черзі г, не суммируя нескінченного ряду (2.2). Дійсно, з (2.5) отримаємо:
а вхідне в цю формулу середнє число зайнятих каналів можна знайти як математичне очікування випадкової величини Z, що набуває значень 0,1, 2 ..., п з вірогідністю p0, p1, p2.,[1-(p0 +p1 +.+pn-1)]:
Z= 0*p0+ 1*p1+2*p2+.+ n*[1-(p0 +p1 +.+pn-1)]=p1+2*p2+.+ n*[1-(p0 +p1 +.+pn-1)] (2.7)
Відмітимо, що у формулі (7.1) фігурує сума нескінченного ряду, що не є прогресією. Проте ця сумма обчислюється приблизно, причому достатньо легко, оскільки члени ряду швидко убувають із збільшенням їх номера. Як приближенного значення для нескінченної суми береться сума кінцевого числа г — 1 членів, а залишок оцінюється таким чином:
У багатьох областях практичної діяльності людини ми стикаємося з необхідністю перебування в стані очікування. Подібні ситуації виникають в чергах в квиткових касах, в крупних аеропортах, при очікуванні обслуговуючим персоналом літаків дозволу на зліт або посадку, на телефонних станціях в очікуванні звільнення лінії абонента, в ремонтних цехах в очікуванні ремонту верстатів і устаткування, на складах постачальницько-збутових організацій в очікуванні розвантаження або вантаження транспортних засобів. У всіх перерахованих випадках маємо справу з масовістю і обслуговуванням. Вивченням таких ситуацій займається теорія масового обслуговування.
Випадковий характер потоку заявок, а в загальному випадку і тривалості обслуговування приводить до того, що в системі масового обслуговування відбуватиметься якийсь випадковий процес. Щоб дати рекомендації по раціональній організації цього процесса і пред'явити розумні вимоги до СМО, необхідно вивчити випадковий процес, що протікає в системі, описати його математично. Цим і займається теорія масового обслуговування.