На практичному занятті розглянемо шлях і порівняємо результати моделювання з теоретичним рішенням.
ВСТУП
ГЛАВА I. ПОСТАНОВКА ЗАВДАНЬ МАСОВОГО ОБСЛУГОВУВАННЯ
1.1 Загальні поняттятеорії масового обслуговування
1.2 Моделювання систем масового обслуговування
1.3 Графи станів СМО
1.4 Випадкові процеси
Розділ II. РІВНЯННЯ, ОПИСУЮЧІ СИСТЕМИ МАСОВОГО ОБСЛУГОВУВАННЯ
2.1 Рівняння Колмогорова
2.2 Процеси «народження – загибелі»
2.3 Економіко-математична постановка задач масового обслуговування
Розділ III. МОДЕЛІ СИСТЕМ МАСОВОГО ОБСЛУГОВУВАННЯ
3.1 Одноканальна СМО з відмовами в обслуговуванні
3.2 Багатоканальна СМО з відмовами в обслуговуванні
3.3 Модель багатофазної системи обслуговування туристів
3.4 Одноканальна СМО з обмеженою довжиною черги
3.5 Одноканальна СМО з необмеженою чергою
3.6 Багатоканальна СМО з обмеженою довжиною черги
3.7 Багатоканальна СМО з необмеженою чергою
3.8 Аналіз системи масового обслуговування супермаркету
ВИСНОВОК
Вступ
В даний час з'явилася велика кількість літератури, присвяченої безпосередньо теорії масового обслуговування, розвитку її математичних аспектів, а також різних сфер її застосування – військової, медичної, транспортної, торгівлі, авіації та ін.
Теорія масового обслуговування спирається на теорію ймовірностей і математичну статистику. Початковий розвиток теорії масового обслуговування пов'язаний з ім'ям датського вченого А.К. Ерланга (1878-1929), з його працями в галузі проектування та експлуатації телефонних станцій.
Теорія масового обслуговування - область прикладної математики, що займається аналізом процесів у системах виробництва, обслуговування, управління, у яких однорідні події повторюються багаторазово, наприклад, на підприємствах побутового обслуговування; у системах прийому, переробки та передачі інформації; автоматичних лініях виробництва та ін. Великий внесок у розвиток цієї теорії зробили російські математики А.Я. Хінчін, Б.В. Гнєденко, О.М. Колмогоров, Є.С. Вентцель та ін.
Предметом теорії масового обслуговування є встановлення залежностей між характером потоку заявок, числом каналів обслуговування, продуктивністю окремого каналу та ефективним обслуговуванням з метою знаходження найкращих шляхів управління цими процесами. Завдання теорії масового обслуговування носять оптимізаційний характер і в кінцевому підсумку включають економічний аспект визначення такого, варіанта системи, при якому буде забезпечений мінімум сумарних витрат від очікування обслуговування, втрат часу і ресурсів на обслуговування і від простоїв каналів обслуговування.
У комерційній діяльності застосування теорії масового обслуговування поки що не знайшло бажаного поширення.
В основному це пов'язано з труднощами постановки завдань, необхідністю глибокого розуміння змісту комерційної діяльності, а також надійного та точного інструментарію, що дозволяє прораховувати у комерційній діяльності різні варіантинаслідків управлінських рішень.
Глава I . Постановка завдань масового обслуговування
1.1 Загальні поняття теорії масового обслуговування
Природа масового обслуговування, у різних сферах, дуже тонка та складна. Комерційна діяльність пов'язані з виконанням безлічі операцій на етапах руху, наприклад товарної маси зі сфери виробництва, у сферу споживання. Такими операціями є навантаження товарів, перевезення, розвантаження, зберігання, обробка, фасування, реалізація. Окрім таких основних операцій процес руху товарів супроводжується великою кількістюпопередніх, підготовчих, супутніх, паралельних та наступних операцій із платіжними документами, тарою, грошима, автомашинами, клієнтами тощо.
Для перерахованих фрагментів комерційної діяльності характерні масовість надходження товарів, грошей, відвідувачів у випадкові моменти часу, потім їхнє послідовне обслуговування (задоволення вимог, запитів, заявок) шляхом виконання відповідних операцій, час виконання яких носить також випадковий характер. Все це створює нерівномірність у роботі, породжує недовантаження, простий та перевантаження у комерційних операціях. Багато неприємностей завдають черги, наприклад, відвідувачів у кафе, їдальнях, ресторанах, або водіїв автомобілів на товарних базах, які очікують на розвантаження, навантаження чи оформлення документів. У зв'язку з цим виникають завдання аналізу існуючих варіантіввиконання всієї сукупності операцій, наприклад, торгового залу супермаркету, ресторану або в цехах виробництва власної продукції з метою оцінки їхньої роботи, виявлення слабких ланок та резервів для розробки зрештою рекомендацій, спрямованих на збільшення ефективності комерційної діяльності.
Крім того, виникають інші завдання, пов'язані зі створенням, організацією та плануванням нового економічного, раціонального варіанту виконання безлічі операцій у межах торгового залу, кондитерського цеху, всіх ланок обслуговування ресторану, кафе, їдальні, планового відділу, бухгалтерії, відділу кадрів та ін.
Завдання організації масового обслуговування виникають практично у всіх сферах людської діяльності, наприклад обслуговування продавцями покупців у магазинах, обслуговування відвідувачів на підприємствах громадського харчування, обслуговування клієнтів на підприємствах побутового обслуговування, забезпечення телефонних розмовна телефонній станції, надання медичної допомоги хворим на поліклініці тощо. У всіх наведених прикладах виникає потреба у задоволенні запитів великої кількостіспоживачів.
Перелічені завдання можна успішно вирішувати за допомогою методів та моделей спеціально створеної для цих цілей теорії масового обслуговування (ТМО). У цій теорії пояснюється, що обслуговувати необхідно будь-кого або що-небудь, що визначається поняттям «заявка (вимогу) на обслуговування», а операції обслуговування виконуються будь-ким, званими каналами (вузлами) обслуговування. Роль заявок у комерційній діяльності виконують товари, відвідувачі, гроші, ревізори, документи, а роль каналів обслуговування - продавці, адміністратори, кухарі, кондитери, офіціанти, касири, товарознавці, вантажники, торгове обладнання та ін. наприклад, кухар у процесі приготування страв є каналом обслуговування, а в іншому - виступає в ролі заявки на обслуговування, наприклад, до завідувача виробництва за отриманням товару.
Заявки з масовості надходження обслуговування утворюють потоки, які до виконання операцій обслуговування називаються вхідними, а після можливого очікування початку обслуговування, тобто. простоячи в черзі, утворюють потоки обслуговування в каналах, а потім формується вихідний потік заявок. Загалом сукупність елементів вхідного потоку заявок, черги, каналів обслуговування і потоку заявок, що виходить, утворює найпростішу одноканальну систему масового обслуговування - СМО.
Під системою розуміється сукупність взаємозалежних та. цілеспрямовано взаємодіючих елементів (елементів). Прикладами таких найпростіших СМО в комерційній діяльності є місця прийому та обробки товарів, вузли розрахунку з покупцями в магазинах, кафе, їдалень, робочі місця економіста, бухгалтера, комерсанта, кухарі на роздачі тощо.
Процедура обслуговування вважається завершеною, коли заявка обслуговування залишає систему. Тривалість інтервалу часу, необхідного для реалізації процедури обслуговування, залежить в основному від характеру запиту заявки на обслуговування, стану обслуговуючої системи та каналу обслуговування.
Дійсно, тривалість перебування покупця у супермаркеті залежить, з одного боку, від особистісних якостейпокупця, його запитів, від асортименту товарів, який він збирається придбати, а з іншого - від форми організації обслуговування та обслуговуючого персоналу, що може значно вплинути на час перебування покупця у супермаркеті та інтенсивність обслуговування. Наприклад, оволодіння касирами-контролерами роботи «сліпим» методом на касовому апараті дозволило збільшити пропускну спроможністьвузлів розрахунку у 1,3 рази та заощадити час, що витрачається на розрахунки з покупцями по кожній касі більш ніж на 1,5 год на день. Впровадження єдиного вузла розрахунку у супермаркеті дає відчутні переваги покупцю. Так, якщо при традиційній формі розрахунків час обслуговування одного покупця становив у середньому 1,5 хв, то при введенні єдиного вузла розрахунку – 67 с. З них 44 с. йдуть на оформлення покупки в секції та 23 с. безпосередньо на розрахунки за покупки. Якщо покупець робить кілька покупок у різних секціях, то втрати часу скорочуються при придбанні двох покупок у 1,4 раза, трьох – у 1,9, п'яти – у 2,9 раза.
Під обслуговуванням заявок розумітимемо процес задоволення потреби. Обслуговування має різний характер за своєю природою. Однак, у всіх прикладах заявки, що надійшли, потребують обслуговування з боку будь-якого пристрою. У деяких випадках обслуговування здійснюється однією людиною (обслуговування покупця одним продавцем, у деяких - групою людей (обслуговування хворого на лікарську комісію в поліклініці), а в деяких випадках - технічними пристроями (продаж газованої води, бутербродів автоматами). Сукупність засобів, що здійснюють обслуговування заявок називається каналом обслуговування.
Якщо канали обслуговування здатні задовольнити однакові заявки, канали обслуговування називаються однорідними. Сукупність однорідних каналів обслуговування називається системою, що обслуговує.
У систему масового обслуговування надходить велика кількість заявок у випадкові моменти часу, тривалість обслуговування яких також є випадковою величиною. Послідовне надходження заявок у систему обслуговування називається вхідним потоком заявок, а послідовність заявок, що залишають систему обслуговування, - потоком, що виходить.
Випадковий характер розподілу тривалості виконання операцій обслуговування поряд з випадковим характером надходження вимог на обслуговування призводить до того, що в каналах обслуговування протікає випадковий процес, який може бути названий (за аналогією з вхідним потоком заявок) потоком обслуговування заявок або просто потоком обслуговування.
Зауважимо, що заявки, що надходять до системи обслуговування, можуть залишити її і не обслуговуючи. Наприклад, якщо покупець не знайде в магазині потрібний товар, він залишає магазин, будучи не обслуженим. Покупець може залишити магазин також, якщо потрібний товар є, але велика черга, а покупець не має часу.
Теорія масового обслуговування займається вивченням процесів, пов'язаних із масовим обслуговуванням, розробкою методів вирішення типових завдань масового обслуговування.
При дослідженні ефективності роботи системи обслуговування важливу роль відіграють різні способирозташування у системі каналів обслуговування.
При паралельному розташуванні каналів обслуговування вимога може бути обслужена будь-яким вільним каналом. Прикладом такої системи обслуговування є розрахунковий вузол у магазинах самообслуговування, де кількість каналів обслуговування збігається з касирів-контролерів.
Насправді часто обслуговування однієї заявки здійснюється послідовно кількома каналами обслуговування. При цьому черговий канал обслуговування починає роботу з обслуговування заявки після того, як попередній канал закінчив свою роботу. У таких системах процес обслуговування має багатофазовий характер, обслуговування заявки одним каналом називається фазою обслуговування. Наприклад, якщо в магазині самообслуговування є відділи із продавцями, то покупці спочатку обслуговуються продавцями, а потім уже касирами-контролерами.
Організація системи обслуговування залежить від волі людини. Під якістю функціонування системи теорії масового обслуговування розуміють не те, наскільки добре виконано обслуговування, а те, наскільки повно завантажена система обслуговування, чи не простоюють канали обслуговування, чи не утворюється черга.
У комерційній діяльності заявки, що надходять до системи масового обслуговування, виступають з високими претензіями ще й на якість обслуговування в цілому, яке включає не тільки перелік характеристик, що історично склалися та розглядаються безпосередньо в теорії масового обслуговування, а й додаткові характерні для специфіки комерційної діяльності. зокрема окремих процедур обслуговування, вимоги, до рівня яких на сьогодні сильно зросли. У зв'язку із цим необхідно враховувати ще й показники комерційної діяльності.
Роботу системи обслуговування характеризують такі показники. Як час очікування початку обслуговування, довжина черги, можливість отримання відмови в обслуговуванні, можливість простою каналів обслуговування, вартість обслуговування та зрештою задоволення якістю обслуговування, яке ще включає показники комерційної діяльності. Щоб поліпшити якість функціонування системи обслуговування, необхідно визначити, яким чином розподілити заявки, що надходять між каналами обслуговування, яку кількість каналів обслуговування необхідно мати, як розмістити або згрупувати канали обслуговування або обслуговуючі апарати для поліпшення показників комерційної діяльності. Для вирішення перелічених завдань існує ефективний методмоделювання, що включає та поєднує досягнення різних наук, у тому числі математики.
1.2 Моделювання систем масового обслуговування
Переходи СМО з одного стану до іншого відбуваються під впливом цілком певних подій - надходження заявок та їх обслуговування. Послідовність появи подій, що йдуть одна за одною у випадкові моменти часу, формує так званий потік подій. Прикладами таких потоків у комерційній діяльності є потоки різної природи – товарів, грошей, документів, транспорту, клієнтів, покупців, телефонних дзвінків, переговорів. Поведінка системи зазвичай визначається одним, а одночасно кількома потоками подій. Наприклад, обслуговування покупців у магазині визначається потоком покупців та потоком обслуговування; у цих потоках випадковими є моменти появи покупців, час очікування у черзі та час, що витрачається обслуговування кожного покупця.
При цьому основний характерною рисоюпотоків є ймовірнісний розподіл часу між сусідніми подіями. Існують різні потоки, що відрізняються своїми характеристиками.
Потік подій називається регулярним, якщо в ньому події йдуть одна за одною через заздалегідь задані і певні проміжки часу. Такий потік є ідеальним і дуже рідко трапляється на практиці. Найчастіше зустрічаються нерегулярні потоки, що не володіють властивістю регулярності.
Потік подій називається стаціонарним, якщо ймовірність попадання будь-якого числа подій на проміжок часу залежить тільки від довжини цього проміжку і не залежить від того, як далеко розташований цей проміжок від початку часу. Стаціонарність потоку означає незалежність від часу його імовірнісних характеристик, зокрема інтенсивність такого потоку є середнє число подій в одиницю часу і залишається величиною постійної. Насправді зазвичай потоки можуть вважатися стаціонарними лише з деякому обмеженому проміжку часу. Зазвичай потік покупців, наприклад, у магазині суттєво змінюється протягом робочого дня. Однак можна виділити певні часові інтервали, всередині яких цей потік можна розглядати як стаціонарний, що має постійну інтенсивність.
Потік подій називається потоком без наслідки, якщо кількість подій, що потрапляють на один із довільно вибраних проміжків часу, не залежить від кількості подій, що потрапили на інший, також довільно вибраний проміжок за умови, що ці проміжки не перетинаються між собою. У потоці без наслідку події виникають у послідовні моменти часу незалежно друг від друга. Наприклад, потік покупців, що входять до магазину, можна вважати потоком без наслідків тому, що причини, що зумовили прихід кожного з них, не пов'язані з аналогічними причинами для інших покупців.
Потік подій називається ординарним, якщо ймовірність попадання на дуже малий відрізок часу одразу двох або більше подій нехтує в порівнянні з ймовірністю попадання тільки однієї події. В простому потоці події відбуваються поодинці, а не по два або більше разів. Якщо потік одночасно має властивості стаціонарності, ординарності та відсутність наслідку, то такий потік називається найпростішим (або пуассонівським) потоком подій. Математичний опис впливу такого потоку на системи виявляється найпростішим. Тому, найпростіший потік грає серед інших існуючих потоків особливу роль.
Розглянемо на осі часу певний проміжок часу t. Припустимо, можливість попадання випадкової події на цей проміжок p, а повне числоможливих подій - п. За наявності властивості ординарності потоку подій ймовірність р має бути досить малою величиною, а я - достатньо більшим числом, Оскільки розглядаються масові явища. У цих умовах для обчислення ймовірності попадання на проміжок часу t деякої кількості подій т можна скористатися формулою Пуассона:
P m, n = a m _e -a; (m=0,n),
де величина а = пр - середня кількість подій, що потрапляють на проміжок часу t, яке можна визначити через інтенсивність потоку подій Xнаступним чином: a = λ τ
Розмір інтенсивності потоку X є середнє число подій в одиницю часу. Між п і λ, р і τ є наступний зв'язок:
де t- весь проміжок часу, на якому розглядається дія потоку подій.
Необхідно визначити розподіл інтервалу часу Т між подіями у такому потоці. Оскільки це випадкова величиназнайдемо її функцію розподілу. Як відомо з теорії ймовірностей, інтегральна функція розподілу F(t) є ймовірність того, що величина T буде меншою за час t.
За умовою протягом часу T не має відбутися жодної події, а на інтервалі часу t має з'явитися хоча б одна подія. Ця можливість обчислюється з допомогою ймовірності протилежного події на проміжку часу (0; t), куди потрапило жодної події, тобто. m= 0, тоді
F(t)=1-P 0 =1-(a 0 *e -a)0!=1-e -Xt ,t≥0
Для малих ∆tможна отримати наближену формулу, одержувану заміною функції e - Xt , тільки двома членами розкладання в ряд за ступенями ∆t, тоді ймовірність попадання на малий проміжок часу ∆t хоча б однієї події становить
P(T<∆t)=1-e - λ t ≈1- ≈ λΔt
Щільність розподілу проміжку часу між двома послідовними подіями отримаємо, продиференціювавши F(t) за часом,
f(t)= λe- λ t ,t≥0
Користуючись отриманою функцією щільності розподілу, можна одержати числові характеристики випадкової величини Т: математичне очікування М(Т), дисперсію D(T) та середнє відхилення квадратне σ(Т).
М(Т)= λ ∞ ∫ 0 t*e - λt *dt=1/λ; D(T)=1/ λ 2 ; σ(T)=1/ λ .
Звідси можна зробити наступний висновок: середній інтервал часу Т між будь-якими двома сусідніми подіями в найпростішому потоці в середньому дорівнює 1/λ і його середнє квадратичне відхилення також дорівнює 1/λ, де, - інтенсивність потоку, тобто. середня кількість подій, що відбуваються в одиницю часу. Закон розподілу випадкової величини, що має такі властивості М(Т) = Т, називається показовим (або експоненціальним), а величина λ є параметром цього показового закону. Таким чином, для найпростішого потоку математичне очікування інтервалу часу між сусідніми подіями дорівнює його середньоквадратичному відхиленню. У цьому випадку ймовірність того, що кількість заявок, що надходять на обслуговування за проміжок часу t, дорівнює до визначається за законом Пуассона:
P k (t) = (λt) k / k! *e -λ t ,
де λ - інтенсивність надходження потоку заявок, середня кількість подій у СМО за одиницю часу, наприклад [чол/хв; руб./год; чеків/годину; докум./день; кг./година; т. / Рік].
Для такого потоку заявок час між двома сусідніми заявками Т розподілено експоненційно із щільністю ймовірності:
ƒ(t)= λe - λ t.
Випадковий час очікування в черзі початку обслуговування t оч також можна вважати розподіленим експоненційно:
ƒ (t оч) = V * e - v t оч,
де v - інтенсивність потоку проходу черги, що визначається середнім числом заявок, що проходять обслуговування в одиницю часу:
де Т оч – середній час очікування обслуговування у черзі.
Вихідний потік заявок пов'язаний з потоком обслуговування в каналі, де тривалість обслуговування t обс також випадковою величиною і підпорядковується в багатьох випадках показовому закону розподілу з щільністю ймовірності:
ƒ(t обс)=µ*е µ t обс,
де - інтенсивність потоку обслуговування, тобто. середня кількість заявок, що обслуговуються в одиницю часу:
µ=1/ t обс [чол/хв; руб./год; чеків/годину; докум./день; кг./година; т./рік] ,
де t обс – середній час обслуговування заявок.
Важливою характеристикою СМО, що поєднує показники λі µ є інтенсивність навантаження: ρ= λ/ µ, яка показує ступінь узгодження вхідного і вихідного потоків заявок каналу обслуговування і визначає стійкість системи масового обслуговування.
Крім поняття найпростішого потоку подій, часто доводиться користуватися поняттями потоків інших типів. Потік подій називається потоком Пальма, коли в цьому потоці проміжки часу між послідовними подіями T 1 , T 2 , ..., Т k ..., Т n є незалежними, однаково розподіленими, випадковими величинами, але на відміну від найпростішого потоку не обов'язково розподіленими за показовим законом. Найпростіший потік є окремим випадком потоку Пальма.
Важливим окремим випадком потоку Пальма є так званий потік Ерланга.
Цей потік виходить «проріджування» найпростішого потоку. Таке «проріджування» здійснюється шляхом відбору за певним правилом подій із найпростішого потоку.
Наприклад, умовившись враховувати тільки кожну другу подію з тих, що утворюють найпростіший потік, ми отримаємо потік Ерланга другого порядку. Якщо брати лише кожну третю подію, то утворюється потік Ерланга третього порядку тощо.
Можна отримати потоки Ерланга будь-якого порядку. Очевидно, найпростішим потіком є потік Ерланга першого порядку.
Будь-яке дослідження системи масового обслуговування починається з вивчення того, що необхідно обслуговувати, отже, з вивчення вхідного потоку заявок та його характеристик.
Оскільки моменти часу tі інтервали часу надходження заявок τ, потім тривалість операцій обслуговування t обс і час очікування в черзі t оч, а також довжина черги l оч - випадкові величини, то, отже, характеристики стану СМО мають імовірнісний характер, а для їх опису слідує застосовувати методи та моделі теорії масового обслуговування.
Перераховані вище характеристики τ, λ, L оч, Т оч, v, t обс, µ, р, Р k є найбільш загальними для СМО, які є зазвичай лише деякою частиною цільової функції, оскільки необхідно враховувати ще й показники комерційної діяльності.
1.3 Графи станів СМО
При аналізі випадкових процесів із дискретними станами та безперервним часом зручно користуватися варіантом схематичного зображення можливих станів СMO (рис. 6.2.1) у вигляді графа з розміткою його можливих фіксованих станів. Стани СМО зображуються зазвичай або прямокутниками, або кружками, а можливі напрями переходів з одного стану до іншого орієнтовані стрілками, що з'єднують ці стани. Наприклад, розмічений граф станів одноканальної системи випадкового процесу обслуговування у газетному кіоску наведено на рис. 1.3.
Рис. 1.3. Розмічений граф станів СМО
Система може бути в одному з трьох станів: S 0 -канал вільний, простоює, S 1 - канал зайнятий обслуговуванням, S 2 - канал зайнятий обслуговуванням і одна заявка в черзі. Перехід системи зі стану S 0 S l відбувається під впливом найпростішого потоку заявок інтенсивністю 01 а зі стану S l в стан S 0 систему переводить потік обслуговування з інтенсивністю 01 . Граф станів системи обслуговування із проставленими інтенсивностями потоків у стрілок називається розміченим. Оскільки перебування системи в тому чи іншому стані носить імовірнісний характер, то ймовірність: p i (t) того, що система перебуватиме в стані S i в момент часу t, називається ймовірністю i-го стану СМО і визначається числом заявок, що надійшли k на обслуговування.
Випадковий процес, що відбувається в системі, полягає в тому, що у випадкові моменти часу t 0 , t 1, t 2 ,..., t k ,..., t n система виявляється в тому чи іншому заздалегідь відомому дискретному стані послідовно. Така. випадкова послідовність подій називається Марківським ланцюгом, якщо для кожного кроку ймовірність переходу з одного стану S t в будь-який інший Sjне залежить від того, коли і як система перейшла в стан S t . Описується марківський ланцюг за допомогою ймовірності станів, причому вони утворюють повну групу подій, тому їхня сума дорівнює одиниці. Якщо ймовірність переходу не залежить від номера до, то марківський ланцюг називається однорідним. Знаючи початковий стан системи обслуговування, можна знайти ймовірності станів для будь-якого значення до числа заявок, що надійшли на обслуговування.
1.4 Випадкові процеси
Перехід СМО з одного стану в інший відбувається випадковим чином і є випадковим процесом. Робота СМО - випадковий процес із дискретними станами, оскільки його можливі стани у часі можна заздалегідь перерахувати. Причому перехід з одного стану в інший, відбувається стрибкоподібно, у випадкові моменти часу, тому він називається процесом з безперервним часом. Таким чином, робота СМО є випадковим процесом з дискретними станами і безперервним; часом. Наприклад, у процесі обслуговування оптових покупців на фірмі «Кристал» у Москві можна фіксувати заздалегідь усі можливі стани найпростіших. СМО, що входять у весь цикл, комерційного обслуговування від моменту укладання договору на поставку лікеро-горілчаної продукції, її оплати, оформлення документів, відпустки та отримання продукції, довантаження та вивезення зі складу готової продукції.
З безлічі різновидів випадкових процесів найбільшого поширення у комерційної діяльності набули такі процеси, котрим будь-якої миті часу характеристики процесу у майбутньому залежать лише з його стану зараз і залежать від передісторії - від минулого. Наприклад, можливість отримання із заводу «Кристал» лікеро-горілчаної продукції залежить від наявності її складі готової продукції, тобто. його стану в даний момент, і не залежить від того, коли і як отримували та відвозили у минулому цю продукцію інші покупці.
Такі випадкові процеси називаються процесами без наслідку, або марківськими, у яких за фіксованого теперішнього майбутнього стану СМО не залежить від минулого. Випадковий процес, що протікає в системі, називається марковським випадковим процесом, або «процесом без наслідку», якщо він має наступну властивість: для кожного моменту часу t 0 ймовірність будь-якого стану t > t 0 системи S i - в майбутньому (t>t Q ) залежить тільки від її стану в теперішньому (при t = t 0) і не залежить від того, коли і яким чином система прийшла до цього стану, тобто. від того, як розвивався процес у минулому.
Марківські випадкові процеси поділяються на два класи: процеси з дискретними та безперервними станами. Процес з дискретними станами виникає в системах, що володіють лише деякими фіксованими станами, між якими можливі стрибкоподібні переходи в деякі заздалегідь не відомі моменти часу. Розглянемо приклад процесу із дискретними станами. В офісі фірми є два телефони. Можливі такі стани цієї системи обслуговування: S o -телефони вільні; S l - один із телефонів зайнятий; S 2 - обидва телефони зайняті.
Процес, що протікає в цій системі, полягає в тому, що система випадково переходить стрибком з одного дискретного стану в інший.
Процеси з безперервними станами відрізняються безперервним плавним переходом з одного стану до іншого. Ці процеси більш характерні для технічних пристроїв, ніж для економічних об'єктів, де зазвичай лише приблизно можна говорити про безперервність процесу (наприклад, безперервне витрачання запасу товару), тоді як фактично процес має дискретний характер. Тому далі ми розглядатимемо лише процеси з дискретними станами.
Марківські випадкові процеси з дискретними станами у свою чергу поділяються на процеси з дискретним часом та процеси з безперервним часом. У першому випадку переходи з одного стану до іншого відбуваються лише у певні, заздалегідь фіксовані моменти часу, тоді як у проміжки між цими моментами система зберігає свій стан. У другому випадку перехід системи зі стану в стан може відбуватися у будь-який довільний момент часу.
Насправді процеси з безперервним часом зустрічаються значно частіше, оскільки переходи системи з одного стану до іншого зазвичай відбуваються над якісь фіксовані моменти часу, а будь-які випадкові моменти часу.
Для опису процесів з безперервним часом використовується модель у вигляді так званого марківського ланцюга з дискретними станами системи або безперервним марківським ланцюгом.
Глава II . Рівняння, що описують системи масового обслуговування
2.1 Рівняння Колмогорова
Розглянемо математичний опис марковського випадкового процесу з дискретними станами системи S o , S l , S 2 (див. рис. 6.2.1) та безперервним часом. Вважаємо, що всі переходи системи масового обслуговування зі стану S i стан Sj відбуваються під впливом найпростіших потоків подій з інтенсивностями λ ij , а зворотний перехід під впливом іншого потоку λ ij ,. Введемо позначення p i як ймовірність того, що в момент часу t система знаходиться у стані S i . Для будь-якого моменту часу tсправедливо записати нормувальну умову-сума ймовірностей усіх станів дорівнює 1:
Σp i (t) = p 0 (t) + p 1 (t) + p 2 (t) = 1
Проведемо аналіз системи в момент часу t, задавши мале збільшення часу Δt, і знайдемо ймовірність р 1 (t+ Δt) того, що система в момент часу (t+ Δt) перебуватиме в стані S 1 яке досягається різними варіантами:
а) система в момент t з ймовірністю p 1 (t) перебувала в стані S 1 і за мале збільшення часу Δt так і не перейшла в інший сусідній стан - ні в S 0, ні bS 2 . Вивести систему зі стану S 1 можна сумарним найпростішим потоком з інтенсивністю (λ 10 +λ 12), оскільки суперпозиція найпростіших потоків також є найпростішим потоком. На цій підставі ймовірність виходу зі стану S 1 за малий проміжок часу Δt приблизно дорівнює (λ 10 +λ 12)* Δt. Тоді ймовірність невиходу з цього стану дорівнює. Відповідно до цього ймовірність того, що система залишиться в стані Siна підставі теореми множення ймовірностей, дорівнює:
p 1 (t);
б)система знаходилася в сусідньому стані S o і за малий час Δt перейшла в стан S o Перехід системи відбувається під впливом потоку λ 01 з ймовірністю, що приблизно дорівнює λ 01 Δt
Імовірність того, що система перебуватиме в стані S 1 , у цьому варіанті дорівнює p o (t) 01 Δt;
в) система знаходилася в стані S 2 і за час Δt перейшла в стан S 1 під впливом потоку інтенсивністю 21 з ймовірністю, приблизно рівної 21 t. Імовірність того, що система перебуватиме в стані S 1 дорівнює p 2 (t) λ 21 Δt.
Застосовуючи теорему складання ймовірностей цих варіантів, отримаємо вираз:
p 2 (t+Δt) = p 1 (t) + po (t)λ 01 Δt+p 2 (t) λ 21 Δt ,
яке можна записати інакше:
p 2 (t+Δt)-p 1 (t)/ Δt= po (t)λ 01 + p 2 (t) λ 21 - p 1 (t) (λ 10 +λ 12) .
Переходячи до межі при Δt-> 0, наближені рівності перейдуть у точні, і тоді отримаємо похідну першого порядку
dp 2 /dt= p 0 λ 01 +p 2 λ 21 -p 1 (λ 10 +λ 12) ,
що є диференціальним рівнянням.
Проводячи міркування аналогічно для всіх інших станів системи, отримаємо систему диференціальних рівнянь, Які називаються рівняннями А.М. Колмогорова:
dp 0 /dt= p 1 λ 10 ,
dp 1 /dt= p 0 λ 01 +p 2 λ 21 -p 1 (λ 10 +λ 12) ,
dp 2 /dt= p 1 λ 12 +p 2 λ 21 .
Для складання рівнянь Колмогорова є загальні правила.
Рівняння Колмогорова дозволяють обчислити всі ймовірності станів СМО S i функції часу p i (t). Теоретично випадкових процесів показано, що й кількість станів системи звісно, та якщо з кожного можна перейти у будь-який інший стан, то існують граничні (фінальні) ймовірності станів, які вказують на середню відносну величину часу перебування системи, у цьому стані. Якщо гранична ймовірність стану S 0 - дорівнює p 0 = 0,2, то, отже, в середньому 20% часу, або 1/5 робочого часу, система знаходиться в стані S o . Наприклад, за відсутності заявок обслуговування до = 0, р 0 = 0,2,; отже, у середньому 2 год на день система перебуває у стані S o і простоює, якщо тривалість робочого дня становить 10 год.
Оскільки граничні ймовірності системи постійні, то замінивши в рівняннях Колмогорова відповідні похідні нульовими значеннями, отримаємо систему лінійних алгебраїчних рівнянь, що описують стаціонарний режим СМО Таку систему рівнянь складають за розміченим графом станів СМО за наступним правилам: ліворуч від знака рівності в рівнянні стоїть гранична ймовірність р i аналізованого стану Siпомножена на сумарну інтенсивність всіх потоків, що виводять (виходять стрілки) виданого стану S i систему, а праворуч від знака рівності - сума творів інтенсивності всіх потоків, що входять (входять стрілки) в стан Siсистему, на ймовірність тих станів, у тому числі ці потоки виходять. Для вирішення подібної системи необхідно додати ще одне рівняння, що визначає нормувальну умову, оскільки сума ймовірностей усіх станів СМО дорівнює 1: n
Наприклад, для СМО, що має розмічений граф із трьох станів S o , S 1 , S 2 рис. 6.2.1, система рівнянь Колмогорова, складена на основі викладеного правила, має такий вигляд:
Для стану S o → p 0 λ 01 = p 1 λ 10
Для стану S 1 →p 1 (λ 10 +λ 12) = p 0 λ 01 +p 2 λ 21
Для стану S 2 → p 2 λ 21 = p 1 λ 12
p 0 +p 1 +p 2 =1
dp 4 (t)/dt=34 p 3 (t) - 43 p 4 (t) ,
p 1 (t) + p 2 (t) + p 3 (t) + p 4 (t) = 1 .
До цих рівнянь слід додати ще початкові умови. Наприклад, якщо при t = 0 система S перебуває у стані S 1, то початкові умови можна записати так:
p 1 (0) = 1, p 2 (0) = p 3 (0) = p 4 (0) = 0 .
Переходи між станами СМО відбувається під впливом надходження заявок та їх обслуговування. Імовірність переходу у разі, якщо потік подій найпростіший, визначається ймовірністю появи події протягом Δt часу, тобто. величиною елемента ймовірності переходу λ ij Δt, де λ ij - інтенсивність потоку подій, що переводять систему зі стану i стан і (за відповідною стрілкою на графі станів).
Якщо всі потоки подій, що переводять систему з одного стану в інший, найпростіші, то процес, що протікає в системі, буде випадковим марківським процесом, тобто. процесом без наслідків. У цьому випадку поведінка системи досить проста, визначається, якщо відомі інтенсивність усіх цих найпростіших потоків подій. Наприклад, якщо в системі протікає марківський випадковий процес з безперервним часом, то, записавши систему рівнянь Колмогорова для ймовірностей станів та проінтегрувавши цю систему за заданих початкових умов, отримаємо всі ймовірності станів як функції часу:
p i (t), p 2 (t), ..., p n (t) .
У багатьох випадках на практиці виявляється, що ймовірності станів як функції часу поводяться таким чином, що існує
lim pi (t) = pi (i = 1,2, ..., n); t→∞
незалежно від виду початкових умов. І тут кажуть, що існують граничні ймовірності станів системи при t->∞ і у системі встановлюється певний граничний стаціонарний режим. При цьому система випадковим чином змінює свої стани, але кожен з цих станів здійснюється з деякою постійною ймовірністю, що визначається середнім часом перебування системи в кожному стані.
Обчислити граничні ймовірності стану р i можна, якщо в системі покласти усі похідні рівними 0, оскільки в рівняннях Колмогорова при t-> ∞ залежність від часу зникає. Тоді система диференціальних рівнянь перетворюється на систему Звичайних лінійних рівнянь алгебри, яка спільно з нормувальною умовою дозволяє обчислити всі граничні ймовірності станів.
2.2 Процеси «народження – загибелі»
Серед однорідних марківських процесів є клас випадкових процесів, що мають широке застосування при побудові математичних моделейу галузях демографії, біології, медицини (епідеміології), економіки, комерційної діяльності. Це звані процеси «народження - загибелі», марківські процеси зі стохастичними графами станів наступного виду:
| S 3 |
| kjlS n |
μ 0 μ 1 μ 3 μ 4 μ n-1
Рис. 2.1 Розмічений граф процесу «народження – загибелі»
Цей граф відтворює відому біологічну інтерпретацію: величина k відображає інтенсивність народження нового представника деякої популяції, наприклад, кроликів, причому поточний обсяг популяції дорівнює k; величина є інтенсивністю загибелі (продажу) одного представника цієї популяції, якщо поточний обсяг популяції дорівнює k. Зокрема, популяція може бути необмеженою (число n станів марківського процесу є нескінченним, але рахунковим), інтенсивність λ може дорівнювати нулю (популяція без можливості відродження), наприклад, при припиненні відтворення кроликів.
Для Марківського процесу «народження – загибелі», описаного стохастичним графом, наведеним на рис. 2.1, знайдемо фінальний розподіл. Користуючись правилами складання рівнянь для кінцевого числа n граничних ймовірностей стану системи S 1 , S 2 , S 3 ,… S k ,…, S n , складемо відповідні рівняння для кожного стану:
для стану S 0 -λ 0 p 0 = μ 0 p 1;
для стану S 1 -(λ 1 +μ 0)p 1 = λ 0 p 0 +μ 1 p 2 , яке з урахуванням попереднього рівняння для стану S 0 можна перетворити на вигляд λ 1 р 1 = μ 1 p 2 .
Аналогічно можна скласти рівняння для інших станів системи S 2 , S 3 ..., S k ..., S n . В результаті отримаємо наступну систему рівнянь:
Вирішуючи цю систему рівнянь, можна отримати вирази, що визначають фінальні стани системи масового обслуговування:
Слід зазначити, що формули визначення фінальних ймовірностей станів р 1 , р 2 , р 3 ,…, р n , входять доданки, що є складовоюсуми виразу, що визначає р0. У чисельниках цих доданків знаходяться твори всіх інтенсивностей, що стоять у стрілок графа станів, що ведуть ліворуч на право до стану S k , а знаменники являють собою твори всіх інтенсивностей, що стоять у стрілок, що ведуть праворуч на ліво до розглянутого стану S k , тобто . μ 0 , μ 1 , μ 2 , μ 3 , ... μ k . У зв'язку з цим запишемо ці моделі у більш компактному вигляді:
до=1,n
2.3 Економіко-математична постановка задач масового обслуговування
Правильна чи найбільш вдала економіко-математична постановка завдання значною мірою визначає корисність рекомендацій щодо вдосконалення систем масового обслуговування у комерційній діяльності.
У зв'язку з цим необхідно ретельно проводити спостереження за процесом у системі, пошуку та виявлення суттєвих зв'язків, формування проблеми, виділення мети, визначення показників та виділення економічних критеріївоцінки роботи СМО В цьому випадку як найбільш загальний, інтегральний показник можуть виступати витрати, з одного боку, СМО комерційної діяльності як обслуговуючої системи, а з іншого – витрати заявок, які можуть мати різну за своїм фізичним змістом природу.
Підвищення ефективності в будь-якій сфері діяльності К. Маркс зрештою розглядав як економію часу та вбачав у цьому один із найважливіших економічних законів. Він писав, що економія часу, як і планомірне розподіл робочого дня по різних галузях виробництва, залишається першим економічним законом з урахуванням колективного виробництва. Цей закон проявляється у всіх сферах суспільної діяльності.
Для товарів, зокрема і коштів, що у комерційну сферу, критерій ефективності пов'язані з часом і швидкістю звернення товарів хороших і визначає інтенсивність надходження коштів у банк. Час та швидкість обігу, будучи економічними показниками комерційної діяльності, характеризує ефективність використання коштів, вкладених у товарні запаси. Товарообіг відбиває середню швидкість реалізації середнього товарного запасу. Показники товарообігу та рівня запасів тісно пов'язані відомими моделями. Таким чином, можна простежити та встановити взаємозв'язок цих та інших показників комерційної діяльності з тимчасовими характеристиками.
Отже, ефективність роботи комерційного підприємства чи організації складається із сукупності часу виконання окремих операцій обслуговування, водночас для населення витрати часу включають час на дорогу, відвідування магазину, їдальні, кафе, ресторану, очікування на початок обслуговування, ознайомлення з меню, вибір продукції, розрахунок і т.д. Проведені дослідження структури витрат часу населення свідчить у тому, що його частина витрачається нераціонально. Зауважимо, що комерційна діяльністьзрештою спрямовано задоволення потреби людини. Тому зусилля моделювання СМО повинні включати аналіз витрат часу щодо кожної елементарної операції обслуговування. За допомогою відповідних методів слід створювати моделі зв'язку показників СМО. Це зумовлює необхідність найбільш загальні та відомі економічні показники, такі як товарообіг, прибуток, витрати обігу, рентабельність та інші, пов'язувати в економіко-математичних моделях з додатковою групою показників, що визначаються специфікою обслуговуючих систем і вносяться власне специфікою теорії масового обслуговування.
Наприклад, особливостями показників СМО з відмовами є: час очікування заявок у черзі Т оч =0, оскільки за своєю природою в таких системах існування черги неможливе, то L оч =0 і, отже, ймовірність її утворення Р оч =0. За кількістю заявок k визначаться режим роботи системи, її стан: при k=0 – простий каналів, при 1
Для СМО з необмеженим очікуванням характерно, що можливість обслуговування заявки Р обс =1, оскільки довжина черги і час очікування початку обслуговування не обмежені, тобто. формально L оч →∞ і Т оч →∞. У системах можливі такі режими роботи: при k=0 спостерігається простий канал обслуговування, при 1
У СМО з очікуванням з обмеженням на довжину черги, якщо кількість заявок у системі k=0, то спостерігається простий каналів, при 1
Отже, перелік характеристик систем масового обслуговування можна наступним чином: середній час обслуговування – t обс; середній час очікування у черзі – Т оч; середнє перебування У СМО - Т смо; середня довжина черги – L оч; середня кількість заявок в СМО-L смо; кількість каналів обслуговування – n; інтенсивність вхідного потоку заявок – λ; інтенсивність обслуговування – μ; інтенсивність навантаження – ρ; коефіцієнт навантаження -?; відносна пропускна здатність – Q; абсолютна пропускна здатність – А; частка часу простою в СМО - Р 0; частка обслужених заявок – Р обс; частка втрачених заявок - Р отк, середня кількість зайнятих каналів - n з; середня кількість вільних каналів - n св; коефіцієнт завантаження каналів - К з; середній час простою каналів - t ін.
Слід зазначити, що іноді досить використовувати до десяти основних показників, щоб виявити слабкі місця та розробити рекомендації щодо вдосконалення СМО.
Це часто пов'язано з вирішенням питань узгодженої роботи ланцюжка або сукупностей СМО.
Наприклад, у комерційній діяльності необхідно враховувати ще й економічні показники СМО: загальні витрати – С; витрати звернення – С ио, витрати споживання – З ип, Витрати обслуговування однієї заявки – З 1 , збитки, пов'язані з відходом заявки, - З у1 , Витрати експлуатацію каналу – С к, витрати простою каналу – С пр, капітальні вкладення – С кап, наведені річні витрати - С пр, поточні витрати - С тек, дохід СМО в одиницю часу - Д 1
У процесі постановки завдань необхідно розкрити взаємозв'язки показників СМО, які за своєю базовою приналежністю можна розділити на дві групи: перша пов'язана з витратами обігу С іо, які визначаються кількістю зайнятих обслуговуванням каналів, витратами на зміст СМО, інтенсивністю обслуговування, ступенем завантаження каналів, ефективністю їх використання, пропускною здатністю СМО та ін; друга група показників визначається витратами власне заявок З іп, що надходять на обслуговування, які утворюють вхідний потік, відчувають ефективність обслуговування і пов'язані з такими показниками, як довжина черги, час очікування обслуговування, можливість відмови в обслуговуванні, час перебування заявки в СМО та ін.
Ці групи показників суперечливі тому, що поліпшення показників однієї групи, наприклад, скорочення довжини черги чи часу очікування у черзі шляхом захоплення числа каналів обслуговування (офіціантів, кухарів, вантажників, касирів), пов'язані з погіршенням показників групи, оскільки це може призвести до збільшення часу простоїв каналів обслуговування, витрат за їх утримання тощо. У зв'язку з цим формалізації завдань обслуговування є цілком природним прагнення побудувати СМО таким чином, щоб встановити розумний компроміс між показниками власне заявок та повнотою використання можливостей системи. З цією метою необхідно вибрати узагальнений, інтегральний показник ефективності СМО, що включає одночасно претензії та можливості обох груп. Як такий показник може бути обраний критерій економічної ефективності, що включає як витрати звернення С іо, так і витрати заявок С іп, які матимуть оптимальне значення при мінімумі загальних витрат С. На цьому обґрунтуванні цільову функцію завдання можна записати так:
С= (З іо +З іп) →min
Оскільки витрати звернення включають витрати, пов'язані з експлуатацією СМО - С екс і простоєм каналів обслуговування - С пр, а витрати заявок включають втрати, пов'язані з відходом не обслужених заявок - С нз, і з перебуванням у черзі - С оч, тоді цільову функцію можна переписати з урахуванням цих показників таким чином:
С=((З пр n св +З екз n з)+С оч Р обс λ(Т оч +t обс)+С з Р отк λ)→min.
Залежно від поставленого завдання як варіювані, тобто керовані, показники можуть бути: кількість каналів обслуговування, організація каналів обслуговування (паралельно, послідовно, змішаним чином), дисципліна черги, пріоритетність обслуговування заявок, взаємодопомога між каналами та ін. Частина показників задачі фігурує як некеровані, які зазвичай є вихідними даними. В якості критерію ефективності цільової функції можуть бути так само товарообіг, прибуток, або дохід, наприклад, рентабельність, тоді оптимальні значення керованих показників СМО знаходяться очевидно, вже при максимізації, як у попередньому варіанті.
У деяких випадках слід користуватися іншим варіантом запису цільової функції:
С=(З екз n з +C пр (n-n з)+C відк *Р отк *λ+С сист * n з )→min
Як загальний критерій може бути обраний, наприклад, рівень культури обслуговування покупців на підприємствах, тоді цільова функція може бути представлена наступною моделлю:
К про =[(З пу *К у)+(З пв *К в)+(З пд *К д)+(З пз *К з)+(З по *К 0)+(З кт *К кт )]*До мп,
де З пу - значимість показника стійкості асортименту товарів;
К у – коефіцієнт стійкості асортименту товарів;
З пв - значимість показника впровадження прогресивних методів продажу товарів;
К – коефіцієнт впровадження прогресивних методів продажу товарів;
З пд - значимість показника додаткового обслуговування;
К д - Коефіцієнт додаткового обслуговування;
З пз - значимість показника завершеності покупки;
К з - коефіцієнт завершеності покупки;
З по - значимість показника витрат часу очікування обслуговування;
К о – показник витрат часу очікування обслуговування;
З кт - значимість показника якості праці колективу;
К кт – коефіцієнт якості праці колективу;
К мп – показник культури обслуговування на думку покупців;
Для аналізу СМО можна обирати інші критерії оцінки ефективності роботи СМО. Наприклад, як такий критерій для систем з відмовими можна вибирати ймовірність відмови Р отк, значення якого не перевищувало б заздалегідь заданої величини. Наприклад, вимога Р відк<0,1 означает, что не менее чем в 90% случаев система должна справляться с обслуживанием потока заявок при заданной интенсивности λ. Можно ограничить среднее время пребывания заявки в очереди или в системе. В качестве показателей, подлежащих определению, могут выступать: либо число каналов n при заданной интенсивности обслуживания μ, либо интенсивность μ при заданном числе каналов.
Після побудови цільової функції необхідно визначити умови вирішення завдання, знайти обмеження, встановити вихідні значення показників, виділити некеровані показники, побудувати або підібрати сукупність моделей взаємозв'язку всіх показників для аналізованого типу СМО, щоб зрештою знайти оптимальні значення керованих показників, наприклад кількість кухарів, офіціантів , касирів, вантажників, обсяги складських приміщень та ін.
Глава III . Моделі систем масового обслуговування
3.1 Одноканальна СМО з відмовами в обслуговуванні
Проведемо аналіз простої одноканальної СМО з відмовими в обслуговуванні, на яку надходить пуасонівський потік заявок з інтенсивністю λ, а обслуговування відбувається під дією пуассонівського потоку з інтенсивністю μ.
Роботу одноканальної СМО n=1 можна подати у вигляді розміченого графа станів (3.1).
Переходи СМО з одного стану S 0 до іншого S 1 відбуваються під дією вхідного потоку заявок з інтенсивністю λ, а зворотний перехід - під дією потоку обслуговування з інтенсивністю μ.
| S 0 |
| S 1 |
S0 – канал обслуговування вільний; S 1 - канал зайнятий обслуговуванням;
Рис. 3.1 Розмічений граф станів одноканальної СМО
Запишемо систему диференціальних рівнянь Колмогорова для ймовірностей стану за викладеними вище правилами:
Звідки отримаємо диференціальне рівняння визначення ймовірності р 0 (t) стану S 0:
Це рівняння можна вирішити за початкових умов у припущенні, що система в момент t=0 перебувала у стані S 0 тоді р 0 (0)=1, р 1 (0)=0.
У цьому випадку рішення диференціального рівняння дозволяє визначити ймовірність того, що канал вільний і не зайнятий обслуговуванням:
Тоді неважко отримати вираз для ймовірності визначення ймовірності зайнятості каналу:
Імовірність р 0 (t) зменшується з плином часу і в межах при t→∞ прагне величини
а ймовірність р 1 (t) водночас збільшується від 0, прагнучи межі при t→∞ до величини
Ці межі ймовірностей можуть бути отримані безпосередньо з рівнянь Колмогорова за умови
Функції р 0 (t) і р 1 (t) визначають перехідний процес в одноканальній СМО і описують процес експоненційного наближення СМО до свого граничного стану з постійною часу характерною для системи, що розглядається.
З достатньою для практики точністю вважатимуться, що перехідний процес у СМО закінчується протягом часу, що дорівнює 3τ.
Імовірність р 0 (t) визначає відносну пропускну здатність СМО, яка визначає частку заявок, що обслуговуються по відношенню до повного числа заявок, що надходять, в одиницю часу.
Дійсно, р 0 (t) є ймовірність того, що заявка, яка надійшла в момент t, буде прийнята до обслуговування. Усього в одиницю часу приходить у середньому λ заявок і з них обслуговується λр 0 заявок.
Тоді частка заявок, що обслуговуються, по відношенню до всього потоку заявок визначаться величиною
У межі при t→∞ практично вже при t>3τ значення відносної пропускної спроможності дорівнюватиме
Абсолютна пропускна здатність, що визначає кількість заявок, що обслуговуються в одиницю часу в межах при t→∞, дорівнює:
Відповідно частка заявок, які отримали відмову, становить у цих самих граничних умовах:
а загальна кількість необслуговуваних заявок дорівнює
Прикладами одноканальних СМО з відмовами в обслуговуванні є стіл замовлень у магазині, диспетчерська автотранспортного підприємства, контора складу, офіс управління комерційної фірми, з якими встановлюється зв'язок по телефону.
3.2 Багатоканальна СМО з відмовами в обслуговуванні
У комерційній діяльності прикладами багатоканальних СМО є офіси комерційних підприємств з кількома телефонними каналами, безкоштовна довідкова служба з наявності в автомобільних магазинах найдешевших автомобілів у Москві має 7 телефонних номерів, а додзвонитися та отримати довідку, як відомо, дуже важко.
Отже, авто магазини втрачають клієнтів, можливість збільшити кількість проданих автомобілів та виручку від продажів, товарообіг, прибуток.
Туристичні фірми з продажу путівок мають два, три, чотири та більше каналів, як, наприклад, фірма Express-Line.
Розглянемо багатоканальну СМО з відмовами в обслуговуванні на рис. 3.2 на вхід якої надходить пуасонівський потік заявок з інтенсивністю λ.
| S 0 |
| S 1 |
| S k |
| S n |
μ 2μkμ (k+1)μ nμ
Рис. 3.2. Розмічений граф станів багатоканальної СМО із відмовами
Потік обслуговування у кожному каналі має інтенсивність μ. За кількістю заявок СМО визначаються її стани S k представлені у вигляді розміченого графа:
S 0 - всі канали вільні k = 0,
S 1 – зайнятий лише один канал, k=1,
S 2 – зайняті лише два канали, k=2,
S k – зайняті до каналів,
S n – зайняті все n каналів, k = n.
Стани багатоканальної СМО змінюються стрибкоподібно у випадкові моменти часу. Перехід з одного стану, наприклад S 0 S 1 , відбувається під впливом вхідного потоку заявок з інтенсивністю λ, а назад - під впливом потоку обслуговування заявок з інтенсивністю μ. Для переходу системи зі стану S k в S k -1 байдуже, який саме з каналів звільнитися, тому потік подій, що переводить СМО, має інтенсивність kμ, отже, потік подій, що переводить систему з S n в S n -1 має інтенсивність nμ . Так формулюється класичне завдання Ерланга, названа на ім'я датського інженера - математика-засновника теорії масового обслуговування.
Випадковий процес, що протікає в СМО, є окремим випадком процесу «народження- загибелі» і описується системою диференціальних рівнянь Ерланга, які дозволяють отримати вирази для граничних ймовірностей стану аналізованої системи, звані формулами Ерланга:
.
Обчисливши всі ймовірності станів n – канальної СМО з відмовами р 0, р 1, р 2, …, р k, …, р n, можна визначити характеристики системи обслуговування.
Імовірність відмови в обслуговуванні визначається ймовірністю того, що заявка на обслуговування, що надійшла, знайде всі n каналів зайнятими, система перебуватиме в стані S n:
k=n.
У системах з відмовами події відмови та обслуговування становлять повну групу подій, тому
Р отк + Р обс = 1
На цій підставі відносна пропускна здатність визначається за формулою
Q = P обс = 1-Р отк = 1-Р n
Абсолютну пропускну здатність СМО можна визначити за формулою
Імовірність обслуговування, або частка обслужених заявок, визначає відносну пропускну здатність СМО, яка може бути визначена і за іншою формулою:
З цього виразу можна визначити середню кількість заявок, що знаходяться під обслуговуванням, або, що саме, середня кількість зайнятих обслуговуванням каналів
Коефіцієнт зайнятості каналів обслуговуванням визначаться ставленням середньої кількості зайнятих каналів до їх загального числа
Імовірність зайнятості каналів обслуговуванням, яка враховує середній час зайнятості t зан і простою t пр каналів, визначається так:
З цього виразу можна визначити середній час простою каналів
Середній час перебування заявки в системі в режимі, що встановився, визначаться формулою Літтла.
Т см = n з /λ.
3.3 Модель багатофазної системи обслуговування туристів
У реальному житті система обслуговування туристів виглядає значно складніше, тому необхідно деталізувати постановку завдання з огляду на запити, вимоги як з боку клієнтів, так і турфірми.
Для підвищення ефективності роботи турфірми необхідно змоделювати загалом поведінку потенційного клієнта від початку операції до її завершення. Структура взаємозв'язку основних систем масового обслуговування фактично складається із СМО різного виду (рис. 3.3).
Пошук Вибір Вибір Рішення
|
референт |
Оплата Переліт Вихід
Рис. 3.3 Модель багатофазної системи обслуговування туристів
Проблема з позиції масового обслуговування туристів, які їдуть на відпочинок, полягає у визначенні точного місця відпочинку (туру), адекватного вимогам претендента, що відповідає його здоров'ю та фінансовим можливостям та уявленням про відпочинок загалом. У цьому йому можуть сприяти турфірми, пошук яких здійснюється зазвичай з рекламних повідомлень СМО, потім після вибору фірми відбувається отримання консультацій по телефону СМО т, після задовільного розмови приїзд в турфірму і отримання більш детальних консультацій особисто з референтом, потім оплата путівки та отримання обслуговування від авіакомпанії по перельоту СМО а та в кінцевому рахунку обслуговування в готелі СМ0 0 . Подальший розвиток рекомендацій щодо покращення роботи СМО фірми пов'язаний із зміною професійного змісту переговорів із клієнтами по телефону. Для цього необхідно поглибити аналіз, пов'язаний з деталізацією діалогу референта з клієнтами, оскільки далеко не кожен телефонний переговор призводить до укладення договору на придбання путівки. Проведення формалізації завдання обслуговування вказало необхідність формування повного (необхідного і достатнього) переліку характеристик та його точних значень предмета комерційної угоди. Потім проводяться ранжування цих характеристик, наприклад методом парних порівнянь, та розташування в діалозі за ступенем їх значущості, наприклад: пора року (зима), місяць (січень), клімат (сухий), температура повітря (+25 ° С), вологість (40 %), географічне місце (ближче до екватора), час авіаперельоту (до 5 годин), трансферт, країна (Єгипет), місто (Хургада), море (Червоне), температура води в морі (+23°С), ранг готелю ( 4 зірки, працюючий кондиціонер, гарантія наявності шампуню в номері), віддаленість від моря (до 300 м), віддаленість від магазинів (поруч), віддаленість від дискотек та інших джерел шуму (далі, тиша протягом сну в готелі), харчування (шведський) стіл - сніданок, вечеря, частота зміни меню за тиждень), готелі (Princes, Marlin-In, Hour-Palace), екскурсії (Каїр, Луксор, коралові острови, підводне плавання), розважальні шоу, спортивні ігри, ціна путівки, форма оплати , утримання страховки, що брати з собою, що купити на місці, гарантії, штрафні санкції
Є ще один дуже суттєвий показник, вигідний клієнту, встановити який пропонується самостійно в'їдливому читачеві. Потім можна, використовуючи метод опарного порівняння перерахованих характеристик х i , сформувати матрицю п х п порівняння, елементи якої заповнюються послідовно за рядками за наступним правилом:
0, якщо характеристика менш значуща,
а ij = 1, якщо характеристика рівнозначна,
2 якщо характеристика домінує.
Після цього визначаються значення сум оцінок за кожним показником рядка S i =∑a ij , вага кожної характеристики M i = S i /n 2 і відповідно інтегральний критерій, на основі якого можна провести вибір турфірми, туру або готелю, за формулою
F = ∑ M i * x i - max.
З метою виключення можливих помилок у цій процедурі вводять, наприклад, 5-бальну шкалу оцінок з градацією характеристик Б i (х i) за принципом гірше (Б i = 1 бал) – краще (Б i = 5 балів). Наприклад, чим дорожчий тур, тим гірше, чим він дешевший, тим краще. На цій підставі цільова функція матиме інший вигляд:
F b = ∑ M i * Б i * x i -> max.
Таким чином, можна на основі застосування математичних методів і моделей, використовуючи переваги формалізації, точніше і об'єктивніше сформулювати постановку завдань та значно покращити показники СМО у комерційній діяльності для досягнення поставленої мети.
3.4 Одноканальна СМО з обмеженою довжиною черги
У комерційній діяльності найчастіше зустрічаються СМО з очікуванням (чергою).
Розглянемо просту одноканальну СМО з обмеженою чергою, у якій кількість місць у черзі т - фіксована величина. Отже, заявка, що надійшла в той момент, коли всі місця в черзі зайняті, не приймається до обслуговування, не встає в чергу і залишає систему.
Граф цієї СМО подано на рис. 3.4 та збігається з графом рис. 2.1 описує процес «народження-загибелі», з тією відмінністю, що за наявності тільки одного каналу.
|
|
|
|
|
μ μμμ... μ
Рис. 3.4. Розмічений граф процесу «народження – загибелі» обслуговування всі інтенсивності потоків обслуговування рівні
Стану СМО можна представити так:
S 0 - канал обслуговування вільний,
S, - канал обслуговування зайнятий, але черги немає,
S 2 - канал обслуговування зайнятий, у черзі стоїть одна заявка,
S 3 - канал обслуговування зайнятий, у черзі стоять дві заявки,
S m +1 - канал обслуговування зайнятий, у черзі всі місця зайняті, будь-яка наступна заявка отримує відмову.
Для опису випадкового процесу СМО можна скористатися викладеними раніше правилами та формулами. Напишемо вирази, що визначають граничні ймовірності станів:
p 1 = ρ * ρ про
p 2 = ρ 2 * ρ 0
p k = ρ k * ρ 0
P m+1 = p m=1 * ρ 0
p 0 = -1
Вираз для р 0 можна в іншому випадку записати простіше, користуючись тим, що в знаменнику стоїть геометрична прогресія щодо р, тоді після відповідних перетворень отримуємо:
ρ= (1- ρ )
Ця формула справедлива всім р, відмінних від 1, якщо р = 1, то р 0 = 1/(т + 2), проте інші ймовірності також дорівнюють 1/(т + 2). Якщо припустити т = 0, ми переходимо від розгляду одноканальної СМО з очікуванням до вже розглянутої одноканальної СМО з відмовами в обслуговуванні. Справді, вираз для граничної ймовірності р 0 у разі т = 0 має вигляд:
p про = μ / (λ + μ)
І у разі λ = μ має величину р 0 = 1/2.
Визначимо основні характеристики одноканальної СМО з очікуванням: відносну та абсолютну пропускну здатність, ймовірність відмови, а також середню довжину черги та середній час очікування заявки у черзі.
Заявка отримує відмову, якщо вона надходить у момент часу, коли СМО вже перебуває в стані S m +1 і, отже, всі місця в черзі так зайняті і один канал обслуговує.
Стан S m +1:
P отк = p m +1 = ρ m +1 * p 0
Відносна пропускна здатність, або частка заявок, що обслуговуються, що надходять в одиницю часу, визначається виразом
Q = 1 - p отк = 1 - ρ m+1 * p 0
абсолютна пропускна здатність дорівнює:
Середня кількість заявок L оч стоять у черзі на обслуговування, визначається математичним очікуванням випадкової величини до - числа заявок, що стоять у черзі
випадкова величина приймає такі лише цілочисельні значення:
1 - у черзі стоїть одна заявка,
2 - у черзі дві заявки,
т-в черзі всі місця зайняті
Імовірності цих значень визначаються відповідними ймовірностями станів, починаючи зі стану S2. Закон розподілу дискретної випадкової величини до зображується так:
| k | 1 | 2 | m |
| p i | p 2 | p 3 | p m+1 |
Математичне очікування цієї випадкової величини дорівнює:
L оч = 1 * p 2 +2 * p 3 + ... + m * p m +1
Загалом при p ≠1 цю суму можна перетворити, користуючись моделями геометричної прогресії, до зручнішого вигляду:
L оч = p 2 * 1-pm* (m-m*p+1)* p 0
В окремому випадку при р = 1, коли всі ймовірності p k виявляються рівними, можна скористатися виразом для суми членів числового ряду
1+2+3+ m = m ( m +1)
Тоді отримаємо формулу
L' оч = m(m+1)* p 0 = m(m+1)(p = 1).
Застосовуючи аналогічні міркування та перетворення, можна показати, що середній час очікування обслуговування заявки а черги визначається формулами Літтла
Т оч = L оч /А (при р ≠ 1) і Т 1 оч = L' оч /А (при р = 1).
Такий результат, коли виявляється, що Т оч ~ 1/λ, може здатися дивним: зі збільшенням інтенсивності потоку заявок нібито має зростати довжина черги та зменшується середній час очікування. Однак слід мати на увазі, що, по-перше, величина L оч є функцією від λ і μ і, по-друге, СМО має обмежену довжину черги не більше mзаявок.
Заявка, що надійшла до СМО в момент часу, коли всі канали зайняті, отримує відмову, і, отже, час її «очікування» в СМО дорівнює нулю. Це призводить у загальному випадку (при р ≠ 1) до зменшення Т оч ростом λ, оскільки частка таких заявок із зростанням λ збільшується.
Якщо відмовитися від обмеження довжину черги, тобто. спрямувати m-> →∞, то випадки р< 1 и р ≥1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду
p k = р k * (1 - р)
При досить великому ймовірність p k прагне нуля. Тому відносна пропускна здатність буде Q= 1, а абсолютна пропускна здатність стане рівною А - Q - λ отже, обслуговуються всі заявки, причому середня довжина черги виявиться рівною:
L оч = p 2 1-p
а середній час очікування за формулою Літтла
Т оч = L оч /А
У межі р<< 1 получаем Т оч = ρ / μт.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р ≥ 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t → ∞). Предельные вероятности состояний поэтому не могут быть определены: при Q= 1 они равны нулю. Фактически СМО не выполняет своих функций, поскольку она не в состоянии обслужить все поступающие заявки. Нетрудно определить, что доля обслуживаемых заявок и абсолютная пропускная способность соответственно составляют в среднем ρ и μ, однако неограниченное увеличение очереди, а следовательно, и времени ожидания в ней приводит к тому, что через некоторое время заявки начинают накапливаться в очереди на неограниченно долгое время.
Як одну з характеристик СМО використовують середній час Т СМО перебування заявки в СМО, що включає середній час перебування в черзі та середній час обслуговування. Ця величина обчислюється за формулами Літтла: якщо довжина черги обмежена - середня кількість заявок, що знаходяться в черзі, дорівнює:
L см= m +1 ;2
Т смо = L смо;при p ≠1
Тоді середній час перебування заявки в системі масового обслуговування (як у черзі, так і під обслуговуванням) дорівнює:
Т смо = m +1 при p ≠1 2μ
3.5 Одноканальна СМО з необмеженою чергою
У комерційній діяльності як одноканальна СМО з необмеженим очікуванням є, наприклад, комерційний директор, оскільки він, як правило, змушений виконувати обслуговування заявок різної природи: документи, телефонні переговори, зустрічі та бесіди з підлеглими, представниками податкової інспекції, міліції, товарознавцями, маркетологами, постачальниками продукції та вирішувати завдання у товарно-фінансовій сфері з високим ступенем фінансової відповідальності, що пов'язано з обов'язковим виконанням запитів, які очікують іноді нетерпляче виконання своїх вимог, а помилки неправильного обслуговування, як правило, є економічно вельми відчутними.
У той самий час товари, завезені на продаж (обслуговування), перебуваючи складі, утворюють чергу обслуговування (продаж).
Довжина черги становить кількість товарів, призначених для продажу. У цій ситуації продавці виступають у ролі каналів, які обслуговують товари. Якщо кількість товарів, призначених для продажу, велика, то в цьому випадку ми маємо справу з типовим випадком СМО з очікуванням.
Розглянемо найпростішу одноканальну СМО з очікуванням обслуговування, яку надходить пуасонівський потік заявок з інтенсивністю λ і інтенсивністю обслуговування µ.
Причому заявка, що надійшла в момент, коли канал зайнятий обслуговуванням, ставиться в чергу та чекає на обслуговування.
Розмічений граф станів такої системи наведено на рис. 3.5
Кількість можливих станів її нескінченно:
Канал вільний, черги немає, ;
Канал зайнятий обслуговуванням, черги немає, ;
Канал зайнятий, одна заявка у черзі, ;
Канал зайнятий, заявка у черзі.
Моделі оцінки ймовірності станів СМО з необмеженою чергою можна отримати з формул, виділених для СМО з необмеженою чергою шляхом переходу до межі при m→∞:
Рис. 3.5 Граф станів одноканальної СМО з необмеженою чергою.
Слід зауважити, що для СМО з обмеженою довжиною черги у формулі
має місце геометрична прогресія з першим членом 1 і знаменником. Така послідовність є сумою нескінченного числа членів при . Ця сума сходиться, якщо прогресія, що нескінченно зменшується при , що визначає режим роботи СМО, що з'явився, з при чергу при з часом може зростати до нескінченності.
Оскільки в аналізованій СМО обмеження на довжину черги відсутня, то будь-яка заявка може бути обслужена, тому , отже, відносна пропускна здатність , відповідно , а абсолютна пропускна здатність
Імовірність перебування у черзі k заявок дорівнює:
;
Середня кількість заявок у черзі –
Середня кількість заявок у системі –
;
Середній час перебування заявки у системі –
;
Середній час перебування заявки із системою –
.
Якщо в одноканальній СМО з очікуванням інтенсивність надходження заявок більша за інтенсивність обслуговування , то черга буде постійно збільшуватися. У зв'язку з цим найбільший інтерес представляє аналіз стійких СМО, що працюють у стаціонарному режимі.
3.6 Багатоканальна СМО з обмеженою довжиною черги
Розглянемо багатоканальну СМО, на вхід якої надходить пуасонівський потік заявок з інтенсивністю, а інтенсивність обслуговування кожного каналу становить максимально можливе число місць у черзі обмежене величиною m. Дискретні стани СМО визначаються кількістю заявок, які надійшли до системи, які можна записати.
Всі канали вільні;
Зайнятий лише один канал (будь-який), ;
Зайняті лише два канали (будь-яких), ;
Зайняті всі канали, .
Поки СМО перебуває у будь-якому з цих станів, черги немає. Після того, як зайняті всі канали обслуговування, наступні заявки утворюють чергу, тим самим, визначаючи подальший стан системи:
Зайняті всі канали і одна заявка стоїть у черзі,
Зайняті всі канали і дві заявки стоять у черзі,
Зайняті всі канали і всі місця в черзі,
Граф станів n-канальної СМО із чергою, обмеженою m місцями на рис.3.6
Рис. 3.6 Граф станів n-канальної СМО з обмеженням на довжину черги m
Перехід СМО в стан з великими номерами визначається потоком заявок, що надходять з інтенсивністю , тоді як за умовою в обслуговуванні цих заявок беруть участь однакових каналів з інтенсивністю потоку обслуговування рівного для кожного каналу. При цьому повна інтенсивність потоку обслуговування зростає з підключенням нових каналів до такого стану , коли всі n каналів виявляться зайнятими. З появою черги інтенсивність обслуговування більш збільшується, оскільки вона досягла максимального значення, рівного .
Запишемо вирази для граничних ймовірностей станів:
Вираз можна перетворити, використовуючи формулу геометричної прогресії для суми членів зі знаменником :
Освіта черги можливе, коли заявка, що знову надійшла, застане в системі не менше вимог, тобто. коли у системі буде перебувати вимог. Ці події незалежні, тому ймовірність того, що всі канали зайняті, дорівнює сумі відповідних ймовірностей.
Імовірність відмови в обслуговуванні настає тоді, коли всі канали і всі місця в черзі зайняті:
Відносна пропускна здатність дорівнюватиме:
Абсолютна пропускна спроможність –
Середня кількість зайнятих каналів –
Середня кількість каналів, що простоюють
Коефіцієнт зайнятості (використання) каналів –
Коефіцієнт простою каналів –
Середня кількість заявок, що знаходяться у чергах –
Якщо , ця формула набуває іншого вигляду –
Середній час очікування у черзі визначається формулами Літтла –
Середній час перебування заявки в СМО, як і для одноканальної СМО, більший за середній час очікування в черзі на середній час обслуговування, що дорівнює , оскільки заявка завжди обслуговується тільки одним каналом:
3.7 Багатоканальна СМО з необмеженою чергою
Розглянемо багатоканальну СМО з очікуванням та необмеженою довжиною черги, на яку надходить потік заявок з інтенсивністю та яка має інтенсивність обслуговування кожного каналу. Розмічений граф станів представлений на рис 3.7. Він має нескінченну кількість станів:
S - всі канали вільні, k = 0;
S - зайнятий один канал, інші вільні, k = 1;
S - зайняті два канали, інші вільні, k = 2;
S - зайняті всі n каналів, k = n, черги немає;
S - зайняті всі n каналів, одна заявка у черзі, k=n+1,
S - зайняті всі n каналів, r заявок у черзі, k=n+r,
Ймовірність станів отримаємо з формул для багатоканальної СМО з обмеженою чергою при переході до межі при m. Слід зазначити, що сума геометричної прогресії у виразі для p розходиться при рівні завантаження p/n>1, черга нескінченно зростатиме, а при p/n<1 ряд сходится, что определяет установившийся стационарный режим работы СМО.
Черги ні
| … | … |
Рис.3.7 Розмічений граф станів багатоканальної СМО
з необмеженою чергою
для якого і визначимо вирази для граничних ймовірностей станів:
Оскільки відмови в обслуговуванні в таких системах не може бути, то характеристики пропускної спроможності дорівнюють:
середня кількість заявок у черзі –
середній час очікування у черзі –
середня кількість заявок до СМО –
Імовірність того, що СМО перебуває в стані, коли немає заявок і не зайнято жодного каналу, визначається виразом
Ця ймовірність визначає середню частку простою каналу обслуговування. Імовірність зайнятості обслуговуванням заявок –
На цій підставі можна визначити ймовірність, або час зайнятості всіх каналів обслуговуванням
Якщо всі канали вже зайняті обслуговуванням, то ймовірність стану визначається виразом
Імовірність опинитися у черзі дорівнює ймовірності застати всі канали вже зайнятими обслуговуванням
Середня кількість заявок, що перебувають у черзі та чекають на обслуговування, дорівнює:
Середній час очікування заявки у черзі за формулою Літтла: і в системі
середня кількість зайнятих каналів обслуговуванням:
середня кількість вільних каналів:
коефіцієнт зайнятості каналів обслуговуванням:
Важливо зауважити, що параметр характеризує ступінь узгодження вхідного потоку, наприклад, покупців у магазині з інтенсивністю потоку обслуговування. Якщо ж в системі будуть зростати середня довжина черги і середній час очікування покупцями початку обслуговування і, отже, СМО працюватиме нестійко.
3.8 Аналіз системи масового обслуговування супермаркету
Однією з важливих завдань комерційної діяльності є раціональна організація торгово-технологічного процесу масового обслуговування, наприклад, в універсамі. Зокрема визначення потужності касового вузла торговельного підприємства є непростим завданням. Такі економіко-організаційні показники, як навантаження товарообігу на 1м 2 торгової площі, пропускна спроможність підприємства, час перебування покупців у магазині, а також показники рівня технологічного рішення торгового залу: співвідношення площ зон самообслуговування та розрахункового вузла, коефіцієнти настановної та виставкової площ багато в чому визначаються пропускною спроможністю касового вузла. В цьому випадку пропускну здатність двох зон (фаз) обслуговування: зони самообслуговування та зони розрахункового вузла (рис.4.1).
| СМО | СМО |
Інтенсивність вхідного потоку покупців;
Інтенсивність приходу покупців зони самообслуговування;
Інтенсивність приходу покупців у розрахунковий вузол;
Інтенсивність потоку обслуговування.
Рис.4.1. Модель двофазної СМО торгового залу універсаму
Основна функція розрахункового вузла полягає у забезпеченні високої пропускної спроможності покупців у торговому залі та створенні комфортного обслуговування покупців. Чинники, що впливають пропускну здатність розрахункового вузла, можна розділити на дві групи:
1) економіко-організаційні фактори: система матеріальної відповідальності в універсамі; середня вартість та структура однієї покупки;
2) організаційну структуру касового вузла;
3) техніко-технологічні фактори: застосовувані типи касових апаратів та касових кабін; технологія обслуговування покупців, що застосовується контролером-касиром; відповідність потужності касового вузла інтенсивності купівельних потоків.
З перелічених груп чинників найбільше впливають організаційне побудова касового вузла і відповідність потужності касового вузла інтенсивності купівельних потоків.
Розглянемо обидві фази системи обслуговування:
1) вибір покупцями товарів у зоні самообслуговування;
2) обслуговування покупців у зоні розрахункового вузла. Вхідний потік покупців потрапляє у фазу самообслуговування, і покупець самостійно відбирає необхідні йому товарні одиниці, формуючи в єдину покупку. Причому час цієї фази залежить від цього, як взаєморозміщені товарні зони, який фронт вони мають, скільки часу витрачає покупець вибір конкретного товару, яка структура купівлі тощо.
Потік покупців, що виходить, з зони самообслуговування одночасно є вхідним потоком в зону касового вузла, який послідовно включає очікування покупця в черзі і потім обслуговування його контролером-касиром. Касовий вузол можна розглядати як систему обслуговування із втратами або як систему обслуговування з очікуванням.
Однак ні перша, ні друга розглянуті системи не дозволяють реально описати процес обслуговування в касовому вузлі універсаму з наступних причин:
у першому варіанті касовий вузол, потужність якого буде розрахована на систему із втратами, вимагає значних як капітальних вкладень, так і поточних витрат на утримання контролерів-касирів;
у другому варіанті касовий вузол, потужність якого буде розрахована на систему з очікуваннями, призводить до великих витрат часу покупців в очікуванні обслуговування. При цьому в години пік зона розрахункового вузла переповнюється і черга покупців перетікає в зону самообслуговування, що порушує нормальні умови для вибору товару іншими покупцями.
У зв'язку з цим доцільно розглядати другу фазу обслуговування як систему з обмеженою чергою, проміжну між системою з очікуванням та системою з втратами. При цьому передбачається, що одночасно в системі можуть перебувати не більше L, причому L=n+m, де n-кількість клієнтів, що обслуговуються в касах, m-кількість покупців, що стоять у черзі, причому будь-яка m+1- заявка залишає систему необслуженою.
Ця умова дозволяє, з одного боку, обмежити площу зони розрахункового вузла з урахуванням максимально допустимої довжини черги, з другого – запровадити обмеження тимчасово очікування покупцями обслуговування у касовому вузлі, тобто. враховувати витрати споживання покупців.
Правомірність постановки завдання у такому вигляді підтверджується проведеними обстеженнями потоків покупців в універсамах, результати яких наведено в табл. 4.1, аналіз яких виявив тісний зв'язок між середньою довгою чергою в касовому вузлі та кількістю покупців, які не здійснили покупок.
| Години роботи | День тижня | ||||||||
| п'ятниця | субота | неділя | |||||||
черга, |
кількість покупців без покупок |
черга, |
кількість покупців без покупок |
черга, |
кількість покупців без покупок |
||||
| чол. | % | чол. | % | чол. | % | ||||
| з 9 до 10 | 2 | 38 | 5 | 5 | 60 | 5,4 | 7 | 64 | 4,2 |
| з 10 до 11 | 3 | 44 | 5,3 | 5 | 67 | 5 | 6 | 62 | 3,7 |
| з 11 до 12 | 3 | 54 | 6,5 | 4 | 60 | 5,8 | 7 | 121 | 8,8 |
| з 12 до 13 | 2 | 43 | 4,9 | 4 | 63 | 5,5 | 8 | 156 | 10 |
| з 14 до 15 | 2 | 48 | 5,5 | 6 | 79 | 6,7 | 7 | 125 | 6,5 |
| з 15 до 16 | 3 | 61 | 7,3 | 6 | 97 | 6,4 | 5 | 85 | 7,2 |
| з 16 до 17 | 4 | 77 | 7,1 | 8 | 140 | 9,7 | 5 | 76 | 6 |
| з 17 до 18 | 5 | 91 | 6,8 | 7 | 92 | 8,4 | 4 | 83 | 7,2 |
| з 18 до 19 | 5 | 130 | 7,3 | 6 | 88 | 5,9 | 7 | 132 | 8 |
| з 19 до 20 | 6 | 105 | 7,6 | 6 | 77 | 6 | |||
| з 20 до 21 | 6 | 58 | 7 | 5 | 39 | 4,4 | |||
| Разом | 749 | 6,5 | 862 | 6,3 | 904 | 4,5 | |||
В організації роботи касового вузла універсаму є ще одна важлива особливість, яка значно впливає на його пропускну здатність: наявність експрес-кас (однієї-двох покупок). Вивчення структури потоку покупців в універсамах на кшталт касового обслуговування показує, що потік оборот становить 12,9% (табл. 4.2).
| Дні тижня | Потоки покупців | Товарообіг | ||||
| всього | по експрес-касам | % до денного потоку | всього | по експрес-касам | % до денного товарообігу | |
| Літній період | ||||||
| Понеділок | 11182 | 3856 | 34,5 | 39669,2 | 3128,39 | 7,9 |
| Вівторок | 10207 | 1627 | 15,9 | 38526,6 | 1842,25 | 4,8 |
| Середа | 10175 | 2435 | 24 | 33945 | 2047,37 | 6 |
| Четвер | 10318 | 2202 | 21,3 | 36355,6 | 1778,9 | 4,9 |
| П'ятниця | 11377 | 2469 | 21,7 | 43250,9 | 5572,46 | 12,9 |
| Субота | 10962 | 1561 | 14,2 | 39873 | 1307,62 | 3,3 |
| Неділя | 10894 | 2043 | 18,8 | 35237,6 | 1883,38 | 5,1 |
| Зимовий період | ||||||
| Понеділок | 10269 | 1857 | 18,1 | 37121,6 | 2429,73 | 6,5 |
| Вівторок | 10784 | 1665 | 15,4 | 38460,9 | 1950,41 | 5,1 |
| Середа | 11167 | 3729 | 33,4 | 39440,3 | 4912,99 | 12,49,4 |
| Четвер | 11521 | 2451 | 21,3 | 40000,7 | 3764,58 | 9,4 |
| П'ятниця | 11485 | 1878 | 16,4 | 43669,5 | 2900,73 | 6,6 |
| Субота | 13689 | 2498 | 18,2 | 52336,9 | 4752,77 | 9,1 |
| Неділя | 13436 | 4471 | 33,3 | 47679,9 | 6051,93 | 12,7 |
Для остаточного побудова математичної моделі процесу обслуговування з урахуванням перелічених вище факторів необхідно визначити функції розподілу випадкових величин, а також випадкові процеси, що описують вхідні та вихідні потоки покупців:
1) функцію розподілу часу покупців на вибір товарів у зоні самообслуговування;
2) функцію розподілу часу роботи контролера-касира для звичайних кас та експрес-кас;
3) випадковий процес, що описує вхідний потік покупців у першу фазу обслуговування;
4) випадковий процес, що описує вхідний потік у другу фазу обслуговування для звичайних кас та експрес-кас.
Моделями для розрахунку характеристик системи масового обслуговування зручно користуватися в тому випадку, якщо вхідний потік вимог до системи обслуговування є найпростішим потоком пуасонів, а час обслуговування заявок розподілено за експоненційним законом.
Дослідження потоку покупців у зоні касового вузла показало, що йому може бути прийнятий пуасонівський потік.
Функція розподілу часу обслуговування покупців контролерами-касирами є експоненційною, таке припущення не призводить до великих помилок.
Безумовний інтерес представляє аналіз характеристик обслуговування потоку покупців у касовому вузлі універсаму, розрахованих для трьох систем: із втратами, з очікуванням та змішаного типу.
Розрахунки параметрів процесу обслуговування покупців у касовому вузлі проведені для комерційного підприємства торговою площею S = 650 на основі таких даних.
Цільова функція може бути записана у загальному вигляді зв'язку (критерію) виручки від реалізації від характеристик СМО:
де - касовий вузол складається з = 7 кас звичайного типу і = 2 експрес-кас,
Інтенсивність обслуговування покупців у зоні звичайних кас – 0,823 чол./хв;
Інтенсивність навантаження касових апаратів у зоні звичайних кас – 6,65,
Інтенсивність обслуговування покупців у зоні експрес-кас – 2,18 чол./хв;
Інтенсивність вхідного потоку до зони звичайних кас – 5,47 чол./хв.
Інтенсивність навантаження касових апаратів у зоні експрес-кас – 1,63,
Інтенсивність вхідного потоку до зони експрес-кас – 3,55 чол./хв;
Для моделі СМО з обмеженням на довжину черги відповідно до проектованої зони касового вузла максимально допустима кількість покупців, що стоять у черзі в одну касу, приймається рівним m=10 покупців.
Слід зауважити, що для отримання порівняно невеликих за абсолютною величиною значень ймовірності втрат заявок та часу очікування покупців у касовому вузлі необхідно дотримуватись наступних умов: 
У табл.6.6.3 наведено результати характеристик якості функціонування СМО у зоні розрахункового вузла.
Розрахунки проведені найбільш напруженого періоду часу робочого дня з 17 до 21 години. Саме цей період, як показали результати обстежень, припадає близько 50% одноденного потоку покупців.
З наведених даних у табл. 4.3 слід, що якби для розрахунку було обрано:
1) модель з відмовами, то 22,6% потоку покупців, що обслуговуються звичайними касами, і відповідно 33,6% потоку покупців, що обслуговуються експрес-касами, мали б піти без покупок;
2) модель з очікуванням, то втрат заявок у розрахунковому вузлі не повинно бути;
Табл. 4.3 Характеристики системи масового обслуговування покупців у зоні розрахункового вузла
| Тип каси | Кількість кас у вузлі | Тип СМО | Характеристики СМО | ||
| Середня кількість зайнятих кас, | середній час очікування обслуговування, | Можливість втрати заявок, | |||
| Звичайні каси | 7 | з відмовами з очікуванням з обмеженням |
|||
| Експрес-каси | 2 | з відмовами з очікуванням з обмеженням |
|||
3) модель з обмеженням на довжину черги, лише 0,12% потоку покупців, що обслуговуються звичайними касами, і 1,8% потоку покупців, що обслуговуються експрес-касами, залишать торговий зал без покупок. Отже, модель з обмеженням на довжину черги дозволяє точніше і реальніше описати процес обслуговування покупців у зоні касового вузла.
Інтерес представляє порівняльний розрахунок потужності касового вузла як з урахуванням експрес-кас, так і без них. У табл. 4.4 наведено характеристики системи обслуговування касового вузла трьох типорозмірів універсамів, розраховані за моделями СМО з обмеженням на довжину черги на найбільш напружений період робочого дня з 17 до 21 години.
Аналіз даних цієї таблиці показує, що не облік фактора "Структура потоку покупців за типом касового обслуговування" на стадії технологічного проектування може призвести до збільшення зони розрахункового вузла на 22-33%, а звідси відповідно і зменшення настановних та виставкових площ торгово-технологічного обладнання та товарної маси, що розміщується у торговому залі.
Проблема визначення потужності касового вузла є ланцюжком взаємопов'язаних характеристик. Так, збільшення його потужності скорочує час покупців на очікування обслуговування, зменшує ймовірність втрати вимог та, отже, втрати товарообігу. Поруч із необхідно відповідно зменшити зону самообслуговування, фронт торгово-технологічного устаткування, товарну масу у торговому залі. Водночас збільшується витрати на заробітну плату контролерів-касирів та обладнання додаткових робочих місць. Тому
| № п/п | Характеристики СМО | Одиниця виміру | Позначення | Показники, розраховані на типи універсамів торгової площі, кв. м | ||||||||||||||||
| Без експрес-кас | З урахуванням експрес-кас | |||||||||||||||||||
| 650 | 1000 | 2000 | 650 | 1000 | 2000 | |||||||||||||||
| Звичайні каси | Експрес-каси | Звичайні каси | експрес-каси | Звичайні каси | експрес-каси | |||||||||||||||
| 1 | Кількість покупців | чол. | k | 2310 | 3340 | 6680 | 1460 | 850 | 2040 | 1300 | 4080 | 2600 | ||||||||
| 2 | Інтенсивність вхідного потоку | λ | 9,64 | 13,9 | 27,9 | 6,08 | 3,55 | 8,55 | 5,41 | 17,1 | 10,8 | |||||||||
| 3 | Інтенсивність обслуговування | чол./хв | μ | 0,823 | 0,823 | 0,823 | 0,823 | 2,18 | 0,823 | 2,18 | 0,823 | 2,18 | ||||||||
| 4 | Інтенсивність навантаження | - | ρ | 11,7 | 16,95 | 33,8 | 6,65 | 1,63 | 10,35 | 2,48 | 20,7 | 4,95 | ||||||||
| 5 | Кількість касових апаратів | шт. | n | 12 | 17 | 34 | 7 | 2 | 11 | 3 | 21 | 5 | ||||||||
| 6 | Загальна кількість кас розрахункового вузла | шт. | ∑n | 12 | 17 | 34 | 9 | 14 | 26 | |||||||||||
необхідно проводити оптимізаційні розрахунки. Розглянемо характеристики системи обслуговування у касовому вузлі універсаму торгової площі 650м, розраховані за моделями СМО з обмеженою довжиною черги до різних потужностей його касового вузла в табл. 4.5.
За підсумками аналізу даних табл. 4.5 можна дійти невтішного висновку, що з збільшення кількості кас час очікування покупців у черзі зростає, та був після певного моменту різко падає. Характер зміни графіка часу очікування покупців зрозумілий, якщо паралельно розглядати зміну ймовірності втрати вимоги Цілком очевидно, що коли потужність касового вузла надмірно мала, то більше 85% покупців будуть йти необслуженими, а решта покупців буде обслужена за дуже короткий час. Чим більша потужність касового вузла, тим ймовірність втрати вимог чекатиме на своє обслуговування, а значить, і час їх очікування в черзі відповідно зростатиме. Після того як очікування та ймовірність втрат різко зменшуватимуться.
Для універсаму торговою площею 650 ця межа для зони звичайних кас лежить між 6 та 7 касовими апаратами. За 7 касових апаратів відповідно середній час очікування – 2,66 хв, а ймовірність втрати заявок дуже мала – 0,1%. Таким чином, що дозволить одержати мінімальні сукупні витрати на масове обслуговування покупців.
| Тип касового обслуговування | Кількість касових апаратів у вузлі n, прим. | Характеристики системи обслуговування | Середня виручка за 1 год. руб. | Середня втрата виручки за 1 год. руб | Число покупців у зоні розрахункового вузла | Площа зони розрахункового вузла, Sy, м | Питома вага площі зони вузла 650/ Sy | |
| Середній час очікування, Т, хв | Ймовірність втрати заявок | |||||||
| Зони Звичайних кас | ||||||||
| Зони експрес-кас | ||||||||
Висновок
За підсумками аналізу даних табл. 4.5 можна дійти невтішного висновку, що з збільшенням кількість кас час очікування покупців у черзі зростає. А потім після певного моменту різко падає. Характер зміни графіка часу очікування покупців зрозумілий, якщо паралельно розглядати зміну ймовірності втрати вимог Цілком очевидно, що коли потужність касового вузла надмірно мала, то більше 85% покупців будуть йти необслуженими, а частина покупців, що залишилася, буде обслужена за дуже короткий час. Чим більша потужність касового вузла. Тим ймовірність втрати вимог зменшуватиметься і відповідно тим більше покупців чекатиме свого обслуговування, а отже, і час їх очікування у черзі відповідно зростатиме. Після того як розрахунковий вузол перевищить оптимальний потужність, час очікування та ймовірність втрат різко зменшуватимуться.
Для універсаму торговою площею 650 кв. метрів ця межа для зони звичайних кас лежить між 6-8 касовими апаратами. При 7 касових апаратах відповідно середній час очікування - 2,66 хв, а ймовірність втрати заявок дуже мало - 0,1%. Таким чином, завдання полягає у виборі такої потужності касового вузла, яка дозволить отримати мінімальні сукупні витрати на масове обслуговування покупців.
У зв'язку з цим наступним етапом вирішення поставленого завдання є оптимізація потужності касового вузла на базі застосування моделей СМО різних типів з урахуванням сукупних витрат та перерахованих вище факторів.
Великий клас систем, які складно вивчити аналітичними способами, але добре вивчаються методами статистичного моделювання, зводиться до систем масового обслуговування (СМО).
У СМО мається на увазі, що є типові шляхи(канали обслуговування), якими у процесі обробки проходять заявки. Прийнято говорити, що заявки обслуговуютьсяканалами. Канали можуть бути різними за призначенням, характеристиками, можуть поєднуватися в різних комбінаціях; заявки можуть перебувати у чергах та чекати на обслуговування. Частина заявок може бути обслугована каналами, а частини можуть відмовити у цьому. Важливо, що заявки, з погляду системи, абстрактні: те, що хоче обслужитися, тобто пройти певний шлях у системі. Канали також є абстракцією: це те, що обслуговує заявки.
Заявки можуть надходити нерівномірно, канали можуть обслуговувати різні заявки за різний час і так далі, кількість заявок завжди дуже велика. Все це робить такі системи складними для вивчення та управління, і простежити всі причинно-наслідкові зв'язки в них неможливо. Тому прийнято уявлення про те, що обслуговування у складних системах має випадковий характер.
Прикладами СМО (див. табл. 30.1) можуть бути: автобусний маршрут і перевезення пасажирів; виробничий конвеєр з обробки деталей; ескадрилья літаків, що влітає на чужу територію і «обслуговується» зенітками ППО; ствол та ріжок автомата, які «обслуговують» патрони; електричні заряди, що переміщаються в деякому пристрої і т.д.
| Таблиця 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 і більше годин, хоча іноді краще міряти цю величину кількістю розглянутих заявок.
Аналіз тимчасової діаграми
Аналіз проведемо вже на розглянутому прикладі.
Спочатку потрібно дочекатися встановленого режиму. Відкидаємо перші чотири заявки як нехарактерні, які відбуваються під час процесу встановлення роботи системи. Вимірюємо час спостереження, припустимо, що у нашому прикладі воно становитиме Tн = 5 годин. Підраховуємо з діаграми кількість обслужених заявок Nобс. , часи простою та інші величини. Через війну можемо обчислити показники, що характеризують якість роботи СМО.
- Можливість обслуговування: Pобс. = Nобс. / N = 5/7 = 0.714 . Для розрахунку ймовірності обслуговування заявки в системі достатньо розділити кількість заявок, яким вдалося обслужитися за час Tн (див. лінійку «Обслужені») Nобс. , на кількість заявок Nякі хотіли обслужитися за цей же час. Як і раніше ймовірність експериментально визначаємо ставленням подій, що відбулися, до загального числа подій, які могли відбутися!
- Пропускна спроможність системи: A = Nобс. / Tн = 7/5 = 1.4 [шт/год]. Для розрахунку пропускної спроможності системи достатньо розділити кількість обслужених заявок Nобс. тимчасово Tн, за яке відбулося це обслуговування (див. лінійку «Обслуговування»).
- Імовірність відмови: Pвідк. = Nвідк. / N = 3/7 = 0.43 . Для розрахунку ймовірності відмови заявці в обслуговуванні достатньо поділити кількість заявок Nвідк. , яким відмовили за час Tн (див. лінійку «Відмовлені»), кількість заявок N, які хотіли обслужитися за цей же час, тобто надійшли до системи. Зверніть увагу. Pвідк. + Pобс.теоретично має бути одно 1. Насправді експериментально вийшло, що Pвідк. + Pобс. = 0.714 + 0.43 = 1.144. Ця неточність пояснюється тим, що час спостереження Tн мало і статистика накопичена недостатня для отримання точної відповіді. Похибка цього показника зараз становить 14%!
- Імовірність зайнятості одного каналу: P 1 = Tзан. / Tн = 0.05/5 = 0.01, де Tзан. — час зайнятості лише одного каналу (першого чи другого). Вимірюванням підлягають тимчасові відрізки, у яких відбуваються певні події. Наприклад, на діаграмі шукаються такі відрізки, під час яких зайняті перший або другий канал. У цьому прикладі є один такий відрізок наприкінці діаграми довжиною 0.05 години. Частка цього відрізка у загальному часі розгляду ( Tн = 5 годин) визначається розподілом і становить ймовірність зайнятості.
- Імовірність зайнятості двох каналів: P 2 = Tзан. / Tн = 4.95/5 = 0.99. На діаграмі шукаються такі відрізки, під час яких одночасно зайняті перший і другий канал. У цьому прикладі таких відрізків чотири, їх сума дорівнює 4.95 години. Частка тривалості цих подій у загальному часі розгляду ( Tн = 5 годин) визначається розподілом і становить ймовірність зайнятості.
- Середня кількість зайнятих каналів: Nск = 0 · P 0 + 1 · P 1 + 2 · P 2 = 0.01 + 2 · 0.99 = 1.99. Щоб підрахувати, скільки каналів зайнято в системі в середньому, достатньо знати частку (ймовірність зайнятості одного каналу) та помножити на вагу цієї частки (один канал), знати частку (ймовірність зайнятості двох каналів) та помножити на вагу цієї частки (два канали) та так далі. Отримана цифра 1.99 говорить про те, що із можливих двох каналів у середньому завантажено 1.99 каналу. Це високий показник завантаження, 99.5%, система добре використовує ресурс.
- Імовірність простою хоча б одного каналу: P * 1 = Tпростою1 / Tн = 0.05/5 = 0.01.
- Імовірність простою двох каналів одночасно: P * 2 = Tпростою2 / Tн = 0.
- Імовірність простою всієї системи: P* c = Tпростою сист. / Tн = 0.
- Середня кількість заявок у черзі: Nсз = 0 · P 0з + 1 · P 1з + 2 · P 2з = 0.34 + 2 · 0.64 = 1.62 [шт]. Щоб визначити середню кількість заявок у черзі, треба визначити окремо ймовірність того, що у черзі буде одна заявка P 1з , ймовірність того, в черзі стоятиме дві заявки P 2з і т. д. і знову з відповідними вагами їх скласти.
- Імовірність того, що в черзі буде одна заявка: P 1з = T 1з / Tн = 1.7/5 = 0.34(Усього на діаграмі чотирьох таких відрізка, що в сумі дають 1.7 години).
- Імовірність того, у черзі стоятиме одночасно дві заявки: P 2з = T 2з / Tн = 3.2/5 = 0.64(Усього на діаграмі три таких відрізки, що в сумі дають 3.25 години).
- Середній час очікування заявки у черзі:
(Скласти всі часові інтервали, протягом яких будь-яка заявка перебувала у черзі, і поділити кількість заявок). На часовій діаграмі таких заявок 4.
- Середній час обслуговування заявки:
(Скласти всі часові інтервали, протягом яких будь-яка заявка перебувала на обслуговуванні в якомусь каналі, та поділити на кількість заявок).
- Середній час перебування заявки у системі: Tпор. сист. = Tпор. ож. + Tпор. обсл..
- Середня кількість заявок у системі:
Розіб'ємо інтервал спостереження, наприклад, на десятихвилинки. Вийде на п'яти годинах Kпідінтервалів (у нашому випадку K= 30). У кожному підінтервалі визначимо за часовою діаграмою, скільки заявок у цей момент перебуває у системі. Дивитися треба на 2, 3, 4 і 5 лінійки - які з них зайняті в даний момент. Потім суму Kдоданків усереднити.
Далі слід оцінити точність кожного з одержаних результатів. Тобто відповісти на запитання: наскільки ми можемо довіряти цим значенням? Оцінка точності проводиться за методикою, описаною у лекції 34 .
Якщо точність не є задовільною, слід збільшити час експерименту і тим самим поліпшити статистику. Можна зробити по-іншому. Знову кілька разів запустити експеримент на якийсь час Tн. А згодом усереднити значення цих експериментів. І знову перевірити результати на критерій точності. Цю процедуру слід повторювати доти, доки не буде досягнуто необхідної точності.
Далі слід скласти таблицю результатів та оцінити значення кожного з них з погляду клієнта та власника СМО (див. табл. 30.3). Наприкінці, враховуючи сказане у кожному пункті, слід зробити загальний висновок. Таблиця повинна мати приблизно такий вигляд, як показано в табл. 30.3.
| Таблиця 30.3. Показники СМО |
||||||||||||||||||||||||
| Показник | Формула | Значення | Інтереси власника СМО | Інтереси клієнта СМО |
| Можливість обслуговування | Pобс. = Nобс. / N | 0.714 | Імовірність обслуговування мала, багато клієнтів йдуть із системи незадоволеними, їхні гроші для власника втрачені. Це мінус. | Імовірність обслуговування мала, кожен третій клієнт хоче, але може обслужитися. Це мінус. |
| Середня кількість заявок у черзі | Nсз = 0 · P 0з + 1 · P 1з + 2 · P 2з | 1.62 | Черга майже весь час вся забита. Усі місця у черзі використовуються досить ефективно. Вкладення на організацію черги окупають витрати на неї. Це "плюс". Клієнти, які довго стоять у черзі, можуть піти, не дочекавшись обслуговування. Клієнти, простоюючи, можуть завдати шкоди системі, ламати обладнання. Багато відмов, втрачених клієнтів. Це "мінуси". |
Черга майже весь час вся забита. Клієнту доводиться стояти у черзі, перш ніж він потрапить на обслуговування. Клієнт може не потрапити навіть у чергу. Це мінус. |
| Загальний висновок: | В інтересах власника: а) збільшити пропускну спроможність каналів, щоб не втрачати клієнтів (щоправда, модернізація каналів коштує грошей); б) збільшити кількість місць у черзі (це теж коштує грошей), щоб затримати потенційних клієнтів. | Клієнти зацікавлені у значному збільшенні пропускної спроможності для зменшення часу очікування та зменшення відмов. | ||
Синтез СМО
Ми зробили аналіз існуючої системи. Це дало змогу побачити її недоліки та визначити напрями покращення її якості. Але залишаються незрозумілими відповіді на конкретні питання, що саме треба зробити — збільшувати кількість каналів чи збільшувати їхню пропускну здатність, чи збільшувати кількість місць у черзі, і, якщо збільшувати, то наскільки? Є й такі питання, що краще — створити 3 канали з продуктивністю 5 шт/год чи один із продуктивністю 15 шт/год?
Щоб оцінити чутливість кожного показника до зміни значення певного параметра, надходять у такий спосіб. Фіксують всі параметри, крім одного, обраного. Потім знімають значення всіх показників за кількох значеннях цього вибраного параметра. Звичайно, доводиться повторювати знову і знову процедуру імітації та усереднювати показники при кожному значенні параметра оцінювати точність. Але в результаті виходять надійні статистичні залежності показників від параметра.
Наприклад, для 12 показників нашого прикладу можна отримати 12 залежностей від одного параметра: залежність ймовірності відмов Pвідк. від кількості місць у черзі (КМО), залежність пропускної спроможності Aвід кількості місць у черзі, і так далі (див. рис. 30.8).
Потім також можна зняти ще 12 залежностей показників Pвід іншого параметра Rзафіксувавши інші параметри. І так далі. Утворюється своєрідна матриця залежностей показників Pвід параметрів R, За якою можна провести додатковий аналіз про перспективи руху (покращення показників) у той чи інший бік. Нахил кривих добре показує чутливість, ефект від руху за певним показником. У математиці цю матрицю називають якобіаном J, в якій роль нахилу кривих відіграють значення похідних Δ P i /Δ R j див. рис. 30.9. (Нагадаємо, що похідна пов'язана геометрично з кутом нахилу дотичної до залежності.)
залежно від зміни параметрів СМО
Якщо показників 12 а параметрів, наприклад, 5, то матриця має розмірність 12 x 5. Кожен елемент матриці - крива, залежність i-го показника від j-го параметра. Кожна точка кривої - середнє значення показника на досить представницькому відрізку Tн або усереднено за кількома експериментами.
Слід розуміти, що криві знімалися у припущенні те, що це параметри крім одного у процесі їх зняття були незмінні. (Якби всі параметри змінювали значення, то криві були б іншими. Але так не роблять, тому що вийде повна плутанина і залежностей не буде видно.)
Тому, якщо на підставі розгляду знятих кривих приймається рішення про те, що певний параметр буде в СМО змінено, то всі криві для нової точки, в якій знову досліджуватиметься питання про те, який параметр слід змінити, щоб покращити показники, слід знімати заново.
Так крок за кроком можна спробувати покращити якість системи. Але поки що ця методика не може відповісти на низку питань. Справа в тому, що, по-перше, якщо криві монотонно ростуть, то виникає питання, де все ж таки слід зупинитися. По-друге, можуть виникати суперечності, один показник може покращуватися при зміні вибраного параметра, тоді як інший одночасно погіршуватиметься. По-третє, ряд параметрів складно висловити чисельно, наприклад, зміну дисципліни обслуговування, зміну напрямів потоків, зміну топології СМО. Пошук рішення у двох останніх випадках проводиться із застосуванням методів експертизи (див. лекцію 36. Експертиза) та методами штучного інтелекту (див. .
Тому зараз обговоримо лише перше питання. Як прийняти рішення, яким має бути значення параметра, якщо з його зростанням показник весь час монотонно покращується? Навряд чи значення нескінченності влаштує інженера.
Параметр R— управління, це те, що знаходиться в розпорядженні власника СМО (наприклад, можливість заасфальтувати майданчик і збільшити кількість місць у черзі, поставити додаткові канали, збільшити потік заявок за рахунок збільшення витрат на рекламу і так далі). Змінюючи керування, можна впливати на значення показника P, Мета, критерій (ймовірність відмов, пропускну спроможність, середній час обслуговування тощо). З рис. 30.10 видно, що якщо збільшувати управління R, то можна добитися завжди покращення показника P. Але очевидно, що будь-яке управління пов'язане із витратами Z. І що більше докладають зусилля керувати, що більше значення управляючого параметра, то більше вписувалося витрати. Зазвичай витрати на управління зростають лінійно: Z = C 1 · R . Хоча трапляються випадки, коли, наприклад, в ієрархічних системах, вони зростають експоненційно, іноді назад експоненційно (знижки за опт) і так далі.
від керованого параметра R (приклад)
У будь-якому випадку ясно, що колись вкладення нових витрат просто перестане себе окупати. Наприклад, ефект від заасфальтованого майданчика розміром 1 км 2 навряд чи окупить витрати власника бензоколонки в Урюпинську, там просто не буде стільки охочих заправитися бензином. Іншими словами показник Pу складних системах не може зростати нескінченно. Рано чи пізно його зростання сповільнюється. А витрати Zзростають (див. рис. 30.11).
З рис. 30.11 видно, що за призначенням ціни C 1 за одиницю витрат Rта ціни C 2 за одиницю показника P, ці криві можна скласти. Криві складають, якщо їх потрібно одночасно мінімізувати чи максимізувати. Якщо одна крива підлягає максимізації, а інша мінімізації, слід знайти їх різницю, наприклад по точках. Тоді результуюча крива (див. рис. 30.12), що враховує і ефект від управління та витрати на це, матиме екстремум. Значення параметру R, що доставляє екстремум функції, і є вирішення задачі синтезу.
та витрат Z на його отримання як функції керованого параметра R
Крім управління Rта показника Pу системах діє обурення. Обурення позначимо як D = {d 1 , d 2, …)див. рис. 30.13. Обурення - це вхідна дія, яка, на відміну від керуючого параметра, не залежить від волі власника системи. Наприклад, низькі температури на вулиці, конкуренція знижують, на жаль, потік клієнтів, поломки обладнання прикро знижують продуктивність системи. І керувати цими величинами безпосередньо власник системи не може. Зазвичай обурення діє «на зло» власнику, знижуючи ефект Pвід керуючих зусиль R. Це відбувається тому, що, загалом, система створюється задля досягнення цілей, недосяжних самих собою у природі. Людина, організуючи систему, завжди сподівається за допомогою її досягти певної мети P. На це він витрачає зусилля Rйдучи всупереч природі. Система — організація доступних людині, вивчених нею природних компонент задля досягнення певної нової мети, недосяжної раніше іншими способами.
на яку впливають керуючі дії R та обурення D
Отже, якщо ми знімемо залежність показника Pвід управління Rще раз (як показано на рис. 30.10), але в умовах обурення, що з'явилося D, то, можливо, характер кривої зміниться. Швидше за все, показник буде за однакових значень управлінь перебувати нижче, оскільки обурення носить «противний» характер, знижуючи показники системи (див. рис. 30.14). Система, надана сама собі, без зусиль керуючого характеру, перестає забезпечувати мету, задля досягнення якої вона була створена. Якщо, як і раніше, побудувати залежність витрат, співвіднести її із залежністю показника від параметра управління, то знайдена точка екстремуму зміститься (див. рис. 30.15) порівняно з випадком «обурення = 0» (див. рис. 30.12).
при різних значеннях, що діють на систему збурень D
Якщо знову збільшити обурення, криві зміняться (див. рис. 30.14) і, як наслідок, знову зміниться положення точки екстремуму (див. рис. 30.15).
при різних значеннях діючого фактора, що обурює D
Зрештою, всі знайдені положення точок екстремуму переносяться на новий графік, де утворюють залежність Показника Pвід Керуючого параметра Rпри зміні Обурень D(Див. рис. 30.16).
параметра R при зміні значень збурень D
(крива складається лише з точок екстремумів)
Зверніть увагу, що насправді на цьому графіку можуть бути й інші робочі точки (графік пронизаний як би сімействами кривих), але нанесені нами точки задають такі координати параметра, що управляє, при яких при заданих обуреннях (!) досягається найбільше з можливих значення показника P .
Цей графік (див. рис. 30.16) пов'язує Показник P, Управління (ресурс) Rта Обурення Dу складних системах, вказуючи, як діяти якнайкраще ЛПР (особі, яка приймає рішення) в умовах виниклих обурень. Тепер користувач може, знаючи реальну обстановку на об'єкті (значення обурення), швидко за графіком визначити, який керуючий вплив на об'єкт необхідно, щоб забезпечити найкраще значення показника, що його цікавить.
Зауважте, якщо керуючий вплив буде менше оптимального, то сумарний ефект знизиться, виникне ситуація недоотриманого прибутку. Якщо керуючий вплив буде більшим за оптимальний, то ефект такожзнизиться, тому що заплатити за чергове збільшення керуючих зусиль треба буде за величиною більше, ніж та, яку ви отримаєте внаслідок її використання (ситуація банкрутства).
Примітка. У тексті лекції ми використовували слова «управління» та «ресурс», тобто вважали, що R = U. Слід пояснити, що управління справді відіграє роль певної обмеженої цінності для власника системи. Тобто, завжди є цінним для нього ресурсом, за який завжди доводиться платити, і якого завжди не вистачає. Дійсно, якби ця величина не була обмежена, то ми могли б досягати за рахунок нескінченної величини управлінь нескінченно великих значень цілей, а ось нескінченно великих результатів у природі явно не спостерігається.
Іноді розрізняють власне управління Uта ресурс R, називаючи ресурсом певний запас, тобто межу можливого значення управляючого впливу. У цьому випадку поняття ресурс та управління не збігаються: U < R. Іноді розрізняють граничне значення управління U ≤ Rта інтегральний ресурс ∫Udt ≤ R .
Системи масового обслуговуванняабо теорія масового обслуговування- предмет, що бере початок у теорії ймовірностей. Але вивчення таких систем у додатку до реального світу (а їх безліч: магазин або вокзал з касами, склад з операторами, перукарні та лікарні, обчислювальні мережі, верстати та наладчики, системи АТС тощо) зазвичай проходить у рамках предметів " Дослідження операцій" та "Математичні методи в економіці", тому ми поміщаємо приклади рішень щодо СМО в даний розділ.
Завдання систем масового обслуговування мають справу з об'єктами, де є: а) черга заявок (клієнтів, дзвінків, відвідувачів, сигналів тощо) та б) обмежена кількість каналів для їх обробки (операторів, касирів, лікарів, транзисторів тощо). п.). Математично можна обчислити ефективність та основні показники робіт системи, що дозволить у реальному світі налагодити роботу найбільш правильно, економічно, вигідно, зручно.
Ви можете замовити рішення своїх завдань та контрольних робіт з різних тем теорії систем масового обслуговування в МатБюро: (Рішення задач з економіко-математичних методів на замовлення). Вартість виконання від 200 рублів, термін від 2 днів, оформлення докладне в Word з графіками та висновками.
Безкоштовні приклади рішень щодо СМО (системи масового обслуговування)
Завдання 1.Інтенсивність потоку телефонних дзвінків в агентство на замовлення залізничних квитків, що має один телефон, становить 16 викликів на годину. Тривалість оформлення замовлення на квиток дорівнює 2.4 хвилин. Визначити відносну та абсолютну пропускну здатність цієї СМО та ймовірність відмови (зайнятості телефону). Скільки телефонів має бути в агентстві, щоб відносна пропускна спроможність була не менше ніж 0,75.
Завдання 2.Система масового обслуговування - квиткова каса з одним віконцем та необмеженою чергою. Каса продає квитки до пунктів А та В. Пасажирів, які бажають купити квиток до пункту А, приходить у середньому троє за 20 хв, до пункту В – двоє за 20 хв. Потік пасажирів найпростіший. Касир у середньому обслуговує трьох пасажирів за 10 хв. Час обслуговування – показовий. Обчислити фінальні ймовірності Р0, P2, P3, середнє число заявок у системі та в черзі, середній час перебування заявки у системі, середній час перебування заявки у черзі.
Завдання 3.Міжміський переговорний пункт має чотири телефонні апарати. У середньому за добу надходить 320 заявок на переговори. Середня тривалість переговорів становить 5 хв. Довжина черги не повинна перевищувати 6 абонентів. Потоки заявок та обслуговувань найпростіші. Визначити характеристики обслуговування переговорного пункту в стаціонарному режимі (імовірність простою каналів, ймовірність відмови, ймовірність обслуговування, середня кількість зайнятих каналів, середня кількість заявок у черзі, середня кількість заявок у системі, абсолютна пропускна спроможність, відносна пропускна спроможність, середній час заявки у черзі, середній час заявки у системі, середній час заявки під обслуговуванням).
Приклади розв'язання задач систем масового обслуговування
Потрібно розв'язати задачі 1–3. Вихідні дані наведено у табл. 2–4.
Деякі позначення, які застосовуються в теорії масового обслуговування, для формул:
n – число каналів СМО;
λ – інтенсивність вхідного потоку заявок П вх;
v – інтенсивність вихідного потоку заявок П вих;
μ - інтенсивність потоку обслуговування П про;
ρ – показник навантаження системи (трафік);
m – максимальна кількість місць у черзі, що обмежує довжину черги заявок;
i – кількість джерел заявок;
p до - Імовірність k-го стану системи;
p о - ймовірність простоювання всієї системи, тобто ймовірність того, що всі канали вільні;
p сист - ймовірність прийняття заявки до системи;
p отк – можливість відмови заявці у прийнятті їх у систему;
р про – ймовірність того, що заявку буде обслуговано;
А – абсолютна пропускна спроможність системи;
Q – відносна пропускна спроможність системи;
оч - середня кількість заявок у черзі;
про – середня кількість заявок під обслуговуванням;
сист - середня кількість заявок у системі;
оч – середній час очікування заявки у черзі;
про – середній час обслуговування заявки, що стосується лише обслуженим заявкам;
сис – середній час перебування заявки у системі;
ож - середній час, що обмежує очікування заявки у черзі;
- Середня кількість зайнятих каналів.
Абсолютна пропускна спроможність СМО А – середня кількість заявок, що може обслужити система за одиницю часу.
Відносна пропускна здатність СМО Q - відношення середньої кількості заявок, що обслуговуються системою в одиницю часу, до середньої кількості заявок, що надходять за цей час.
При вирішенні завдань масового обслуговування вкрай важливо дотримуватися наведеної нижче послідовності:
1) визначення типу СМО за табл. 4.1;
2) вибір формул відповідно до типу СМО;
3) розв'язання задачі;
4) формулювання висновків із завдання.
1.Схема загибелі та розмноження.Ми знаємо, що, маючи у розпорядженні розмічений граф станів, можна легко написати рівняння Колмогорова для ймовірностей станів, а також написати та вирішити рівняння алгебри для фінальних ймовірностей. Варто сказати, що в деяких випадках вдається останні рівняння
вирішити заздалегідь, у буквеному вигляді. Зокрема, це вдається зробити, якщо граф станів системи є так званою «схемою загибелі і розмноження».
Граф станів для схеми загибелі та розмноження має вигляд, показаний на рис. 19.1. Особливість цього графа в тому, що всі стани системи можна витягнути в один ланцюжок, в якому кожен із середніх станів ( S 1 , S 2 ,…,S n-1) пов'язано прямою і зворотною стрілкою з кожним із сусідніх станів - правим і лівим, а крайні стани (S 0 , S n) - тільки з одним сусіднім станом. Термін «схема загибелі та розмноження» веде початок від біологічних завдань, де подібною схемою описується зміна чисельності популяції.
Схема загибелі та розмноження дуже часто зустрічається в різних завданнях практики, зокрема - в теорії масового обслуговування, у зв'язку з цим корисно, один раз і назавжди знайти для неї фінальні ймовірності станів.
Припустимо, що всі потоки подій, що переводять систему за стрілками графа, - найпростіші (для стислості будемо називати і систему Sі протікає у ній процес - найпростішими).
Користуючись графом рис. 19.1, складемо і вирішимо алгебраїчні рівняння для фінальних ймовірностей (стан), існування випливає з того, що з кожного стану можна перейти в кожне інше, в число станів звичайно). Для першого стану S 0 маємо:
(19.1)
Для другого стану S 1:
В силу (19.1) остання рівність наводиться до вигляду
де kприймає всі значення від 0 до п.Отже, фінальні ймовірності p 0 , p 1 ,..., р n задовольняють рівнянням
(19.2)
крім того, потрібно врахувати нормувальну умову
p 0 + p 1 + p 2 +…+ p n =1. (19.3)
Вирішимо цю систему рівнянь. З першого рівняння (19.2) виразимо p 1 через р 0 :
p 1 = p 0. (19.4)
З другого, з урахуванням (19.4), отримаємо:
(19.5)
‣‣‣ із третього, з урахуванням (19.5),
(19.6)
і взагалі, для будь-кого k(від 1 до n):
(19.7)
Звернімо увагу на формулу (19.7). У чисельнику стоїть твір всіх інтенсивностей, що стоять у стрілок, що ведуть зліва направо (з початку і до цього стану S k), а в знаменнику - добуток всіх інтенсивностей, що стоять у стрілок, що ведуть праворуч наліво (з початку і до S k).
Τᴀᴋᴎᴎᴀᴈᴏᴍ, всі ймовірності станів р 0 , p 1 , ..., р nвиражені через одну з них ( р 0). Підставимо ці висловлювання в нормувальну умову (19.3). Отримаємо, виносячи за дужку р 0:
звідси отримаємо вираз для р 0 :
(дужку ми звели в ступінь -1, щоб не писати двоповерхових дробів). Всі інші ймовірності виражені через р 0 (див. формули (19.4) – (19.7)). Зауважимо, що коефіцієнти при р 0 у кожній з них являють собоюне що інше, як послідовні члени ряду, що стоїть після одиниці у формулі (19.8). Отже, обчислюючи р 0 , ми вже знайшли всі ці коефіцієнти.
Отримані формули дуже корисні під час вирішення найпростіших завдань теорії масового обслуговування.
^ 2. Формула Літтла.Тепер ми виведемо одну важливу формулу, яка зв'язує (для граничного, стаціонарного режиму) середню кількість заявок Lсист, що перебувають у системі масового обслуговування (тобто обслуговуються або стоять у черзі), та середній час перебування заявки в системі Wсист.
Розглянемо будь-яку СМО (одноканальну, багатоканальну, марківську, немарківську, з необмеженою або з обмеженою чергою) та пов'язані з нею два потоки подій: потік заявок, що прибувають до СМО, та потік заявок, що залишають СМО. Якщо в системі встановився граничний, стаціонарний режим, то середня кількість заявок, що прибувають до СМО за одиницю часу, дорівнює середній кількості заявок, що залишають її: обидва потоки мають одну і ту ж інтенсивність λ.
Позначимо: X(t) -кількість заявок, які прибули до СМО до моменту t. Y(t) - кількість заявок, що залишили СМО
до моменту t.І та, і інша функції є випадковими і змінюються стрибком (збільшуються на одиницю) в моменти приходів заявок (X(t)) та доглядів заявок (Y(t)).Вигляд функцій X(t) та Y(t)показано на рис. 19.2; обидві лінії - ступінчасті, верхня - X(t),нижня- Y(t).Очевидно, що для будь-якого моменту tїхня різниця Z(t)= X(t) - Y(t)є не що інше, як кількість заявок, які перебувають у СМО. Коли лінії X(t)і Y(t)зливаються, у системі немає заявок.
Розглянемо дуже великий проміжок часу Т(подумки продовживши графік далеко межі креслення) і обчислимо йому середнє число заявок, що у СМО. Воно дорівнюватиме інтегралу від функції Z(t)на цьому проміжку, поділеному на довжину інтервалу Т:
Lсист. = . (19.9) про
Але цей інтеграл є не що інше, як площа фігури, заштрихованої на рис. 19.2. Розглянемо добре цей малюнок. Фігура складається з прямокутників, кожен з яких має висоту, рівну одиниці, і основу, що дорівнює часу перебування в системі відповідної заявки (першої, другої тощо). Позначимо ці часи t 1 , t 2 ,...Щоправда, під кінець проміжку Тдеякі прямокутники увійдуть у заштриховану фігуру не повністю, а частково, але за досить великого Тці дрібниці не відіграватимуть ролі. Τᴀᴋᴎᴎᴎᴈᴏᴍ, можна вважати, що
(19.10)
де сума поширюється на всі заявки, що прийшли за час Т.
Розділимо праву та ліву частину (.19.10) на довжину інтервалу Т.Отримаємо, з урахуванням (19.9),
Lсист. =. (19.11)
Розділимо та помножимо праву частину (19.11) на інтенсивність X:
Lсист. =.
Але величина Тλє не що інше, як середня кількість заявок, що прийшли за час ^ Т.Якщо ми розділимо суму всіх часів t iна середню кількість заявок, то отримаємо середній час перебування заявки у системі Wсист. Отже,
Lсист. = λ Wсист. ,
Wсист. =. (19.12)
Це і є чудова формула Літтла: для будь-якої СМО, за будь-якого характеру потоку заявок, за будь-якого розподілу часу обслуговування, за будь-якої дисципліни обслуговування середній час перебування заявки у системі дорівнює середньому числу заявок у системі, поділеному на інтенсивність потоку заявок.
Так само виводиться друга формула Літтла, що пов'язує середній час перебування заявки в черзі ^ W очта середня кількість заявок у черзі Lоч:
Wоч = . (19.13)
Для виведення достатньо замість нижньої лінії на рис. 19.2 взяти функцію U(t)- кількість заявок, що пішли до моменту tне з системи, а з черги (якщо заявка, що прийшла в систему, не стає в чергу, а відразу йде під обслуговування, можна все ж таки вважати, що вона стає в чергу, але знаходиться в ній нульовий час).
Формули Літтла (19.12) та (19.13) відіграють велику роль у теорії масового обслуговування. На жаль, у більшості існуючих посібників ці формули (доведені у загальному вигляді порівняно недавно) не наводяться 1).
§ 20. Найпростіші системи масового обслуговування та їх характеристики
У цьому параграфі ми розглянемо деякі найпростіші СМО і виведемо вирази для їх характеристик (показників ефективності). При цьому ми продемонструємо основні методичні прийоми, характерні для елементарної, «марківської» теорії масового обслуговування. Ми не гнатимемося за кількістю зразків СМО, для яких будуть виведені кінцеві вирази характеристик; дана книга - не довідник з теорії масового обслуговування (таку роль краще виконують спеціальні керівництва). Наша мета - познайомити читача з деякими «маленькими хитрощами», які полегшують шлях крізь теорію масового обслуговування, яка в низці наявних (навіть претендують на популярність) книг може здатися нескладним набором прикладів.
Всі потоки подій, що переводять СМО зі стану в стан, у даному параграфі ми вважатимемо найпростішими (не обговорюючи це щоразу спеціально). Серед них буде і так званий «потік обслуговування». Під ним розуміється потік заявок, що обслуговуються одним безперервно зайнятим каналом. У цьому потоці інтервал між подіями, як і завжди в найпростішому потоці, має показовий розподіл (у багатьох посібниках натомість кажуть: «час обслуговування - показовий», ми і самі надалі користуватимемося таким терміном).
1) У популярній книжці дано дещо інший, порівняно з вищевикладеним, висновок формули Літтла. Взагалі, знайомство з цією книжкою («Розмова друга») корисно для початкового ознайомлення з теорією масового обслуговування.
У даному параграфі показовий розподіл часу обслуговування буде само собою зрозумілим, як завжди для «найпростішої» системи.
Характеристики ефективності аналізованих СМО ми будемо вводити під час викладу.
^ 1. п-канальна СМО з відмовами(Завдання Ерланга). Тут ми розглянемо одну з перших за часом, «класичних» завдань теорії масового обслуговування;
це завдання виникло з практичних потреб телефонії і було вирішено на початку ХХ століття датським математиком Ерлантом. Завдання ставиться так: є пканалів (ліній зв'язку), на які надходить потік заявок з інтенсивністю? Потік обслуговування має інтенсивність μ (величина, зворотна середньому часу обслуговування tпро). Знайти фінальні ймовірності станів СМО, а також характеристики її ефективності:
^ А -абсолютну пропускну спроможність, тобто середня кількість заявок, що обслуговуються в одиницю часу;
Q -відносну пропускну здатність, тобто середню частку заявок, що прийшли, обслуговуються системою;
^ Р відк- ймовірність відмови, тобто того, що заявка залишає СМО не обслуженою;
k -середня кількість зайнятих каналів.
Рішення. Стан системи ^ S(СМО) нумеруватимемо за кількістю заявок, що знаходяться в системі (в даному випадку воно збігається з числом зайнятих каналів):
S 0 -в СМО немає жодної заявки,
S 1 -в СМО знаходиться одна заявка (один канал зайнятий, інші вільні),
S k -у СМО знаходиться kзаявок ( kканалів зайняті, інші вільні),
S n -у СМО знаходиться пзаявок (все nканалів зайняті).
Граф станів СМО відповідає схемі загибелі у розмноженні (рис. 20.1). Розмітимо цей граф - проставимо у стрілок інтенсивності потоків подій. З S 0 в S 1систему переводить потік заявок з інтенсивністю λ (як тільки надходить заявка, система перескакує з S 0в S 1).Той самий потік заявок перекладає
систему з будь-якого лівого стану в сусідній правий (див. верхні стрілки на рис. 20.1).
Проставимо інтенсивність у нижніх стрілок. Нехай система перебуває в стані ^ S 1 (працює один канал). Він виробляє μ обслуговування в одиницю часу. Проставляємо у стрілки S 1 →S 0 інтенсивність? Тепер уявімо, що система перебуває в стані S 2(Працюють два канали). Щоб їй перейти до S 1 ,потрібно, щоб закінчив обслуговування перший канал, або другий; сумарна інтенсивність їх потоків обслуговування дорівнює 2μ; проставляємо її у відповідної стрілки. Сумарний потік обслуговування, що дається трьома каналами, має інтенсивність 3μ, kканалами - kμ.Проставляємо ці інтенсивності у нижніх стрілок на рис. 20.1.
А тепер, знаючи всі інтенсивності, скористаємося вже готовими формулами (19.7), (19.8) для фінальних ймовірностей у схемі загибелі та розмноження. За формулою (19.8) отримаємо:
Члени розкладання 
являтимуть собою коефіцієнти при р 0у виразах для p 1
Зауважимо, що у формули (20.1), (20.2) інтенсивності λ і μ входять не окремо, а лише у вигляді відношення λ/μ. Позначимо
λ/μ = ρ (20.3)
і будемо називати величину р «наведеною інтенсивністю потоку заявок». Її зміст-середня кількість заявок, що надходить за середній час обслуговування однієї заявки. Користуючись цим позначенням, перепишемо формули (20.1), (20.2) у вигляді:
Формули (20.4), (20.5) для фінальних ймовірностей станів називаються формулами Ерланга – на честь засновника теорії масового обслуговування. Більшість інших формул цієї теорії (сьогодні їх більше, ніж грибів у лісі) не мають жодних спеціальних імен.
Τᴀᴋᴎᴎᴩᴀᴈᴏᴍ, фінальні ймовірності знайдені. За ними ми обчислимо показники ефективності СМО. Спочатку знайдемо ^ Р відк. - ймовірність того, що заявка, що прийшла, отримає відмову (не буде обслужена). Для цього потрібно, щоб все пканалів були зайняті, отже,
Рвідк = р n = . (20.6)
Звідси знаходимо відносну пропускну спроможність - ймовірність того, що заявку буде обслуговано:
Q = 1 - Pвідк. = 1 - (20.7)
Абсолютну пропускну здатність отримаємо, помножуючи інтенсивність потоку заявок λ, Q:
A = Q = λ. (20.8)
Залишилося тільки знайти середню кількість зайнятих каналів k.Цю величину можна було б знайти «прямо», як математичне очікування дискретної випадкової величини з можливими значеннями 0, 1, ..., пта ймовірностями цих значень р 0 р 1 ..., р n:
k = 0 · р 0 + 1 · p 1 + 2 · р 2 + ... + п · р n.
Підставляючи сюди вирази (20.5) для р k , (k = 0, 1, ..., д)і виконуючи відповідні перетворення, ми зрештою отримали б вірну формулу для k.Але ми виведемо її набагато простіше (ось вона, одна з «маленьких хитрощів»!) Насправді, нам відома абсолютна пропускна здатність А.Це не що інше, як інтенсивність потоку обслужених системою заявок. Кожен зайнятий i .шал за одиницю часу обслуговує у середньому |л заявок. Отже, середня кількість зайнятих каналів дорівнює
k = A/μ, (20.9)
або, враховуючи (20.8),
k = 
(20.10)
Рекомендуємо читачеві самостійно вирішити приклад.
Розміщено на реф.
Є станція зв'язку з трьома каналами ( n= 3), інтенсивність потоку заявок λ = 1,5 (заявки за хвилину); середній час обслуговування однієї заявки tпро = 2 (хв.), всі потоки подій (як і у всьому цьому параграфі) - найпростіші. Знайти фінальні ймовірності станів та характеристики ефективності СМО: А, Q, Pвідк, k.Про всяк випадок повідомляємо відповіді: p 0 = 1/13, p 1 = 3/13, p 2 = 9/26, р 3 = 9/26 ≈ 0,346,
А≈ 0,981, Q ≈ 0,654, Pвідкл ≈ 0,346, k ≈ 1,96.
З відповідей видно, між іншим, що наша СМО значною мірою перевантажена: із трьох каналів зайнято в середньому близько двох, а з заявок, що надходять, близько 35% залишаються не обслуженими. Пропонуємо читачеві, якщо він цікавий і нелінів, дізнатися: скільки потрібно каналів для того, щоб задовольнити не менше 80% заявок, що надходять? І яка частка каналів при цьому простоюватиме?
Тут уже проглядає деякий натяк на оптимізацію.Насправді зміст кожного каналу в одиницю часу обходиться в якусь суму. Водночас, кожна обслужена заявка приносить якийсь дохід. Помножуючи цей дохід на середню кількість заявок А,що обслуговуються в одиницю часу, ми отримаємо середній дохід від СМО в одиницю часу. Природно, зі збільшенням числа каналів цей дохід зростає, але зростають і витрати, пов'язані зі змістом каналів. Що переважить – збільшення доходів чи витрат? Це залежить від умов операції, від «плати за обслуговування заявки» та від вартості змісту каналу. Знаючи ці величини, можна знайти оптимальну кількість каналів, найбільш ефективне економічно. Ми такого завдання вирішувати не будемо, надаючи все тому ж «нелінивому і цікавому читачеві» придумати приклад і вирішити. Взагалі, вигадування завдань більше розвиває, ніж вирішення поставлених кимось.
^ 2. Одноканальна СМО з необмеженою чергою.На практиці досить часто зустрічаються одноканальні СМО з чергою (лікар, який обслуговує пацієнтів; телефон-автомат з однією будкою; ЕОМ, що виконує замовлення користувачів). Теоретично масового обслуговування одноканальні СМО із чергою також займають особливе місце (саме до таких СМО належить більшість отриманих досі аналітичних формул для немарківських систем). З цієї причини ми приділимо одноканальній СМО із чергою особливу увагу.
Нехай є одноканальна СМО з чергою, на яку не накладено жодних обмежень (ні за довжиною черги, ні за часом очікування). На цю СМО надходить потік заявок з інтенсивністю ; потік обслуговування має інтенсивність μ, зворотну середньому часу обслуговування заявки tпро. Потрібно знайти фінальні ймовірності станів СМО, а також характеристики її ефективності:
Lсист. - середня кількість заявок у системі,
Wсист. - середній час перебування заявки у системі,
^ L оч- середня кількість заявок у черзі,
Wоч - середній час перебування заявки у черзі,
Pзан - ймовірність того, що канал зайнятий (ступінь завантаження каналу).
Щодо абсолютної пропускної спроможності Ата відносною Q,то обчислювати їх немає потреби:
в силу того, що черга необмежена, кожну заявку рано чи пізно буде обслужено, у зв'язку з цим А = λ,з тієї ж причини Q = 1.
Рішення. Стан системи, як і раніше, будемо нумерувати за кількістю заявок, що знаходяться в СМО:
S 0 - канал вільний,
S 1 - канал зайнятий (обслуговує заявку), черги немає,
S 2 - канал зайнятий, одна заявка стоїть у черзі,
S k - канал зайнятий, k - 1 заявок стоять у черзі,
Теоретично кількість станів нічим не обмежена (нескінченно). Граф стан має вигляд, показаний на рис. 20.2. Це - схема загибелі та розмноження, але з нескінченним числом станів. За всіма стрілками потік заявок з інтенсивністю λ переводить систему зліва направо, а праворуч наліво - потік обслуговування з інтенсивністю μ.
Насамперед запитаємо себе, а чи існують у разі фінальні ймовірності? Адже кількість станів системи нескінченна, і, в принципі, при t → ∞черга може необмежено зростати! Так, так воно і є: фінальні ймовірності для такої СМО існують не завжди, а коли система не перевантажена. Можна довести, що якщо ρ менше одиниці (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t→ ∞ росте необмежено. Особливо «незрозумілим» здається даний факт при ρ = 1. Здавалося б, до системи не пред'являється нездійсненних вимог: за час обслуговування однієї заявки приходить в середньому одна заявка, і все має бути в порядку, а ось на ділі - не так. При ρ = 1 СМО справляється з потоком заявок, тільки якщо цей потік - регулярний, і час обслуговування - теж не випадковий, рівний інтервалу між заявками. У цьому «ідеальному» випадку черги в СМО взагалі не буде, канал буде безперервно зайнятий і регулярно випускатиме обслужені заявки. Але варто тільки потоку заявок або потоку обслуговування стати хоча б трохи випадковими - і черга вже зростатиме до нескінченності. На практиці цього не відбувається тільки тому, що «нескінченна кількість заявок у черзі» - абстракція. Ось яких грубих помилок може призвести заміна випадкових величин їх математичними очікуваннями!
Але повернемося до нашої одноканальної СМО із необмеженою чергою. Строго кажучи, формули для фінальних ймовірностей у схемі загибелі та розмноження виводилися нами лише для випадку кінцевого числа станів, але дозволимо собі вільність – скористаємося ними і для нескінченної кількості станів. Підрахуємо фінальні ймовірності станів за формулами (19.8), (19.7). У разі число доданків у формулі (19.8) буде нескінченним. Отримаємо вираз для р 0:
p 0 = -1 =
= (1 + р + р 2 + ... + р k + ....) -1. (20.11)
Ряд у формулі (20.11) є геометричною прогресією. Ми знаємо, що за ρ< 1 ряд сходится - это бесконечно убывающая геометрическая прогрессия со знаменателем р.
Розміщено на реф.
При р ≥ 1 ряд розходиться (що є непрямим, хоч і не суворим доказом того, що фінальні ймовірності станів р 0, p 1, ..., p k, ...існують тільки при р<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем
1 + ρ + ρ 2 + ... + ρ k + ... = ,
p 0 = 1 – ρ. (20.12)
Ймовірності р 1, р 2, ..., р k,... знайдуться за формулами:
p 1 = ρ p 0 , p 2= ρ 2 p 0 ..., p k = ρ p 0, ...,
звідки, з урахуванням (20.12), знайдемо остаточно:
p 1= ρ (1 - ρ), p 2= ρ 2 (1 - ρ), . . . , p k =ρ k(1 - ρ), . . .(20.13)
Як видно, імовірності p 0, p 1, ..., p k , ...утворюють геометричну прогресію зі знаменником нар.
Розміщено на реф.
Як це не дивно, максимальна з них р 0 -ймовірність того, що канал взагалі буде вільний. Як би не була навантажена система з чергою, якщо тільки вона взагалі справляється з потоком заявок (ρ<1), самое вероятное число заявок в системе будет 0.
Знайдемо середню кількість заявок у СМО ^ L сист. . Тут доведеться трохи повозитися. Випадкова величина Z -число заявок у системі - має можливі значення 0, 1, 2, .... k, ...з ймовірностями p 0, р 1, р 2, ..., p k, ...Її математичне очікування одно
Lсист = 0 · p 0 + 1 · p 1 + 2 · p 2 +…+k · p k + ... = (20.14)
(Сума береться не від 0 до ∞, а від 1 до ∞, так як нульовий член дорівнює нулю).
Підставимо у формулу (20.14) вираз для p k (20.13):
Lсист. = 
Тепер винесемо за знак суми ρ (1-ρ):
Lсист. = ρ (1-ρ)
Тут ми знову застосуємо «маленьку хитрість»: kρ k-1 є не що інше, як похідна по ρ від вираження ρ k; значить,
Lсист. = ρ (1-ρ)
Змінюючи місцями операції диференціювання підсумування, отримаємо:
Lсист. = ρ (1-ρ) (20.15)
Але сума у формулі (20.15) є не що інше, як сума нескінченно спадної геометричної прогресії з першим членом і знаменником; ця сума
дорівнює , а її похідна .Підставляючи цей вираз в (20.15), отримаємо:
Lсист = . (20.16)
Ну, а тепер застосуємо формулу Літтла (19.12) та знайдемо середній час перебування заявки в системі:
Wсист = (20.17)
Знайдемо середню кількість заявок у черзі Lоч. Будемо міркувати так: кількість заявок у черзі дорівнює кількості заявок у системі мінус кількість заявок, що знаходяться під обслуговуванням. Значить (за правилом складання математичних очікувань), середня кількість заявок у черзі Lоч дорівнює середньому числу заявок у системі Lсист мінус середня кількість заявок під обслуговуванням. Число заявок під обслуговуванням має бути або нулем (якщо канал вільний), або одиницею (якщо він зайнятий). Математичне очікування такої випадкової величини дорівнює ймовірності того, що канал зайнятий (ми її позначили Рзан). Очевидно, Рзан одно одиниці мінус ймовірність р 0того, що канал вільний: L зовнішній і середній час цього очікування Wзовніш (дві останні величини пов'язані формулою Літтла). Нарешті, знайдіть сумарний добовий штраф Ш, який доведеться заплатити станції за простої складів на зовнішніх шляхах, якщо за одну годину простою одного складу станція сплачує штраф (руб.). Про всяк випадок повідомляємо відповіді: Lсист. = 2 (склад), Wсист. = 1 (година), Lоч = 4/3 (склад), Wоч = 2/3 (години), Lзовніш = 16/27 (склад), Wзовніш = 8/27 ≈ 0,297 (години). Середній добовий штраф за очікування складів на зовнішніх шляхах отримаємо, перемножуючи середню кількість складів, що прибувають на станцію за добу, середній час очікування складу на зовнішніх шляхах і часовий штраф а: Ш ≈ 14,2 а.
^ 3. re-канальна СМО з необмеженою чергою.Абсолютно аналогічно задачі 2, але трохи складніше, вирішується задача про n-канальної СМО з необмеженою чергою Нумерація станів - знову за кількістю заявок, що у системі:
N<1. В случае если ρ/n≥ 1, черга зростає до безкінечності.
Припустимо, що умова ρ/ n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для р 0буде стояти ряд членів, що містять факторіали, плюс сума нескінченно спадної геометричної прогресії зі знаменником ρ/ n. Підсумовуючи її, знайдемо
(20.22)
Тепер знайдемо характеристики ефективності СМО. З них найлегше перебуває середня кількість зайнятих каналів k== λ/μ, = ρ (це взагалі справедливо для будь-якої СМО з необмеженою чергою). Знайдемо середню кількість заявок у системі Lсист та середня кількість заявок у черзі Lоч. З них легше вирахувати друге, за формулою
Lоч =
виконуючи відповідні перетворення за зразком задачі 2
(з диференціюванням ряду), отримаємо:
Lоч = 
(20.23)
Додаючи до нього середню кількість заявок під обслуговуванням (воно ж - середня кількість зайнятих каналів) k =ρ, отримаємо:
Lсист = Lоч + ρ. (20.24)
Для висловлювання для Lоч і Lсист на λ , за формулою Літтла отримаємо середні часи перебування заявки у черзі та в системі:
(20.25)
А тепер вирішимо цікавий приклад.
Розміщено на реф.
Залізнична каса з продажу квитків з двома віконками є двоканальною СМО з необмеженою чергою, що встановлюється відразу до двох вікон (якщо одне віконце звільняється, найближчий у черзі пасажир його займає). Каса продає квитки у два пункти: А та Ст.Інтенсивність потоку заявок (пасажирів, які бажають купити квиток) для обох пунктів А і Воднакова: λ А = λ В = 0,45 (пасажира за хвилину), а у сумі вони утворюють загальний потік заявок з інтенсивністю λ А +
λ В = 0,9. Касир витрачає обслуговування пасажира загалом дві хвилини. Досвід показує, що біля каси накопичуються черги, пасажири скаржаться на повільність обслуговування. Надійшла раціоналізаторська пропозиція: замість однієї каси, що продає квитки і в Аі в В,створити дві спеціалізовані каси (по одному віконце в кожному), що продають квитки одна - тільки в пункт А, інша - тільки до пункту Ст.Розумність цієї пропозиції викликає суперечки – дехто стверджує, що черги залишаться незмінними. Потрібно перевірити корисність пропозиції розрахунком. Так як ми вміємо вважати характеристики тільки для найпростіших СМО, припустимо, що всі потоки подій - найпростіші (на якісній стороні висновків це не позначиться).
Ну що ж, візьмемося до справи. Розглянемо два варіанти організації продажу квитків – існуючий та пропонований.
Варіант I (існуючий). На двоканальну СМО надходить потік заявок з інтенсивністю = 0,9; інтенсивність потоку обслуговування μ = 1/2 = 0,5; ρ = λ/μ = l,8. Оскільки ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим р 0 ≈ 0,0525. Середнє число заявок у черзі знаходимо за формулою (20.23): L оч ≈ 7,68; середній час, що проводиться заявкою в черзі (за першою із формул (20.25)), дорівнює Wоч ≈ 8,54 (хв.).
Варіант II (пропонований). Треба розглянути дві одноканальні СМО (два спеціалізовані вікна); на кожну надходить потік заявок з інтенсивністю = 0,45; μ . як і дорівнює 0,5; ρ = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) Lоч = 8,1.
Ось тобі й раз! Довжина черги, виявляється, не лише не зменшилась, а збільшилась! Можливо, зменшився середній час очікування у черзі? Подивимося. Ділячи Lоч на λ = 0,45, отримаємо Wоч ≈ 18 (хвилин).
Ось так раціоналізація! Замість зменшитися, і середня довжина черги, і середній час очікування в ній збільшилися!
Спробуймо здогадатися, чому так сталося? Розкинувши мізками, приходимо до висновку: сталося це тому, що в першому варіанті (двоканальна СМО) менша середня частка часу, яку простоює
Приклади вирішення завдань систем масового обслуговування – поняття та види. Класифікація та особливості категорії "Приклади розв'язання задач систем масового обслуговування" 2017, 2018.
Розглянутий у попередній лекції марківський випадковий процес з дискретними станами та безперервним часом має місце у системах масового обслуговування (СМО).
Системи масового обслуговування - це такі системи, в які у випадкові моменти часу надходять заявки на обслуговування, при цьому заявки, що надійшли, обслуговуються за допомогою наявних у розпорядженні системи каналів обслуговування.
Прикладами систем масового обслуговування можуть бути:
- розрахунково-касові вузли у банках, на підприємствах;
- персональні комп'ютери, які обслуговують заявки, що надходять, або вимоги на вирішення тих чи інших завдань;
- станції технічного обслуговування автомобілів; АЗС;
- аудиторські фірми;
- відділи податкових інспекцій, що займаються прийманням та перевіркою поточної звітності підприємств;
- телефонні станції тощо.
Вузли |
Вимоги |
|
Лікарня |
Санітари |
Пацієнти |
Виробництво |
||
Аеропорт |
Виходи на злітно-посадкові смуги Пункти реєстрації |
Пасажири |
Розглянемо схему роботи СМО (рис. 1). Система складається з генератора заявок, диспетчера та вузла обслуговування, вузла обліку відмов (термінатора, знищувача заявок). Вузол обслуговування у випадку може мати кілька каналів обслуговування.
Рис. 1
- Генератор заявок - Об'єкт, що породжує заявки: вулиця, цех із встановленими агрегатами. На вхід надходить потік заявок(Потік покупців у магазин, потік агрегатів, що зламалися (машин, верстатів) на ремонт, потік відвідувачів у гардероб, потік машин на АЗС і т. д.).
- Диспетчер – людина або пристрій, який знає, що робити із заявкою. Вузол, що регулює та направляє заявки до каналів обслуговування. Диспетчер:
- приймає заявки;
- формує чергу, якщо всі канали зайняті;
- спрямовує їх до каналів обслуговування, якщо є вільні;
- дає заявкам відмову (з різних причин);
- приймає інформацію від вузла обслуговування про вільні канали;
- стежить за часом роботи системи.
- Черга - Накопичувач заявок. Черга може бути відсутня.
- Вузол обслуговування складається із кінцевого числа каналів обслуговування. Кожен канал має 3 стани: вільний, зайнятий, не працює. Якщо всі канали зайняті, можна придумати стратегію, кому передавати заявку.
- Відмова від обслуговування настає, якщо всі канали зайняті (деякі навіть можуть працювати).
Крім цих основних елементів СМО в деяких джерелах виділяються також такі складові:
термінатор – знищувач трансактів;
склад – накопичувач ресурсів та готової продукції;
рахунок бухгалтерського обліку – до виконання операцій типу «проводка»;
менеджер – розпорядник ресурсів;
Класифікація СМО
Перший поділ (за наявності черг):
- СМО із відмовими;
- СМО із чергою.
У СМО з відмовамизаявка, що надійшла в момент, коли всі канали зайняті, отримує відмову, залишає СМО і надалі не обслуговується.
У СМО з чергоюзаявка, що прийшла в момент, коли всі канали зайняті, не йде, а стає в чергу і чекає на можливість бути обслуженою.
СМО із чергамиподіляються на різні види залежно від того, як організовано чергу, – обмежена або не обмежена. Обмеження можуть стосуватися як довжини черги, так і часу очікування, дисципліни обслуговування.
Отже, наприклад, розглядаються такі СМО:
- СМО з нетерплячими заявками (довжина черги та час обслуговування обмежений);
- СМО з обслуговуванням з пріоритетом, тобто деякі заявки обслуговуються позачергово і т.д.
Типи обмеження черги можуть бути комбінованими.
Інша класифікація поділяє СМО за джерелом заявок. Породжувати заявки (вимоги) може сама система або якесь зовнішнє середовище, що існує незалежно від системи.
Природно, потік заявок, породжений системою, залежатиме від системи та її стану.
Крім цього СМО діляться на відкритіСМО та замкнутіСМО.
У відкритій СМО характеристики потоку заявок не залежить від того, в якому стані сама СМО (скільки каналів зайнято). У замкнутій СМО – залежать. Наприклад, якщо один робітник обслуговує групу верстатів, іноді потребують налагодження, то інтенсивність потоку «вимог» з боку верстатів залежить від того, скільки на них вже справно і чекає налагодження.
Приклад замкнутої системи: видача касиром зарплати для підприємства.
За кількістю каналів СМО поділяються на:
- одноканальні;
- багатоканальні.
Характеристики системи масового обслуговування
Основними характеристиками системи масового обслуговування будь-якого виду є:
- вхідний потік вимог чи заявок на обслуговування;
- дисципліна черги;
- Механізм обслуговування.
Вхідний потік вимог
Для опису вхідного потоку потрібно задати ймовірнісний закон, що визначає послідовність моментів надходження вимог на обслуговування,та вказати кількість таких вимог у кожному черговому надходженні. У цьому, зазвичай, оперують поняттям «імовірнісний розподіл моментів надходження вимог». Тут можуть діяти як поодинокі, і групові вимоги (кількість таких вимог у кожному черговому вступі). У разі зазвичай йдеться про систему обслуговування з паралельно-груповим обслуговуванням.
А і– час надходження між вимогами – незалежні однаково розподілені випадкові величини;
E(A)- Середнє (МО) час надходження;
λ=1/E(A)- Інтенсивність надходження вимог;
Характеристики вхідного потоку:
- Імовірнісний закон, визначальний послідовність моментів надходження вимог обслуговування.
- Кількість вимог у кожному черговому надходженні для групових потоків.
Дисципліна черги
Черга - Сукупність вимог, що очікують обслуговування.
Черга має ім'я.
Дисципліна черги визначає принцип, відповідно до якого вимоги, що надходять на вхід обслуговуючої системи, підключаються з черги до процедури обслуговування. Найчастіше використовуються дисципліни черги, що визначаються такими правилами:
- першим прийшов – перший обслуговуєшся;
First in First out (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) буде більшою; чого й слід було чекати. За формулою можна знайти і менш очевидний факт: перевантаження також збільшується, коли мінливість розподілу часу обслуговування зростає, навіть якщо середній час обслуговування залишається незмінним. Інтуїтивно це можна пояснити так: дисперсія випадкової величини часу обслуговування може прийняти велике значення (оскільки вона має бути позитивною), тобто єдиний пристрій обслуговування буде зайнятий тривалий час, що призведе до збільшення черги.
Предметом теорії масового обслуговуванняє встановлення залежності між факторами, що визначають функціональні можливості системи масового обслуговування, та ефективністю її функціонування. У більшості випадків усі параметри, що описують системи масового обслуговування, є випадковими величинами або функціями, тому ці системи відносяться до стохастичних систем.
Випадковий характер потоку заявок (вимог), а також, у випадку, і тривалості обслуговування призводить до того, що у системі масового обслуговування відбувається випадковий процес. За характером випадкового процесу , що відбувається в системі масового обслуговування (СМО), розрізняють системи марківські та немарківські . У марківських системах вхідний потік вимог і потік обслужених вимог (заявок), що виходить, є пуассонівськими. Пуассонівські потоки дозволяють легко описати та побудувати математичну модель системи масового обслуговування. Ці моделі мають досить прості рішення, тому більшість відомих додатків теорії масового обслуговування використовують марківську схему. У разі немарківських процесів завдання дослідження систем масового обслуговування значно ускладнюються та вимагають застосування статистичного моделювання, чисельних методів з використанням ЕОМ.
Завантаження...