Введення
Долю вимог, які при вступі в систему обслуговування застають всі прилади зайнятими, визначають за допомогою завдання типу системи обслуговування. Один з типів систем є система з очікуванням.
Системи з очікуванням - можливо очікування для будь-якого числа вимог, які не можуть бути обслужені відразу. Вони складають чергу, і за допомогою деякої дисципліни обслуговування визначаються, в якому порядку очікують вимоги вибираються з черги для обслужіванія.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)
Введемо для зручності запису позначення
?=?/?.< br /> Рівняння (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
Функція має в точці t = 0 розрив безперервності, що дорівнює ймовірності застати всі прилади зайнятими.

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

Нескладні обчислення призводять до формули
(23)
Дисперсія величини? дорівнює
.
Формула (23) дає середню тривалість очікування одного вимоги. Знайдемо середню втрату часу вимогами, які прийшли в систему обслуговування протягом проміжку часу T. За час T в систему надходить? T вимог в середньому; загальна втрата ними часу на очікування в середньому становить
(24)
Наведемо невеликі арифметичні підрахунки, які продемонструють нам, як швидко зростають сумарні втрати часу на очікування зі зміною величини?. При цьому ми обмежуємося випадком T = 1 і розглядаємо лише самі малі значення m: m = 1 і m = 2.
При m = 1 в силу (20)

При? = 0.1; 0.3; 0.5; 0.9; значення?? приблизно дорівнює 0.011; 0.267; 0.500; 1.633; 8.100.
При m = 2 в силу (21)

При? = 0.1; 1.0; 1.5; 1.9 значення?? приблизно дорівнює 0.0003; 0.333; 1.350; 17.587.
Наведені дані ілюструють добре відомий факт щодо великої чутливості систем обслуговування, вже досить сильно завантажених, до зростання завантаження. Споживач при цьому відразу відчуває значне зростання тривалості очікування. Цей факт обов'язково варто враховувати при розрахунку завантаження обладнання в системах масового обслужіванія.3

Додаток теорії до руху повітряного транспорту

З деякими поняттями, пов'язаними з керуванням рухом повітряного транспорту, ми познайомилися в ілюстративних додатку першого розділу. Пірс розглянув програми деяких ідей теорії масового обслуговування до організації посадки літаків. У даному випадку зазвичай становить інтерес скорочення часу посадки. Обчислимо спочатку ймовірність того, що один за одним n-1 літаків очікують приземлення.
Припустимо, що літаки наближаються до зони управління з випадкових напрямків через випадкові проміжки часу, розподілені за експоненціальним законом, з постійною інтенсивністю прибуття, яка приймається рівною одній одиниці. Отже, et - розподіл проміжків часу між моментами прибуття. Літак, який прибуває через проміжок часу, менший мінімального часу, необхідне для безпечного попереднього літака, затримується на мінімальний час. Відношення мінімального часу, необхідного для безпечної посадки, до середньої тривалості проміжку часу між прибувають літаками позначається T (для простоти будемо вважати, що для даного аеропорту ця величина постійна). Зазвичай становить інтерес випадок T
(14.54)
Імовірність того, що буде затриманий один літак, знайдемо, розглянувши всі затримки одиночних літаків між двома незадержіваемимі літаками. Літак, який буде затриманий, повинен прибути через проміжок часу t12T-t1. Таким чином, шукана ймовірність спільного появи цих двох подій дорівнює

Імовірність того, що буде затримано два літаки, знаходиться аналогічно (розглядається два затримуваних літака між двома незадержіваемимі) шляхом обчислення ймовірності появи спільного подій:
t1
t2 <2T-t1 - для другого затримуваного літака, наступного за перше затримувати;>
t <3T-t1 - t2 - для незадержіваемого літака, що настає безпосередньо за двома затримуваних.>
В результаті для двох затримуваних літаків отримуємо
. (14.55)
Загальний вираз для ймовірності того, що затримується n-1 літаків, має вигляд? N Tn-1 e-nT, де? N-коефіцієнт, що залежить тільки від n. Очевидно, що повинно виконуватися співвідношення
(14.56)
або
(14.57)

де величина U? Te-T для малих T визначається однозначно, отже, T можна виразити як функцію від U:
(14.58)
Використовуючи ту обставину, що початок координат - кратний полюс, маємо
(14.59)

Отже, розклавши подинтегральное вираз в ряд і вибравши коефіцієнт при T-1, можна знайти вирахування.
Імовірність того, що один за одним затримуються n-1 літаків, дорівнює
(14.60)
Використовуючи формулу Стірлінга для n?, Пірс наводить ряд кривих для цього розподілу.
Середнє число літаків, що знаходяться в системі (з урахуванням першого літака, що здійснює посадку без очікування), так само
(14.61)
Цей вираз можна легко знайти, диференціюючи вираз (14.56) по T і виробляючи спрощення. (Зауважимо, що при T = 1 затримуються всі літаки). Аналогічно знаходимо другий початковий момент, він дорівнює.
Частка затримуваних літаків визначається як відношення середнього числа літак?? в, що знаходяться в системі, без урахування літака, що здійснює посадку, до середнього числа літаків:
.
Розподіл тривалості посадки знайдемо шляхом наступних міркувань. Усі проміжки часу тривалістю tT, з'являється з частотою 1-T появи незадержіваемих літаків, помноженої на ймовірність їх прибуття, тобто на e-(t + T). Використовуємо одиничну функцію H (T-t) (що дорівнює одиниці для позитивних значень аргументу і дорівнює нулю для негативних; її похідна є дельта-функцією) і дельта-функцію? (Tt), щоб представити цей розподіл у вигляді

Тепер, використовуючи інтегральне рівняння Ліндлі, можна отримати розподіл часу очікування. Шляхом детального аналізу Пірс знаходить вираз для розподілу в проміжку часу t, mT

звідки після інтегрування по t (?? t??) він визначає T як частку затримуваних літаків. Зауважимо, що при підсумовуванні по m необхідно розглядати інтервали (mT, (m +1) T). Звідси знаходимо також середній час очікування
.
Зауважимо, що час очікування збільшується із зростанням T. Наведене вище розподіл дає критерії для визначення необхідної пропускної здатності аеропорта.4
Список літератури

1. Д. Кеніг, Д. Штойян. Методи теорії масового обслуговування: Пер. с нем./Под. ред. Г. П. Климова. М., 1981.
2. Г. І. Івченко, В. А. Каштанов, И. Н. Коваленко. Теорія масового обслуговування. М., 1982.
3. Б. В. Гнеденко, И. Н. Коваленко. Введення в теорію масового обслуговування. М., 1987.
4. Т. Л. Сааті. Елементи теорії масового обслуговування та її застосування: Пер. з англ./Под. ред. І.М. Коваленко, изд-ие 2. М., 1971.
1 [1] стор 23-24
2 [2] стор 50-51

3 стр 25-35
4 стор 384 - 387



12