Тема. Теорія систем масового обслуговування.

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

Класифікація СМО щодо способу обробки вхідного потоку заявок.

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

З відмовами

(без черги)

З чергою

Необмежена черга

Обмежена черга

З пріоритетом

У порядку надходження

Відносний пріоритет

Абсолютний пріоритет

За часом обслуговування

По довжині черги

Класифікація за способом функціонування:

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

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

Багатоканальна СМО з очікуванням

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

Стан системи нумерується за кількістю заявок, пов'язаних системою:

немає черги:

- всі канали вільні;

- зайнятий один канал, інші вільні;

- зайняті -каналів, решта немає;

- зайняті всі -каналів, вільних немає;

є черга:

- зайняті всі n-каналів; одна заявка стоїть у черзі;

- зайняті всі n-каналів, r-заявок у черзі;

- зайняті всі n-каналів, r-заявок у черзі.

ДСП наведено на рис. 9. У кожної стрілки проставлено відповідні інтенсивності потоків подій. За стрілками зліва направо систему завжди переводить один і той же потік заявок з інтенсивністю , за стрілками справа наліво систему переводить потік обслуговування, інтенсивність якого дорівнює , помноженому на кількість зайнятих каналів

Рис. 9. Багатоканальна СМО з очікуванням

Ймовірність відмови.

(29)

Відносна пропускна здатність доповнює можливість відмови до одиниці:

Абсолютна пропускна здатність СМО:

(30)

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

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

(31)

де .

Тут знову (вираз у дужках) зустрічається похідна суми геометричній прогресії(див. вище (23), (24) - (26)), використовуючи співвідношення для неї, отримуємо:

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

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

(32)

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

.

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

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

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

Ймовірність відмови

Середню кількість заявок у черзі отримаємо при з (31):

,

а середній час очікування – з (32): .

Середня кількість заявок .

приклад 2. Автозаправна станція з двома колонками (n = 2) обслуговує потік машин з інтенсивністю =0,8 (машин на хвилину). Середній час обслуговування однієї машини:

У даному районі немає іншої АЗС, тож черга машин перед АЗС може рости практично необмежено. Знайти властивості СМО.

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

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

Пуасонівський «потік доглядів» з інтенсивністю:

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

немає черги:

- всі канали вільні;

- зайнятий один канал;

- зайняті два канали;

- зайняті всі n-каналів;

є черга:

- зайняті всі n-каналів, одна заявка стоїть у черзі;

- зайняті всі n-каналів, r-заявок стоять у черзі і т.д.

Граф станів та переходів системи показаний на рис. 10.

Рис. 10. СМО з обмеженим часом очікування

Розмітимо цей граф, як і раніше; у всіх стрілок, що ведуть зліва направо, стоятиме інтенсивність потоку заявок . Для станів без черги у стрілок, що ведуть з них справа наліво, буде, як і раніше, стояти сумарна інтенсивність потоку обслуговування всіх зайнятих каналів. Що стосується станів з чергою, то у стрілок, що ведуть з них справа наліво, стоятиме сумарна інтенсивність потоку обслуговування всіх n-каналів плюс відповідна інтенсивність потоку відходів із черги. Якщо в черзі стоять r-заявок, то сумарна інтенсивність потоку доглядів дорівнюватиме .

Середня кількість заявок у черзі: (35)

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

Середня кількість зайнятих каналів як і раніше отримуємо, ділячи абсолютну пропускну здатність А на Замкнуті СМО

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

У замкнутій СМО циркулює одне й те саме кінцеве число потенційних вимог. Поки потенційна вимога не реалізувалася як вимога на обслуговування, вважається, що вона знаходиться у блоці затримки. У момент реалізації воно надходить у саму систему. Наприклад, робітники обслуговують групу верстатів. Кожен верстат є потенційною вимогою, перетворюючись на реальне на момент своєї поломки. Поки верстат працює, він знаходиться у блоці затримки, а з моменту поломки до моменту закінчення ремонту – у самій системі. Кожен робітник є каналом обслуговування. = =P 1 + 2 P 2 +…+(n- 1 )P n- 1 +n( 1 -P На вхід триканальної СМО з відмовами надходить потік заявок з інтенсивністю =4 заявки за хвилину, час обслуговування заявки одним каналомt обсл=1/μ =0,5 хв. Чи вигідно з точки зору пропускної спроможності СМО змусити всі три канали обслуговувати заявки відразу, причому середній час обслуговування зменшується втричі? Як це позначиться на середньому часі перебування заявки до СМО?

Приклад 2 . /μ=2, ρ/n =2/3<1.

Завдання 3:

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

Знайдіть середню частку вільного часу кожного робочого і середній час роботи верстата.

Знайдіть ті ж характеристики для системи, в якій:

а) за кожним робітником закріплено два верстати;

б) два робочі завжди обслуговують верстат разом, причому з подвійною інтенсивністю;

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

Приклади розв'язання задач систем масового обслуговування

Потрібно розв'язати задачі 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того, що канал вільний:

Рзан = 1 - р 0 = ρ. (20.18)

Отже, середня кількість заявок під обслуговуванням дорівнює

^ L про= ρ, (20.19)

Lоч = Lсист - ρ =

та остаточно

Lоч = (20.20)

За формулою Літтла (19.13) знайдемо середній час перебування заявки у черзі:

(20.21)

Таким чином, усі характеристики ефективності СМО знайдені.

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

складу триває випадковий (показовий) час із середнім значенням t про = 20(мін.). У парку прибуття станції є два шляхи, на яких можуть очікувати обслуговування склади, що прибувають; якщо обидва шляхи зайняті, склади змушені чекати зовнішніх шляхах. Потрібно знайти (для граничного, стаціонарного режиму роботи станції): середня кількість складів lсист, пов'язаних зі станцією, середній час Wсистема перебування складу при станції (на внутрішніх шляхах, на зовнішніх шляхах і під обслуговуванням), середня кількість Lоч складів, що чекають черги на розформування (все одно, на яких шляхах), середній час Wоч перебування складу черги. Крім того, спробуйте знайти середню кількість складів, що очікують на розформування на зовнішніх шляхах. 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-канальної СМО з необмеженою чергою Нумерація станів - знову за кількістю заявок, що у системі:

S 0- у СМО заявок немає (всі канали вільні),

S 1 -зайнятий один канал, інші вільні,

S 2 -зайнято два канали, інші вільні,

S k- зайнято kканалів, інші вільні,

S n- зайняті всі пканалів (черги немає),

S n+1- зайняті всі nканалів, одна заявка стоїть у черзі,

S n+r -зайняті вага пканалів, rзаявок стоїть у черзі,

Граф станів показано на рис. 20.3. Пропонуємо читачеві самому обміркувати та обґрунтувати значення інтенсивностей, проставлених у стрілок. Граф рис. 20.3

λ λ λ λ λ λ λ λ λ

μ 2μ kμ (k+1)μ nμ nμ nμ nμ 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 (хвилин).

Ось так раціоналізація! Замість того, щоб зменшитися, і середня довжина черги, і середній час очікування у ній збільшилися!

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

Ну , добре, - готовий погодитися читач, - збільшення можна пояснити, але чому воно таке суттєве? Чи немає тут помилок у розрахунку?

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

Таким чином, що здається спочатку парадоксальним (або навіть просто невірним) результат обчислень виявляється на перевірку правильним і зрозумілим.

Такі парадоксальними висновками, причина яких аж ніяк не очевидна, багата теорія масового обслуговування. Автору самому неодноразово доводилося «дивуватися» результатам розрахунків, які потім виявлялися правильними.

Розмірковуючи над останнім завданням, читач може порушити питання так: адже якщо каса продає квитки лише в один пункт, то, природно, час обслуговування має зменшитися, ну, не вдвічі, а хоч скільки-небудь, а ми вважали, що воно як і раніше в середньому дорівнює 2 (хв.). Пропонуємо такому прискіпливому читачеві відповісти на запитання: а наскільки треба його зменшити, щоб «раціоналізаторська пропозиція» стала вигідною? Знову ми зустрічаємося хоч і з елементарною, але все ж таки завданням оптимізації. За допомогою орієнтовних розрахунків навіть на найпростіших, марківських моделях вдається прояснити якісну сторону явища – як вигідно чинити, а як – невигідно. У наступному параграфі ми познайомимося з деякими елементарними немарківськими моделями, які розширять наші можливості.

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

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

Потрібно знайти фінальні ймовірності станів (до речі, вони в цьому завданні існують за будь-якого ρ - адже число станів звичайно), ймовірність відмови Рвідк, абсолютну пропускну здатність А,ймовірність того, що канал зайнятий Рзан, середню довжину черги Lоч, середня кількість заявок до СМО Lсист , середній час очікування у черзі Wоч , середній час перебування заявки до СМО Wсист. При обчисленні показників черги можна скористатися тим самим прийомом, який ми застосовували в задачі 2, з тією різницею, що підсумовувати треба не нескінченну прогресію, а кінцеву.

^ 5. Замкнена СМО з одним каналом і mджерелами заявок.Для конкретності поставимо завдання у наступній формі: один робітник обслуговує тверстатів, кожен з яких іноді вимагає налагодження (виправлення). Інтенсивність потоку вимог кожного працюючого верстата дорівнює λ . Якщо верстат вийшов з ладу в момент, коли робітник вільний, він одразу надходить на обслуговування. Якщо він вийшов з ладу в момент, коли робітник зайнятий, він стає в чергу і чекає, поки робітник звільниться. Середній час налагодження верстата tпро = 1/μ. Інтенсивність потоку заявок, що надходять до робітника, залежить від того, скільки верстатів працює. Якщо працює kверстатів, вона дорівнює kλ. Знайти фінальні ймовірності станів, середню кількість працюючих верстатів та ймовірність того, що робітник буде зайнятий.

Зауважимо, що і в цій СМО фінальні ймовірності

існуватимуть за будь-яких значень λ і μ = 1/ tпро, оскільки кількість станів системи звичайно.

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

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

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

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

Система масового обслуговування (СМО)– це модель, що включає: 1) випадковий потік вимог, викликів або клієнтів, які потребують обслуговування; 2) алгоритм здійснення цього обслуговування; 3) канали (прилади) обслуговування.

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

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

Головна особливість завдань даного класу – явна залежність результатів аналізу та одержуваних рекомендацій від двох зовнішніх факторів: частоти надходження та складності замовлень (а значить і часу їх виконання).

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

В якості характеристик СМОрозглядаються:

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

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

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

Кожну СМО може характеризувати виразом: (a / b / c) : (d / e / f) , де

a - розподіл вхідного потоку заявок;

b - Розподіл вихідного потоку заявок;

c - Конфігурація обслуговуючого механізму;

d – дисципліна черги;

e – блок очікування;

f - Ємність джерела.

Тепер докладніше розглянемо кожну характеристику.

Вхідний потік заявок– кількість заявок, що надійшли в систему. Характеризується інтенсивністю вхідного потоку l.

Вихідний потік заявок– кількість обслуговуваних системою заявок. Характеризується інтенсивністю вихідного потоку m.

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

1. один каналобслуговування (одна злітно-посадкова смуга, один продавець);
2. один канал обслуговування, що включає кілька послідовних вузлів(їдальня, поліклініка, конвеєр);
3. кілька однотипних каналівобслуговування, з'єднані паралельно (АЗС, довідкова служба, вокзал).

Таким чином, можна виділити одно-і багатоканальні СМО.

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

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

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

1. ПЕРППО (першим прийшов – першим обслуговуєшся) – найпоширеніший тип;
2. ПОСППО (останнім прийшов – першим обслуговуєшся);
3. СОЗ (випадковий відбір заявок) – із банку даних.
4. ПР – обслуговування із пріоритетом.

Довжина чергиможе бути

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

Блок очікування- «Місткість» системи - загальна кількість заявок, що знаходяться в системі (у черзі та на обслуговуванні). Таким чином, е=з+d.

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

Кількість моделей СМО відповідає числу всіляких поєднань цих компонентів.

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

З кожним відрізком часу [ a, a+ T ], зв'яжемо випадкову величину Х, що дорівнює кількості вимог, що надійшли в систему за час Т.

Потік вимог називається стаціонарнимякщо закон розподілу не залежить від початкової точки проміжку а, а залежить тільки від довжини цього проміжку Т. Наприклад, потік заявок на телефонну станцію протягом доби ( Т= 24 години) не можна вважати стаціонарним, а ось з 13 до 14 годин ( Т= 60 хвилин) – можна.

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

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

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

Основна теорема.Якщо потік найпростіший, то с.в. Х [a. a + T] розподілено згідно із законом Пуассона, тобто. .

Наслідок 1. Найпростіший потік також називається пуассонівським.

Наслідок 2. M(X)= M(Х [ a , a + T ] )= lT, тобто. за час Т lTзаявок. Отже, за одну одиницю часу в систему надходить у середньому lзаявок. Ця величина і називається інтенсивністювхідного потоку.

Розглянемо ПРИКЛАД .

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

Рішення.

За умовою завдання, l=3, Т=2 дні, вхідний потік пуасонівський, n ³5. при рішенні зручно запровадити протилежну подію, яка полягає в тому, що за час Тнадійде менше 5 заявок. Отже, за формулою Пуассона, отримаємо

^

3.3 Стан системи. Матриця та графік переходів.

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

Е 0 - Всі канали вільні;

Е 1 – зайнятий один канал;

Е n– зайняті всі канали;

Е n +1 – зайняті всі канали та одна заявка у черзі;

Е n + m– зайняті всі канали та всі місця в черзі.

Аналогічна система з відмовами може перебувати у станах E 0 – E n .

Для СМО з чистим очікуванням існує безліч станів. Таким чином, стан E n СМО на момент часу t – це кількість n заявок (вимог), що у системі на даний час, тобто. n= n(t) - випадкова величина, E n (t) – результати цієї випадкової величини, а P n (t) - Імовірність перебування системи в стані E n .

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

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

Малюнок 3.1 – граф переходів

Упоряд.	Е 0	Е 1	Е 2
Е 0	Р 0,0	Р 0,1	Р 0,2
Е 1	Р 1,0	Р 1,1	Р 1,2
Е 2	Р 2,0	Р 2,2	Р 2,2

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

Оскільки система обов'язково перейде з одного

стану в інше, то сума ймовірностей у кожному рядку завжди дорівнює одиниці.

3.4 Одноканальні СМО.

3.4.1 Одноканальні СМО з відмовами.

Розглянемо системи, що задовольняють вимогам:

(Р/Е/1):(–/1/¥) . Припустимо також, що час обслуговування вимоги не залежить від кількості вимог, що надійшли до системи. Тут і далі «Р» означає, що вхідний потік розподілено згідно із законом Пуассона, тобто. Найпростіший «Е» означає, що вихідний потік розподілений за експоненційним законом. Також тут і надалі основні формули даються без доказів.

Для такої системи можливі два стани: Е 0 – система вільна та Е 1 - Система зайнята. Складемо матрицю переходів. Візьмемо Dt- Безмежно малий проміжок часу. Нехай подія А полягає в тому, що в систему за час Dtнадійшла одна вимога. Подія полягає в тому, що за час Dtобслуговано одну вимогу. Подія А i , k- за час Dtсистема перейде зі стану E iу стан E k. Так як l- Інтенсивність вхідного потоку, то за час Dtу систему в середньому надходить l*Dtвимог. Тобто, ймовірність надходження однієї вимоги Р(А)=l* Dt, а ймовірність протилежної події Р(?)=1-l*Dt.Р(В)=F(Dt)= P(b< D t)=1- e - m D t = m Dt– можливість обслуговування заявки за час Dt. Тоді А 00 – заявка не надійде чи надійде, але буде обслужена. А 00 = + А * Ст Р 00 =1 - l*Dt. (ми врахували, що (Dt) 2 – нескінченно мала величина)

А 01 – заявка надійде, але не буде обслуговано. А 01 = А * . Р 01 = l*Dt.

А 10 – заявку буде обслуговано і новою не буде. А 10 = * Ā. Р 10 = m*Dt.

А 11 – заявка не буде обслужена або надійде нова, яка ще не обслужена. А 11 = +У * А. Р 01 = 1- m*Dt.

Таким чином, отримаємо матрицю переходів:

Упоряд.	Е 0	Е 1
Е 0	1-l * Dt	l * Dt
Е 1	m * Dt	1-m * Dt

Імовірність простою та відмови системи.

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

Асимптотою графіка є пряма
.

Очевидно, починаючи з певного моменту t,

1

Малюнок 3.2

Остаточно отримаємо, що
і
, де р 1 (t) - Імовірність того, що в момент часу t система зайнята (тобто перебуває в стані Е 1 ).

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

Стаціонарний режим роботи та коефіцієнт завантаження системи.

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

На автомийці один блок обслуговування. Автомобілі прибувають за пуассонівським розподілом з інтенсивністю 5 авто/год. Середній час обслуговування однієї машини – 10 хвилин. Знайти ймовірність того, що автомобіль, що під'їхав, знайде систему зайнятої, якщо СМО працює в стаціонарному режимі.

Рішення.За умовою завдання, l=5, m y =5/6. Потрібно знайти ймовірність р 1 - Імовірність відмови системи.
.

3.4.2 Одноканальні СМО з необмеженою довжиною черги.

Розглянемо системи, що задовольняють вимогам: (Р/Е/1):(d/¥/¥). Система може бути в одному зі станів E 0 , …, E k, … Аналіз показує, що через деякий час така система починає працювати в стаціонарному режимі, якщо інтенсивність вихідного потоку перевищує інтенсивність вхідного потоку (тобто коефіцієнт завантаження системи менше одиниці). Враховуючи цю умову, отримаємо систему рівнянь

вирішуючи яку знайдемо, що . Таким чином, за умови, що y<1, получим
Звісно,
і
- Імовірність знаходження СМО в стані Е kу випадковий час.

Середні показники системи.

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

• n – кількість вимог, які перебувають у СМО (у черзі та на обслуговуванні);
• v - Довжину черги;
• w - Час очікування початку обслуговування;
• w 0 – загальний час перебування у системі.

Нас цікавитимуть середні характеристики(Тобто беремо математичне очікування від аналізованих випадкових величин, і пам'ятаємо, що y<1).

– середня кількість заявок у системі.

- Середня довжина черги.

– середній час очікування початку обслуговування, тобто. час очікування у черзі.

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

На автомийці є один блок для обслуговування і є місце для черги. Автомобілі прибувають за пуассонівським розподілом з інтенсивністю 5 авто/год. Середній час обслуговування однієї машини – 10 хвилин. Знайти усі середні характеристики СМО.

Рішення. l=5, m= 60хв/10хв = 6. Коефіцієнт завантаження y =5/6. Тоді середня кількість автомобілів у системі
, середня довжина черги
, середній час очікування початку обслуговування
години = 50 хв, і, нарешті, середній час перебування у системі
годину.

3.4.3 Одноканальні СМО змішаного типу.

Припустимо, що довжина черги становить mвимог. Тоді для будь-кого s£ m, ймовірність перебування СМО може Е 1+ s, обчислюється за формулою
, тобто. одна заявка обслуговується та ще sзаявок – у черзі.

Імовірність простою системи дорівнює
,

а ймовірність відмови системи -
.

Дано три одноканальні системи, для кожної l=5, m =6. Але перша система – з відмовами, друга – з чистим очікуванням, а третя – з обмеженою довжиною черги, m=2. Знайти та порівняти ймовірності простою цих трьох систем.

Рішення.Для всіх систем коефіцієнт завантаження y=5/6. Для системи з відмовами
. Для системи з чистим очікуванням
. Для системи з обмеженою довжиною черги
. Висновок очевидний: чим більше заявок перебуває в черзі, тим менша ймовірність простою системи.

3.5 Багатоканальні СМО.

3.5.1 Багатоканальні СМО з відмовами.

Розглянемо системи (Р/Е/s):(-/s/¥) у припущенні, що час обслуговування не залежить від вхідного потоку і всі лінії працюють незалежно. Багатоканальні системи, крім коефіцієнта завантаження, можна також характеризувати коефіцієнтом
, де s- Число каналів обслуговування. Досліджуючи багатоканальні СМО, отримаємо такі формули (формули Ерланга) для ймовірності знаходження системи в стані Е kу випадковий момент часу:

, k = 0, 1, …

функція вартості.

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

Для пошуку оптимального варіанта треба знайти (і це можна зробити) мінімальне значення функції вартості: С(s) = с 1* l * p s +с 2*, графік якої представлений малюнку 3.3:

Малюнок 3.3

Пошук мінімального значення функції вартості полягає в тому, що ми знаходимо її значення спочатку для s =1, потім для s =2, потім для s =3, і т.д. до тих пір, поки на якомусь кроці значення функції С( s) не стане більше попереднього. Це означає, що функція досягла свого мінімуму і почала зростати. Відповіддю буде те число каналів обслуговування (значення s), для якого функція вартості мінімальна.

ПРИКЛАД .

Скільки ліній обслуговування має містити СМО з відмовами, якщо l= 2треб / год, m=1треб/час, штраф за кожну відмову становить 7 тис.руб., вартість простою однієї лінії – 2 тис.руб. в годину?

Рішення. y = 2/1=2. з 1 =7, з 2 =2.

Припустимо, що СМО має два канали обслуговування, тобто. s =2. Тоді
. Отже, С(2) = с 1 *l*p 2 +с 2 *(2- y*(1-р 2 )) = =7*2*0.4+2*(2-2*0.6)=7.2.

Припустимо, що s =3. Тоді
, С(3) = с 1 *l*p 3 +с 2 *
=5.79.

Припустимо, що є чотири канали, тобто. s =4. Тоді
,
, С(4) = с 1 *l*p 4 +с 2 *
=5.71.

Припустимо, що СМО має п'ять каналів обслуговування, тобто. s =5. Тоді
, С(5) = 6.7 – більше за попереднє значення. Отже, оптимальна кількість каналів обслуговування – чотири.

3.5.2 Багатоканальні СМО з чергою.

Розглянемо системи (Р/Е/s):(d/d+s/¥) у припущенні, що час обслуговування не залежить від вхідного потоку і всі лінії працюють незалежно. Говоритимемо, що в системі встановився стаціонарний режим роботи, Якщо середня кількість вимог, що надходять менше середнього числа вимог, обслужених на всіх лініях системи, тобто. l

P(w>0) - Імовірність очікування початку обслуговування,
.

Остання характеристика дозволяє вирішувати задачу про визначення оптимального числа каналів обслуговування з таким розрахунком, щоб ймовірність очікування початку обслуговування була меншою від заданого числа. Для цього достатньо прорахувати ймовірність очікування послідовно при s =1, s =2, s=3 тощо.

ПРИКЛАД .

СМО – станція швидкої допомоги невеликого мікрорайону. l=3 виклику на годину, а m= 4 виклики на годину для однієї бригади. Скільки бригад необхідно мати на станції, щоб ймовірність очікування виїзду була меншою за 0.01?

Рішення.Коефіцієнт завантаження системи y =0.75. Припустимо, що є дві бригади. Знайдемо ймовірність очікування початку обслуговування при s =2.
,
.

Припустимо наявність трьох бригад, тобто. s=3. За формулами отримаємо, що р 0 =8/17, Р(w>0)=0.04>0.01 .

Припустимо, що у станції чотири бригади, тобто. s=4. Тоді отримаємо, що р 0 =416/881, Р(w>0)=0.0077<0.01 . Отже, на станції має бути чотири бригади.

3.6 Запитання для самоконтролю

1. Предмет та завдання теорії масового обслуговування.
2. СМО, їх моделі та позначення.
3. Вхідний потік вимог. Інтенсивність вхідного потоку.
4. Стан системи. Матриця та графік переходів.
5. Одноканальні СМО з відмовами.
6. Одноканальні СМО з чергою. Характеристики.
7. Стаціонарний режим роботи. Коефіцієнт завантаження системи.
8. Багатоканальні СМО з відмовами.
9. Оптимізація функції вартості.
10. Багатоканальні СМО із чергою. Характеристики.

3.7 Вправи для самостійної роботи

1. Закусочна на АЗС має один прилавок. Автомобілі прибувають відповідно до пуассонівського розподілу, в середньому 2 автомобілі за 5 хвилин. Для виконання замовлення в середньому достатньо 1,5 хвилини, хоча тривалість обслуговування розподілена за експоненційним законом. Знайти: а) можливість простою прилавка; b) середні показники; c) ймовірність того, що кількість автомобілів, що прибули, буде не менше 10.
2. Рентгенівський апарат дозволяє обстежити в середньому 7 осіб на годину. Інтенсивність відвідувачів складає 5 осіб на годину. Припускаючи стаціонарний режим роботи, визначити середні показники.
3. Час обслуговування в СМО підпорядковується експоненційному закону,
   m = 7вимог на годину. Знайти ймовірність того, що: а) час обслуговування знаходиться в інтервалі від 3 до 30 хвилин; b) вимога буде обслужена протягом однієї години. Скористайтеся таблицею значень функції е х .
4. У річковому порту один причал, інтенсивність вхідного потоку – 5 суден щодня. Інтенсивність вантажно-розвантажувальних робіт – 6 суден на день. Маючи на увазі стаціонарний режим роботи, визначити усі середні характеристики системи.
5. l=3, m=2, штраф за кожну відмову дорівнює 5, а вартість простою однієї лінії дорівнює 2?
6. Яка оптимальна кількість каналів обслуговування повинна мати СМО, якщо l=3, m =1, штраф за кожну відмову дорівнює 7, а вартість простою однієї лінії дорівнює 3?
7. Яка оптимальна кількість каналів обслуговування повинна мати СМО, якщо l=4, m=2, штраф за кожну відмову дорівнює 5, а вартість простою однієї лінії дорівнює 1?
8. Визначити кількість злітно-посадкових смуг для літаків з урахуванням вимоги, що ймовірність очікування має бути меншою, ніж 0.05. При цьому інтенсивність вхідного потоку 27 літаків на добу, а інтенсивність їхнього обслуговування – 30 літаків на добу.
9. Скільки рівноцінних незалежних конвеєрних ліній повинен мати цех, щоб забезпечити ритм роботи, при якому ймовірність очікування обробки виробів повинна бути меншою за 0.03 (кожний виріб випускається однією лінією). Відомо, що інтенсивність надходження замовлень 30 виробів за годину, а інтенсивність обробки виробу однією лінією – 36 виробів за годину.
10. Безперервна випадкова величина Х розподілена за показовим законом із параметром l=5. Знайти функцію розподілу, характеристики та ймовірність влучення с.в. Х інтервал від 0.17 до 0.28.
11. Середня кількість викликів, що надходять на АТС за одну хвилину, дорівнює 3. Вважаючи потік пуассонівським, знайти ймовірність того, що за 2 хвилини надійде: а) два виклики; б) менше двох дзвінків; в) не менше двох дзвінків.
12. У ящику 17 деталей, із яких 4 – браковані. Складальник навмання витягує 5 деталей. Знайти ймовірність того, що а) усі витягнуті деталі – якісні; б) серед вилучених деталей 3 браковані.
13. Скільки каналів повинна мати СМО з відмовами, якщо l= 2треб / год, m=1треб/час, штраф за кожну відмову становить 8т.руб., вартість простою однієї лінії – 2т.руб. в годину?

Система масового обслуговування має один канал. Вхідний потік заявок на обслуговування - найпростіший потік з інтенсивністю λ. Інтенсивність потоку обслуговування дорівнює μ (тобто в середньому безперервно зайнятий канал видаватиме μ обслужених заявок). Тривалість обслуговування - випадкова величина, підпорядкована показовому закону розподілу. Потік обслуговування є найпростішим пуасонівським потоком подій. Заявка, що надійшла в момент, коли канал зайнятий, стає в чергу і чекає на обслуговування.

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

Граф станів СМО у разі має вигляд, показаний на рис. 2

Малюнок 5.2 – Граф станів одноканальної СМО з очікуванням (схема загибелі та розмноження)

Стани СМО мають таку інтерпретацію:

S0 - "канал вільний";

S1 – «канал зайнятий» (черги немає);

S2 – «канал зайнятий» (одна заявка стоїть у черзі);

Sn – «канал зайнятий» (п – 1 заявок стоїть у черзі);

SN – «канал зайнятий» (N – 1 заявок стоїть у черзі).

Стаціонарний процес у цій системі описуватиметься наступною системою алгебраїчних рівнянь:

(10)

п – номер стану.

Рішення наведеної вище системи рівнянь (10) для нашої моделі СМО має вигляд

(11)

(12)

Слід зазначити, що виконання умови стаціонарності

для даної СМО не обов'язково, оскільки кількість заявок, що допускаються в обслуговувальну систему, контролюється шляхом введення обмеження на довжину черги (яка не може перевищувати N - 1), а не співвідношенням між інтенсивностями вхідного потоку, тобто не ставленням λ/μ=ρ

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

ймовірність відмови в обслуговуванні заявки:

(13)

відносна пропускна здатність системи:

(14)

абсолютна пропускна спроможність:

середня кількість заявок, що знаходяться в системі:

(16)

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

(17)

середня тривалість перебування клієнта (заявки) у черзі:

(18)

середня кількість заявок (клієнтів) у черзі (довжина черги):

(19)

Розглянемо приклад одноканальної СМО з очікуванням.

приклад2. Спеціалізований пост діагностики є одноканальною СМО. Число стоянок для автомобілів, що очікують проведення діагностики, обмежено і дорівнює 3 (N- 1) = 3]. Якщо всі стоянки зайняті, тобто в черзі вже три автомобілі, то черговий автомобіль, що прибув на діагностику, в чергу на обслуговування не стає. Потік автомобілів, що прибувають на діагностику, розподілений за законом Пуассона і має інтенсивність = 0,85 (автомобіля на годину). Час діагностики автомобіля розподілено за показовим законом і в середньому дорівнює 1,05 год.

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

Рішення

1. Параметр потоку обслуговувань автомобілів:

2. Наведена інтенсивність потоку автомобілів визначається як відношення інтенсивностей λ, μ, тобто.

3. Обчислимо фінальні можливості системи

4. Імовірність відмови в обслуговуванні автомобіля:

5. Відносна пропускна здатність посту діагностики:

6. Абсолютна пропускна здатність посту діагностики

(автомобіля за годину).

7. Середня кількість автомобілів, що знаходяться на обслуговуванні та в черзі (тобто в системі масового обслуговування):

8. Середній час перебування автомобіля у системі:

9. Середня тривалість перебування заявки у черзі обслуговування:

10. Середня кількість заявок у черзі (довжина черги):

Роботу розглянутого поста діагностики можна вважати задовільною, оскільки пост діагностики не обслуговує автомобілі в середньому у 15,8% випадків. (Р відк = 0,158).

Перейдемо тепер до розгляду одноканальної СМО з очікуванням без обмеження на місткість блоку очікування (тобто N →∞).Інші умови функціонування СМО залишаються без змін.

Стаціонарний режим функціонування цієї СМО існує при t →∞ оо для будь-якого n = 0, 1, 2, ... і коли λ< μ. Система алгебраических уравнений, описывающих работу СМО при t →∞ для любого n = 0, 1, 2, ... , имеет вид

(20)

Вирішення даної системи рівнянь має вигляд

де ρ = λ/μ< 1.

Характеристики одноканальної СМО з очікуванням, без обмеження на довжину черги, такі:

Середня кількість клієнтів (заявок) на обслуговування, що знаходяться в системі:

(22)

середня тривалість перебування клієнта у системі:

(23)

середня кількість клієнтів у черзі на обслуговуванні:

(24)

середня тривалість перебування клієнта у черзі:

(25)

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

Потрібно визначити фінальні значення наступних імовірнісних характеристик:

ймовірності станів системи (поста діагностики);

Середня кількість автомобілів, що знаходяться в системі (на обслуговуванні та в черзі);

Середню тривалість перебування автомобіля у системі (на обслуговуванні та в черзі);

Середня кількість автомобілів у черзі на обслуговуванні;

Середню тривалість перебування автомобіля у черзі.

1. Параметр потоку обслуговування μ та наведена інтенсивність потоку автомобілів ρ визначені у прикладі 2:

μ= 0,952; ρ = 0,893.

2. Обчислимо граничні ймовірності системи за формулами

Р 0 = 1 – ρ = 1 – 0,893 = 0,107;

Р 1 = (1 - ρ). ρ = (1 - 0,893) * 0,893 = 0,096;

Р 2 = (1 - ρ). ρ 2 = (1 - 0,893) * 0,8932 = 0,085;

Р з = (1 - ρ). ρ 3 = (1 - 0,893) * 0,8933 = 0,076;

Р 4 = (1 - ρ). ρ 4 = (1 - 0,893) * 0,8934 = 0,068;

Р 5 = (1 - ρ). ρ 5 = (1 - 0,893) * 0,8935 = 0,061 і т.д.

Слід зазначити, що Р 0 визначає частку часу, протягом якого пост діагностики вимушено не діє (випростує). У прикладі вона становить 10,7%, оскільки Р 0 = 0,107.

3. Середня кількість автомобілів, що знаходяться в системі (на обслуговуванні та в черзі):

4. Середня тривалість перебування клієнта у системі:

5. Середня кількість автомобілів у черзі на обслуговування:

6. Середня тривалість перебування автомобіля у черзі:

7. Відносна пропускна спроможність системи:

т. е. кожну заявку, яка прийшла в систему, буде обслужена.

8. Абсолютна пропускна спроможність:

А = λ * q = 0,85 * 1 = 0,85.

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

Припустимо, в початковому варіанті кількість місць для стоянки автомобілів, що прибувають, дорівнювала трьом (див. приклад 2). Частота mвиникнення ситуацій, коли автомобіль, що прибуває на посаду діагностики, не має можливості приєднатися до черги:

m=λ*P N

У нашому прикладі за N = 3 + 1 = 4 і ρ = 0,893

m=λ*P 0 *ρ 4 =0.85*0.248*0.8934=0.134автомобіля на годину.

При 12-годинному режимі роботи посту діагностики це еквівалентно тому, що пост діагностики в середньому за зміну (день) втрачатиме 12*0,134 = 1,6 автомобіля. Зняття обмеження на довжину черги дозволяє збільшити кількість обслужених клієнтів у нашому принаймні в середньому на 1,6 автомобіля за зміну (12 год. роботи) посту діагностики. Зрозуміло, що рішення щодо розширення площі для стоянки автомобілів, які прибувають на посаду діагностики, має ґрунтуватися на оцінці економічної шкоди, яка обумовлена ​​втратою клієнтів за наявності лише трьох місць для стоянки цих автомобілів.

4.4 Багатоканальна модель з пуассонівським вхідним потоком та експоненційним розподілом тривалості обслуговування

У переважній більшості випадків практично системи масового обслуговування є багатоканальними, і, отже, моделі з n обслуговуючими каналами (де n > 1) представляють безсумнівний інтерес.

Процес масового обслуговування, описуваний даною моделлю, характеризується інтенсивністю вхідного потоку λ, у своїй паралельно може обслуговуватися трохи більше n клієнтів (заявок). Середня тривалість обслуговування однієї заявки дорівнює l/μ. Вхідний та вихідний потоки є пуассонівськими. Режим функціонування обслуговуючого каналу не впливає на режим функціонування інших обслуговуючих каналів системи, причому тривалість процедури обслуговування кожним з каналів є випадковою величиною, підпорядкованою експоненційному закону розподілу. Кінцева мета використання n паралельно включених обслуговуючих каналів полягає у підвищенні (порівняно з одноканальною системою) швидкості обслуговування вимог за рахунок обслуговування одночасно n клієнтів.

Граф станів багатоканальної системи масового обслуговування із відмовами має вигляд, показаний на рис. 4.3.

Стани цієї СМО мають таку інтерпретацію:

S0 - всі канали вільні;

S 1 - зайнятий один канал, інші вільні;

……………………….

S k - зайняті до k каналів, інші вільні;

……………………….

S n - зайняті всі n канали, заявка отримує відмову в обслуговуванні.

Рівняння Колмогорова для ймовірностей станів системи Р 0 , …, P k ,…, Р n будуть мати такий вигляд:

(26)

Початкові умови вирішення системи такі:

P 0 (0) = 1, P 1 (0) = P 2 (0) = ... = P k (0) = ... = P n (0) = 0.

Стаціонарне рішення системи має вигляд:

(27)

Формули для обчислення ймовірностей P kназиваються формулами Ерланга.

Визначимо ймовірнісні характеристики функціонування багатоканальної СМО з відмовами у стаціонарному режимі:

Імовірність відмови:

(28)

так як заявка отримує відмову, якщо приходить у момент, коли все nканали зайняті. Розмір Р отк характеризує повноту обслуговування вхідного потоку;

Імовірність того, що заявка буде прийнята до обслуговування (вона ж - відносна пропускна здатність системи q) доповнює Р відк до одиниці:

(29)

Абсолютна пропускна спроможність

A=λ*q=λ*(1-P отк); (30)

Середня кількість каналів, зайнятих обслуговуванням:

(31)

Воно характеризує рівень завантаження системи.

Приклад 4. Нехай n-канальна СМО є обчислювальний центр (ВЦ) з трьома (n = 3) взаємозамінними ПЕОМ для вирішення завдань, що надходять. Потік завдань, що надходять на ПЦ, має інтенсивність λ = 1 завдання на годину. Середня тривалість обслуговування t обсл = 1,8 год. Потік заявок на вирішення завдань та потік обслуговування цих заявок є найпростішими.

Потрібно обчислити фінальні значення:

ймовірності станів ВЦ;

Ймовірність відмови в обслуговуванні заявки;

Відносної пропускної спроможності ПЦ;

Абсолютної пропускної спроможності ПЦ;

Середнього числа зайнятих ПЕОМ на ПЦ.

Визначте, скільки додатково треба придбати ПЕОМ, щоб збільшити пропускну здатність ВЦ у 2 рази.

1. Визначимо параметр μ потоку обслуговування:

ρ=λ/μ=1/0.555=1.8

3. Граничні ймовірності станів знайдемо за формулами Ер-
ланга (27):

P 1 = 1.8 * 0.186 = 0.334;

P 2 = 1.62 * 0.186 = 0.301;

P 3 = 0.97 * 0.186 = 0.180.

4. Імовірність відмови в обслуговуванні заявки

P отк = P 3 = 0.180

5. Відносна пропускна здатність ВЦ

q = 1 - P отк = 1 - 0.180 = 0,820.

6. Абсолютна пропускна здатність ВЦ

А= λ q= 1 0,820 = 0,820.

7. Середня кількість зайнятих каналів - ПЕОМ

Таким чином, при режимі СМО, що встановився, в середньому буде зайнято 1,5 комп'ютера з трьох - решта півтора простоюватиме. Роботу розглянутого ВЦ навряд можна вважати задовільною, оскільки центр не обслуговує заявки загалом у 18% випадків (P 3 =0,180). Очевидно, що пропускну здатність ВЦ за даними λ і μ можна збільшити лише рахунок збільшення числа ПЕОМ.

Визначимо, скільки необхідно використовувати ПЕОМ, щоб скоротити кількість не обслужених заявок, що надходять на ВЦ, вдесятеро, тобто. щоб ймовірність відмови у вирішенні завдань не перевищувала 0,0180. Для цього використовуємо формулу (28):

Складемо таку таблицю:

n
P 0	0,357	0,226	0,186	0,172	0,167	0,166
P відк	0,643	0,367	0,18	0,075	0,026	0,0078

Аналізуючи дані таблиці, слід зазначити, що розширення числа каналів ПЦ за даних значень λ і μ до 6 одиниць ПЕОМ дозволить забезпечити задоволення заявок на вирішення завдань на 99,22%, тому що при п= 6 ймовірність відмови в обслуговуванні (Р відк)складає 0,0078.

4.5 Багатоканальна система масового обслуговування з очікуванням

Процес масового обслуговування при цьому характеризується наступним: вхідний і вихідний потоки пуассонівськими з інтенсивностями λ і μ відповідно; паралельно обслуговуватися можуть не більше С клієнтів. Система має З каналів обслуговування. Середня тривалість обслуговування одного клієнта дорівнює

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

(32)

Рішення системи рівнянь (32) має вигляд

(33) (34)

(35)

Рішення буде дійсним, якщо виконується така умова:

Імовірнісні характеристики функціонування в стаціонарному режимі багатоканальної СМО з очікуванням та необмеженою чергою визначаються за такими формулами:

Імовірність того, що в системі знаходиться n клієнтів на обслуговуванні, визначається за формулами (33) та (34);

Середня кількість клієнтів у черзі на обслуговування

(36)

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

Середня тривалість перебування клієнта (заявки на обслуговування) у черзі

Середня тривалість перебування клієнта у системі

Розглянемо приклади багатоканальної системи масового обслуговування з очікуванням.

Приклад 5. Механічна майстерня заводу із трьома постами (каналами) виконує ремонт малої механізації. Потік несправних механізмів, що прибувають до майстерні, - пуасонівський і має інтенсивність λ= 2,5 механізму на добу, середній час ремонту одного механізму розподілено за показовим законом і дорівнює t = 0,5 діб. Припустимо, що іншої майстерні на заводі немає, і, отже, черга механізмів перед майстернею може рости практично необмежено.

Потрібно обчислити такі граничні значення імовірнісних характеристик системи:

ймовірності станів системи;

Середня кількість заявок у черзі на обслуговування;

Середня кількість заявок, що знаходяться в системі;

Середню тривалість перебування заявки у черзі;

Середню тривалість перебування заявки у системі.

1. Визначимо параметр потоку обслуговування

μ = 1/t = 1/0,5 = 2.

2. Наведена інтенсивність потоку заявок

ρ = λ/μ = 2,5/2,0 = 1,25,

при цьому λ/μ*с=2,5/2*3=0,41.

Оскільки λ/μ* с<1 , то очередь не растет безгранично и в сис­теме наступает предельный стационарный режим работы.

3. Обчислимо ймовірність станів системи:

4. Імовірність відсутності черги біля майстерні

5. Середня кількість заявок у черзі на обслуговування

6. Середня кількість заявок, що знаходяться в системі

L s = Lq+ρ = 0,111 + 1,25 = 1,361.

7. Середня тривалість перебування механізму у черзі обслуговування

8. Середня тривалість перебування механізму у майстерні (у системі)

1

1. Агішева Д.К., Зотова С.А., Матвєєва Т.А., Світлична В.Б. Математична статистика (навчальний посібник) // Успіхи сучасного природознавства. - 2010. - № 2. - С. 122-123; URL: http://www.natural-sciences.ru/ru/article/view?id=7763.

2. Хрущов Д.Г., Силантьєв А.В., Агішева Д.К., Зотова С.А. Помилки прийняття гіпотези математичної статистики // Міжнародний студентський науковий вісник. - 2015. - № 3; URL: www.

3. Агішева Д.К., Зотова С.А., Матвєєва Т.А., Світлична В.Б. Математична статистика: навчальний посібник/Д.К. Агішева, С.А. Зотова, Т.А. Матвєєва, В.Б. Світлична; ВПІ (філія) ВолгДТУ. - Волгоград, 2010.

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

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

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

де λ - інтенсивність надходження заявок до системи (середня кількість заявок, що надходять до системи за одиницю часу).

Щільність розподілу тривалостей обслуговування:

де – інтенсивність обслуговування; tоб - середній час обслуговування одного клієнта.

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

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

Ця величина дорівнює ймовірності Р0 те, що канал обслуговування вільний.

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

Імовірність відмови в обслуговуванні заявки дорівнюватиме ймовірності стану «канал обслуговування зайнятий»:

Розмір Ротк може бути інтерпретована як середня частка необслужених заявок серед усіх поданих.

Нехай одноканальна система масового обслуговування (СМО) з відмовими є одне місце у черзі до каси у банку. Заявка - відвідувач, який прибув у момент, коли місце зайняте, отримує відмову в обслуговуванні. Інтенсивність потоку приходу відвідувачів = 3 (чол./ч). Середня тривалість обслуговування tоб = 0,6 год.

Ми будемо визначати в режимі, що встановився, наступні граничні значення: відносну пропускну здатність q; абсолютну пропускну здатність А; можливість відмови Ротк.

Порівняємо фактичну пропускну спроможність системи масового обслуговування з номінальною пропускною спроможністю, яка була б, якби кожен відвідувач обслуговувався 0,6 години, і черга була б безперервною.

Спочатку визначимо інтенсивність потоку обслуговування:

Обчислимо відносну пропускну здатність:

Величина q означає, що в режимі система буде обслуговувати приблизно 62,4% людей.

Абсолютну пропускну здатність визначимо за формулою:

Це означає, що система здатна здійснити в середньому 0,624 обслуговування людей на годину.

Обчислимо ймовірність відмови:

Це означає, що близько 37,6% відвідувачів на касу отримають відмову в обслуговуванні.

Визначимо номінальну пропускну спроможність системи:

Виходячи з даних розрахунків, робимо висновок, що Аном у рази більше, ніж фактична пропускна спроможність, обчислена з урахуванням випадкового характеру потоку заявок та часу обслуговування.

Ця система працює неефективно. Імовірність відмови занадто велика - 37 осіб зі 100 підуть із банку, не отримавши обслуговування. Це недопустимо. У такій ситуації є кілька розв'язань проблеми:

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

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

Не додаючи ще одного каналу створити систему без відмов, але з очікуванням у черзі. Цього можна досягти, якщо встановити дивани для очікування.

Таким чином, можна підвищити ефективність роботи найприйнятнішим для банку рішенням.

Бібліографічне посилання

Якушина А.А., Биханов А.В., Єлагіна А.І., Матвєєва Т.А., Агішева Д.К., Світлична В.Б. ОДНОКАНАЛЬНА СИСТЕМА МАСОВОГО ОБСЛУГОВУВАННЯ З ПУАССОНІВСЬКИМ ВХІДНИМ ПОТІКОМ // Міжнародний студентський науковий вісник. - 2016. - № 3-3.;
URL: http://сайт/ua/article/view?id=15052 (дата звернення: 18.03.2019). Пропонуємо до вашої уваги журнали, що видаються у видавництві «Академія Природознавства»