Теорія масового обслуговування з очікуванням

содержание Введение в теорію масового обслуговування з очікуванням 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). Необхідність такого була зрозуміла вже самому Эрлангу, і він у ряді робіт зробив зусилля знайти інші вдалі розподілу для тривалості обслуговування. Зокрема, їм запропоновано зване розподіл Эрланга, щільність розподілу якого дається формулой.

[pic] де, (> 0, а k — ціле позитивне число.

Розподіл Эрланга є розподіл суми k незалежних доданків, кожна з яких має розподіл (1).

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

[pic].

Це рівність дає спосіб оцінки параметра (по досвідченим даним. Як неважко обчислити, дисперсія тривалості обслуговування равна.

[pic].

2. Упорядкування рівнянь. система з очікуванням у разі найпростішого потоку і показового часу обслуговування є випадковий процес Маркова.

Знайдемо ті рівняння, яким задовольняють ймовірності Pk (t). Один із рівнянь очевидно, саме кожному за t.

[pic]. (2).

Знайдемо спочатку можливість, зараз t+h все прилади вільні. Це може відбутися такими способами: в останній момент t все прилади мали свободу і поза час h нових вимог не надходило; в останній момент t один прилад переймався обслуговуванням вимоги, й інші прилади вільні; під час h обслуговування вимоги завершили і нових вимог не поступило.

Інші можливості, якось: були задіяні двоє чи троє приладу і поза час h робота ними скінчилася — мають ймовірність o (h), як в цьому убедится.

Можливість першого із зазначених подій равна.

[pic] ймовірність другого события.

[pic].

Таким образом,.

[pic].

Звідси вочевидь дійшли уравнению.

[pic] (3).

Перейдемо тепер до написання рівнянь для Pk (t) при k (1. Розглянемо окремо два різних випадку: 1 (k (m і k (m. Нехай спочатку 1 (k (m. Перерахуємо лише суттєві стану, із яких завітати у стан Ek в останній момент t+h. Ці стану таковы:

У час t система перебувала у стані Ek, під час h нових вимог не надійшла й жоден прилад не закінчив обслуговування. Така ймовірність події равна.

[pic].

У час t система перебувала у стані Ek-1, під час h надійшло нову вимогу, але й одне раніше тримав вимога був закінчено обслуговуванням. Така ймовірність події равна.

[pic].

У час t система перебувала у стані Ek+1, під час h нових вимог не надійшло, але одну вимогу було обслуговано. Можливість цього равна.

[pic].

Решта мислимі можливості переходу до стану Ek за проміжок часу h мають ймовірність, рівну 0(h).

Зібравши воєдино знайдені ймовірності, отримуємо таке равенство:

[pic].

Нескладні перетворення наводять нас до такого рівнянню для 1 (k (m:

[pic] (4).

Схожі міркування для k (m призводять до уравнению.

[pic] ` (5).

Для визначення ймовірностей Pk (t) ми маємо нескінченну систему диференційних рівнянь (2)-(5). Її вирішення представляє безсумнівні технічні трудности.

3. Визначення стаціонарного решения.

Теоретично масового обслуговування зазвичай вивчають лише усталене рішення для t ((. Існування таких рішень встановлюється так званими эргодическими теоремами, окремі пізніше будуть нами встановлено. У завданню виявляється, що граничні чи, як кажуть зазвичай, стаціонарні ймовірності існують. Введемо їм позначення Pk. Зауважимо додатково, (цього ми також нині різноманітні станемо доводити), що [pic] при t ((.

Сказане дозволяє укласти, що рівняння (3), (4) і (5) для стаціонарних ймовірностей приймають наступний вид:

[pic] (6) при 1 (k (m.

[pic] (7) при k (m.

[pic] (8).

До цих рівнянням додається нормирующее условие.

[pic] (9).

Аби вирішити отриманої безкінечною алгебраїчній системи введемо позначення: при 1(k (m.

[pic] при k (m [pic].

Система рівнянь (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.

[pic] (12) При k (m з рівняння (11) знаходимо, что.

[pic] і отже, при k (m.

[pic] (13).

Залишається знайти P0. І тому в (9) підставляємо висловлювання Pk з (12) і (13). У результате.

[pic].

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

((m (14) то становищі знаходимо равенство.

[pic] (15).

Якщо умова (14) не виконано, тобто. якщо ((m, то ряд, котрий у квадратної скобці рівняння визначення P0, розходиться і, отже, P0 має бути одно 0. Та заодно, як випливає з (12) і (13), попри всі k (1 виявляється Pk =0.

Методи теорії ланцюгів Маркова дозволяють укласти, що з ((m з часом чергу прагне (по вероятности.

4. Деякі підготовчі результаты.

У запровадження ми вже казали, що з завдання з очікуванням основний характеристикою якості обслуговування є тривалість очікування вимогою початку обслуговування. Тривалість очікування є випадкову величину, яку позначимо буквою (. Розглянемо залишився завдання визначення розподілу ймовірностей тривалості очікування у вже що встановилася процесі обслуговування. Означимо далі через P (((t (можливість, що тривалість очікування перевершить t, і крізь Pk (((t (ймовірність нерівності, вказаної у скобці, за умови, зараз надходження вимоги, у черзі перебувати k вимог. З огляду на формули повної ймовірності маємо равенство.

P (((t (=[pic]. (16).

Перш ніж перетворити цієї формули до виду, зручного для користування, приготуємо деякі необхідні нам задля її подальшого відомості. Насамперед для випадків m=1 і m=2 знайдемо прості формули для P0. нескладні перетворення призводять до таким равенствам: при m=1.

P0=1-(, (17) а при m=2.

[pic] (18).

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

[pic] (19).

Ця формула для m=1 приймає особливо простий вид:

(=(, (20) при m=2.

[pic] (21).

Нагадаємо, що у формулі (19) (може приймати будь-яке значення від 0 до m (включно). Тож у формулі (20) (((, а (21) ((2.

5. визначення функції розподілу тривалості ожидания.

Якщо момент надходження вимоги у черзі вже перебували k-m вимог, то оскільки обслуговування відбувається у порядку черговості, знову яке надійшло вимога має очікувати, якщо будуть обслужені k-m+1 вимог. Нехай qs (t) означає можливість, що з проміжок часу тривалості t після вступу даного нас вимоги закінчилося обслуговування рівно вимог. Зрозуміло, що k (m має місце равенство.

[pic].

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

[pic].

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

[pic].

Итак,.

[pic] і, следовательно,.

[pic] Але ймовірності Pk известны:

[pic] поэтому.

[pic] очевидними перетвореннями наводимо праву частина останнього рівності до виду.

[pic] З формул (13) і (19) слід, що [pic], тому при t>0.

[pic] (22) Звісно ж, що з t.