зміст
Введення в теорію масового обслуговування з очікуванням 2
1. Постановка завдання. 3
2. Складання рівнянь. 4
3. Визначення стаціонарного рішення. 5
4. Деякі підготовчі результати. 6
5. визначення функції розподілу тривалості очікування. 7
6. Середня тривалість очікування. 8
Висновок. Додаток теорії до руху повітряного транспорту 10
Список використаної літератури 13
Введення
Долю вимог, які при вступі в систему обслуговуваннязастають всі прилади зайнятими, визначають за допомогою завдання типу системиобслуговування. Один з типів систем є система з очікуванням.
Системи з очікуванням - можливо очікування для будь-якого числа вимог,які не можуть бути обслужені відразу. Вони складають чергу, і за допомогоюпевної дисципліни обслуговування визначаються, в якому порядку очікуютьвимоги вибираються з черги для обслуговування. [1]
Зобразимо дану систему графічно (рис. 1). Тут кружечок 1 --обслуговуючий прилад, трикутник - накопичувач, кружечок О - джереловимог. Вимога, що виникає в джерелі в момент закінченняфіктивної операції "очікування вимог", надходить в накопичувач. Якщо вцей момент прилад 1 вільний, то вимога негайно надходить наобслуговування. Якщо ж прилад зайнятий, то вимога залишається у накопичувачі,стаючи в кінець черги наявною.
Як тільки прилад 1 закінчує вироблену ним операцію, негайноприймається до обслуговування вимога з черги тобто з накопичувача, іпочинається нова операція обслуговування. Якщо вимог у накопичувачі немає,то нова операція не починається, а стрілкою показаний потік вимог відджерела до накопичувача, стрілкою b - потік обслугованих вимог. [2]
Система масового обслуговування з очікуванням
1. Постановка завдання.
Ми вивчимо тут класичну завдання теорії масового обслуговування втих умовах, в яких вона була розглянута і вирішена Ерланген. На mоднакових приладів надходить найпростіший потік вимог інтенсивності (.
Якщо в момент надходження вимоги є хоча б один вільний прилад,воно негайно починає обслуговуватися. Якщо ж всі прилади зайняті, то зновущо надійшла вимога стає в чергу за всіма тими вимогами,які надійшли раніше і ще не почали обслуговуватися. Звільнивсяприлад негайно приступає до обслуговування чергового вимоги, якщотільки є чергу. Кожна вимога обслуговується тільки однимприладом, і кожен прилад обслуговує в кожен момент не більше одноговимоги. Загальна тривалість обслуговування є випадковою величинуз одним і тим же розподілом ймовірностей F (x). Передбачається, що приx (0
F (x) = 1 - e-(x, (1)де (> 0 - постійна.
Ерланга вирішив це завдання, маючи на увазі постановки питань що виникли дотой час у телефонному справі.
Вибір розподілу (1) для опису діяльності обслуговуваннязроблений не випадково. Справа в тому, що в цьому припущенні завданнядопускає просте рішення, яке із задовільною для практикиточності описує хід цікавить нас процесу. Ми побачимо, щорозподіл (1) грає в теорії масового обслуговування винятковуроль, яка значною мірою викликана наступну властивість:
При показовому розподіл тривалості обслуговуваннярозподіл діяльності, що залишилася, роботи по обслуговуванню незалежить від того, скільки воно вже тривало.
Дійсно, нехай fa (t) означає ймовірність того, щообслуговування, яке вже триває час a, триватиме ще не менше ніжt. У припущенні, що тривалість обслуговування розподіленапоказово, f0 (t) = e-(t. Далі ясно, що f0 (a) = e-(a і f0 (a + t) = e-((a +1).
А так як завжди f0 (a + t) = f0 (a) fa (t), то e-((a + t) = e-(a f0 (t) і,отже, fa (t) = e-(t = fo (t).
Необхідна доведено.
Безсумнівно, що в реальній обстановці показовий часобслуговування є, як правило, лише грубим наближенням додійсності. Так, нерідко час обслуговування не може бути менше ніж,ніж деяка певна величина. Припущення ж (1) призводить до того,що значна частка вимог потребує лише короткочасної операціїблизькою до 0. Пізніше перед нами постає завдання звільнення від зайвогообмеження, який накладається припущенням (1). Необхідність цього булаясна вже самому Ерланген, і він у ряді робіт робив зусилля знайти інші вдалірозподілу для тривалості обслуговування. Зокрема, їм булозапропоновано так званий "розподіл Ерланга, щільність розподілуякого дається формулою
де, (> 0, а k - ціле позитивне число.
Розподіл Ерланга являє собою розподіл суми kнезалежних доданків, кожне з яких має розподіл (1).
Позначимо для випадку розподілу (1) через (час обслуговуваннявимоги. Тоді середня тривалість обслуговування дорівнює
Це рівність дає нам спосіб оцінки параметра (по дослідним даним.
Як легко вирахувати, дисперсія тривалості обслуговування дорівнює
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 k (Pk = (Pk-1 (10)і при k (m m (Pk = (Pk-1 (11)
Введемо для зручності запису позначення
(=(/(.
Рівняння (10) дозволяє зробити висновок, що при 1 (k (m
(12)
При k (m з рівняння (11) знаходимо, що
і отже, при k (m
(13)
Залишається знайти P0. Для цього в (9) підставляємо вирази Pk з (12) і
(13). У результаті
Так нескінченна сума, що стоїть у квадратних дужках, знаходиться тількиза умови, що
((m (14)то при цьому положенні знаходимо рівність
(15)
Якщо умова (14) не виконано, тобто якщо ((m, то ряд, що стоїть вквадратні дужки рівняння для визначення P0, розходиться і, виходить, P0має дорівнювати 0. Але при цьому, як випливає з (12) і (13), при всіх k (
1 виявляється Pk = 0.
Методи теорії ланцюгів Маркова дозволяють зробити висновок, що при ((m зплином часу чергу прагне до (по ймовірності.
4. Деякі підготовчі результати.
У вступі ми вже говорили, що для задачі з очікуванням основнийхарактеристикою якості обслуговування є тривалість очікуваннявимогою початку обслуговування. Загальна тривалість очікування євипадкову величину, яку позначимо буквою (. Розглянемо зараз тількизадачу визначення розподілу ймовірностей тривалості очікування у вжесталому процесі обслуговування. Позначимо далі через P (((t (ймовірність того, що тривалість очікування перевершить t, і через Pk (((t (ймовірність нерівності, вказати в дужках, за умови, що в моментнадходження вимоги, в черзі вже знаходиться k вимог. У силуформули повної ймовірності маємо рівність
P (((t (=. (16)
Перед тим, як перетворити цю формулу до вигляду, зручному длякористування, приготуємо деякі необхідні нам для подальшого відомості.
Перш за все для випадків m = 1 і m = 2 знайдемо прості формули для P0.нескладні перетворення приводять до таких рівність: при m = 1
P0 = 1 - (, (17)а при m = 2
(18)
Обчислимо тепер ймовірність того, що всі прилади будуть зайняті вякийсь навмання взятий момент. Очевидно, що ця ймовірність дорівнює
(19)
Ця формула для m = 1 приймає особливо простий вигляд:
(= (, (20)при m = 2
(21)
Нагадаємо, що у формулі (19) (може приймати будь-яке значення від 0 доm (включно). Так що у формулі (20) (((, а в (21) ((2.
5. Визначення функції розподілу тривалості очікування.
Якщо в момент надходження вимоги в черзі вже знаходилися kmвимог, то оскільки обслуговування відбувається в порядку черговості,знову надійшла вимога повинна чекати, коли будуть обслужені k-m +1вимог. Нехай qs (t) означає ймовірність того, що за проміжокчасу тривалості t після надходження цікавить нас вимогизакінчилося обслуговування рівно вимог. Ясно, що k (m має місцерівність
Так як розподіл тривалості обслуговування припущенопоказовим і незалежним ні від того, скільки вимог знаходиться вчерги, ні від того, як великі тривалості обслуговування іншихвимог, то ймовірність за час t не завершити жодного обслуговування
(тобто ймовірність того, що не звільниться жоден з приладів) дорівнює
Якщо всі прилади зайняті обслуговуванням і ще є достатнячергу вимог, які чекають на обслуговування, то потік обслуженихвимог буде найпростішим. Дійсно, в цьому випадку всі три умови
- Стаціонарність, відсутність післядії і ординарність - виконані.
Вірогідність звільнення за проміжок часу t рівно s приладів дорівнює
(це можна показати і простим підрахунком)
Отже,
і, отже,
Але ймовірності Pk відомі:
тому
очевидними перетвореннями наводимо праву частину останньогорівності до виду
З формул (13) і (19) випливає, що, тому при t> 0
(22)
Само собою зрозуміло, що при t
