Введення
Долю вимог, які при надходженні в систему обслуговування застають всі прилади зайнятими, визначають за допомогою завдання типу системи обслуговування. Один з типів систем є система з очікуванням.
Системи з очікуванням - можливо очікування для будь-якого числа вимог, які не можуть бути обслужені відразу. Вони складають чергу, і з допомогою деякої дисципліни обслуговування визначаються, в якому порядку очікують вимоги вибираються з черги для обслуговування.
Зобразимо дану систему графічно (рис. 1). Тут кружечок 1 - обслуговуючий прилад, трикутник - накопичувач, кружечок О - джерело вимог. Вимога, що виникає в джерелі в момент закінчення фіктивної операції "очікування вимог", надходить в накопичувач. Якщо в цей момент прилад 1 вільний, то вимога негайно надходить на обслуговування. Якщо ж прилад зайнятий, то вимога залишається в накопичувачі, стаючи в кінець наявної черги.
Як тільки прилад 1 закінчує вироблену ним операцію, негайно приймається до обслуговування вимога з черги тобто з накопичувача, і починається нова операція обслуговування. Якщо вимог у накопичувачі немає, то нова операція не починається, стрілкою а показаний потік вимог від джерела до накопичувача, стрілкою b - потік обслугованих вимог.
Система масового обслуговування з очікуванням
1. Постановка завдання.
Ми вивчимо тут класичну задачу теорії масового обслуговування в тих умовах, в яких вона була розглянута і вирішена Ерланген. На m однакових приладів надходить найпростіший потік вимог інтенсивності l. Якщо в момент надходження вимоги є хоча б один вільний прилад, воно негайно починає обслуговуватися. Якщо ж всі прилади зайняті, то знову надійшла вимога стає в чергу за всіма тими вимогами, які надійшли раніше і ще не почали обслуговуватися. Звільнений прилад негайно приступає до обслуговування чергового вимоги, якщо тільки є черга. Кожна вимога обслуговується тільки одним приладом, і кожен прилад обслуговує в кожен момент не більше однієї вимоги. Тривалість обслуговування представляє собою випадкову величину з одним і тим же розподілом ймовірностей F (x). Передбачається, що при
x ³ 0
F (x) = 1 - e-m x, (1)
де m> 0 - постійна.
Ерланг вирішив це завдання, маючи на увазі постановки питань що виникли на той час у телефонному справі.
Вибір розподілу (1) для опису діяльності обслуговування зроблений не випадково. Справа в тому, що в цьому припущенні завдання допускає просте рішення, яке з задовільною для практики точності описує хід даного нас процесу. Ми побачимо, що розподіл (1) грає в теорії масового обслуговування виняткову роль, яка значною мірою викликана наступну властивість:
При показовому розподілі тривалості обслуговування розподіл діяльності решти роботи по обслуговуванню не залежить від того, скільки воно вже тривало.
Дійсно, нехай fa (t) означає ймовірність того, що обслуговування, яке вже триває час a, триватиме ще не менше ніж t. У припущенні, що тривалість обслуговування розподілена показово, f0 (t) = em t. Далі ясно, що f0 (a) = em a і f0 (a + t) = em (a +1). А так як завжди f0 (a + t) = f0 (a) fa (t), то em (a + t) = em a f0 (t) і, отже,
fa (t) = e-m t = fo (t).
Необхідну доведено.
Безсумнівно, що в реальній обстановці показове час обслуговування є, як правило, лише грубим наближенням до дійсності. Так, нерідко час обслуговування не може бути менше ніж, ніж деяка певна величина. Припущення ж (1) призводить до того, що значна частка вимог потребує лише короткочасною операції близькою до 0. Пізніше перед нами постає завдання звільнення від зайвого обмеження, що накладається припущенням (1). Необхідність цього була зрозумілою вже самому Ерланга, і він у ряді робіт робив зусилля знайти інші вдалі розподілу для тривалості обслуговування. Зокрема, їм було запропоновано так зване розподіл Ерланга, щільність розподілу якого дається формулою
де, m> 0, а k - ціле позитивне число.
Розподіл Ерланга представляє собою розподіл суми k незалежних доданків, кожне з яких має розподіл (1).
Позначимо для випадку розподілу (1) через h час обслуговування вимоги. Тоді середня тривалість обслуговування дорівнює
Це рівність дає нам спосіб оцінки параметра m за дослідними даними. Як легко вирахувати, дисперсія тривалості обслуговування дорівнює
2. Складання рівнянь.
система з очікуванням у випадку найпростішого потоку і показового часу обслуговування представляють собою випадковий процес Маркова.
Знайдемо ті рівняння, яким задовольняють ймовірності Pk (t). Одне з рівнянь очевидно, а саме для кожного t
. (2)
Знайдемо спочатку ймовірність того, що в момент t + h всі прилади вільні. Це може статися наступними способами:
в момент t всі прилади були вільні й за час h нових вимог не надходило;
в момент t один прилад був зайнятий обслуговуванням вимоги, всі інші прилади вільні; за час h обслуговування вимоги було завершено і нових вимог не надійшло.
Інші можливості, як-то: були зайняті два або три прилади і за час h робота на них була закінчена - мають ймовірність o (h), як легко в цьому переконатися.
Імовірність першого з зазначених подій дорівнює
ймовірність другого події
Таким чином,
Звідси очевидним чином приходимо до рівняння
(3)
Перейдемо тепер до складання рівнянь для Pk (t) при k ³ 1. Розглянемо окремо два різних випадки: 1 £ k <m і k ³ m. Нехай спочатку 1 £ k <m. Перерахуємо лише суттєві стану, з яких можна прийти в стан Ek в момент t + h. Ці стани такі:
У момент t система знаходилася у стані Ek, за час h нових вимог не надійшло і жоден прилад не закінчив обслуговування. Імовірність цієї події дорівнює
У момент t система знаходилася у стані Ek-1, за час h надійшло нову вимогу, але ні один раніше знаходилося вимога не було закінчено обслуговуванням. Імовірність цієї події дорівнює
У момент t система знаходилася у стані Ek +1, за час h нових вимог не надійшло, але одна вимога було обслуговано. Вірогідність цього дорівнює
Всі інші мислимі можливості переходу в стан Ek за проміжок часу h мають ймовірність, що дорівнює 0 (h).
Зібравши воєдино знайдені ймовірності, отримуємо наступне рівність:
Нескладні перетворення приводять нас до такого рівняння для 1 £ k <m:
(4)
Подібні ж міркування для k ³ m призводять до рівняння
`(5)
Для визначення ймовірностей Pk (t) ми отримали нескінченну систему диференціальних рівнянь (2) - (5). Її рішення являє безсумнівні технічні труднощі.
3. Визначення стаціонарного рішення.
У теорії масового обслуговування зазвичай вивчають лише усталене рішення для t ® ¥. Існування таких рішень встановлюється так званими ергодичної теореми, деякі з них пізніше будуть нами встановлені. У розглянутій задачі виявляється, що граничні або, як кажуть звичайно, стаціонарні ймовірності існують. Введемо для них позначення Pk. Зауважимо додатково, (цього ми також зараз не станемо доводити), що при t ® ¥.
Сказане дозволяє зробити висновок, що рівняння (3), (4) і (5) для стаціонарних ймовірностей приймають такий вигляд:
(6)
при 1 £ k <m
(7)
при k ³ m
(8)
До цих рівнянь додається нормуюче умова
(9)
Для вирішення отриманої нескінченної алгебраїчної системи введемо позначення: при 1 £ k <m
при k ³ m
Система рівнянь (6) - (8) в цих позначеннях приймає такий вигляд:
z1 = 0, zk-zk +1 = 0 при k ³ 1
Звідси полягає, що при всіх k ³ 1 zk = 0
тобто при 1 £ k <m
km Pk = l Pk-1 (10)
і при k ³ mmm Pk = l Pk-1 (11)
Введемо для зручності запису позначення
r = l / m.
Рівняння (10) дозволяє зробити висновок, що при 1 £ k <m
(12)
При k ³ m з рівняння (11) знаходимо, що
і отже, при k ³ m
(13)
Залишається знайти P0. Для цього в (9) підставляємо вираження Pk з (12) і (13). У результаті
Так нескінченна сума, що стоїть у квадратних дужках, знаходиться тільки за умови, що
r <m (14)
то при цьому положенні знаходимо рівність
(15)
Якщо умова (14) не виконано, тобто якщо r ³ m, то ряд, що стоїть в квадратній скобці рівняння для визначення P0, розходиться і, значить, P0 має дорівнювати 0. Але при цьому, як випливає з (12) і (13), при всіх k ³ 1 виявляється Pk = 0.
Методи теорії ланцюгів Маркова дозволяють укласти, що при r ³ m з плином часу чергу прагне до ¥ за ймовірністю.
4. Деякі підготовчі результати.
У вступі ми вже говорили, що для задачі з очікуванням основною характеристикою якості обслуговування є тривалість очікування вимогою початку обслуговування. Тривалість очікування являє собою випадкову величину, яку позначимо буквою g. Розглянемо зараз тільки задачу визначення розподілу ймовірностей тривалості очікування у вже сталому процесі обслуговування. Позначимо далі через P {g> t} ймовірність того, що тривалість очікування перевершить t, і через Pk {g> t} ймовірність нерівності, зазначеного в скобці, за умови, що в момент надходження вимоги, в черзі вже знаходиться k вимог. У силу формули повної ймовірності маємо рівність
P {g> t} = . (16)
Перш ніж перетворити цю формулу до вигляду, зручного для користування, приготуємо деякі необхідні нам для подальшого відомості. Перш за все для випадків m = 1 і m = 2 знайдемо прості формули для P0. нескладні перетворення приводять до таких равенствам: при m = 1
P0 = 1-r, (17)
а при m = 2
(18)
Обчислимо тепер ймовірність того, що всі прилади будуть зайняті в якійсь навмання взятий момент. Очевидно, що ця ймовірність дорівнює
(19)
Ця формула для m = 1 приймає особливо простий вигляд:
p = r, (20)
при m = 2
(21)
Нагадаємо, що у формулі (19) r може приймати будь-яке значення від 0 до m (включно). Так що у формулі (20) r <1, а в (21) r <2.
5. визначення функції розподілу тривалості очікування.
Якщо в момент надходження вимоги в черзі вже перебували km вимог, то оскільки обслуговування відбувається в порядку черговості, знову надійшла вимога повинна чекати, коли будуть обслужені k-m +1 вимог. Нехай qs (t) означає ймовірність того, що за проміжок часу тривалості t після надходження даного нас вимоги закінчилося обслуговування рівно вимог. Ясно, що k ³ m має місце рівність
Так як розподіл тривалості обслуговування припущено показовим і незалежних ні від того, скільки вимог знаходиться в черзі, ні від того, як великі тривалості обслуговування інших вимог, то ймовірність за час t не завершити жодного обслуговування (тобто ймовірність того, що не звільниться жоден з приладів) дорівнює
Якщо всі прилади зайняті обслуговуванням і ще є достатня чергу вимог, які очікують обслуговування, то потік обслугованих вимог буде найпростішим. Дійсно, в цьому випадку всі три умови - стаціонарність, відсутність післядії і ординарність - виконані. Імовірність звільнення за проміжок часу t рівно s приладів дорівнює (це можна показати і простим підрахунком)
Отже,
і, отже,
Але ймовірності Pk відомі:
тому
очевидними перетвореннями наводимо праву частину останнього рівності до виду
З формул (13) і (19) випливає, що , Тому при t> 0
(22)
Само собою зрозуміло, що при t