Реферат: Моделі систем масового обслуговування. Класифікація систем масового обслуговування

/> 

РЕФЕРАТ

На тему:

«Моделі системмасового обслуговування. Класифікація систем масового обслуговування»

Математичне введення в теорію ланцюгів Маркова. (Markov’schain)

Дискретні ланцюги Маркова. Говоритимемо,що заданий дискретний ланцюг Маркова, якщо для послідовності випадкових величинвиконується рівність />.

Це означає, що потік випадкових величин визначається тількивірогідністю переходу від попереднього значення випадкової величини доподальшого. Знаючи початковий розподіл вірогідності, можна знайти розподіл набудь-якому кроці. Величини in можнаінтерпретувати як номери станів деякої динамічної системи з дискретною безліччюстанів (типу кінцевого автомата). Якщо вірогідність переходів не залежить відномера кроку, то такий ланцюг Маркова називається однорідним і її визначеннязадається набором вірогідності />.

Для однорідного Марківського ланцюга можнавизначити вірогідність переходу із стану i в стан j за m кроків

/>

Ланцюг Маркова називається тією, що неприводиться, якщо кожний її стан може бути досягнутий з будь-якого іншогостану. Стан i називається поглинаючим, якщо для нього pii<sub/>=1.

Стан називається поворотним, якщо вірогідність попадання внього за кінцеве число кроків рівна одиниці. В іншому випадку стан відноситьсядо неповоротних. Поворотний стан може бути періодичним і аперіодичним залежновід наявності кратних кроків повернення. Введемо вірогідність повернення в станi через n кроків після відходу з цього стану: />

Вони дозволяють визначити середнє число кроків або, інакшекажучи, середній час повернення:/>.

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

Теорема 1

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

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

Теорема 2

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

А) всі стани ланцюга неповоротні або всіповоротні нульові, і тоді вся гранична вірогідність рівна нулю і стаціонарногостану не існує;

Б) всі стани поворотні ненульові і тодііснує стаціонарний розподіл вірогідності:

/>

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

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

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

/>

ЛанцюгМаркова

Введемо матрицю вірогідності переходів і вектор-рядоквірогідності на кроці n

/>.

Розподіл вірогідності на довільному кроцітоді підкорятиметься матричному співвідношенню:

/>.

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

/>

Його можна вирішувати як систему лінійнихрівнянь алгебри, якщо ланцюг кінцевий.

Для прикладу (мал. 1) маємо:

/>.

і рішення матричного рівняння зводиться дорішення системи трьох рівнянь:

/>

Коефіцієнти першого рівняння в цій системі доповнюють доодиниці суму коефіцієнтів другого і третього рівнянь; це свідчить про лінійнузалежність між ними. Тому для вирішення системи рівнянь потрібно ввестидодаткову нормуючу умову. В даному прикладі: />.

Вирішуючи систему отриманих рівнянь,маємо:

/>

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

/>.

Позначаючи відповідні перетворення, отримаємо: />.

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

Розглянемо вірогідність переходу системиіз стану i на m-том кроці в стан j на n-том кроці для n > m.

Можна показати, що ця вірогідністьзв'язана між собою, так званим рівняннями Чепмена-Колмогорова. (Chapman – Kolmogorov)

/>.

Для однорідних ланцюгів Маркова цірівняння спрощуються оскільки

/>.

І зводяться до аналізованих вище.

Безперервні ланцюги Маркова

Випадковий процес X(t) з дискретною безліччю значеньутворює безперервний ланцюг Маркова, якщо

/>.

Майбутні стани залежать від минулого тільки через поточнийстан. Для безперервний ланцюгів Маркова основним також є рівняння Чепмена – Колмогорова,для однорідного ланцюга має вигляд: />.

Тут матриця H(t)= [pij(t)] – матрицявірогідності переходу із стану i в стан j у момент часу t, а матриця Q називається«матрицею интенсивностей переходів». Її елементи маютьнаступний сенс: якщо у момент часу t система знаходилася в стані Ei, товірогідність переходу протягом проміжку часу (t,t+Дt) в довільний стан Ejзадається величиною qij(t)Дt + о(Дt), а вірогідність відходу із стану Eiвеличиною -qiiДt + про(Дt).

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

Найважливішим для подальшоговикористовування є клас безперервних ланцюгів Маркова званих «процесамизагибелі – розмноження» (Birth – death process). Длятаких систем із стану до можливі переходи тільки в стани до, k‑1 і k+1 внаступні моменти часу:

·         у момент t об'єм популяції був рівний до іпротягом часу (t, t+Дt) не відбулося зміни стану

·         у момент t об'єм популяції був рівний k‑1і протягом часу (t, t+Дt) народився один член популяції

·         у момент часу t об'єм популяції був рівний k+1і протягом часу (t, t+Дt) загинув один член популяції.

/>

Мал. 1. Можливі переходи в стан Тіньк

Шукатимемо вірогідність того, що у моментчасу t об'єм популяції рівний до, позначивши його Pk(t). Можна записатиспіввідношення для вірогідності досягнення стану до у момент часу t+Дt.

/>.

Визначимограничні і нормуючі умови:

/>

Виразимо вірогідність переходів за інтервал Дt черезінтенсивності

Віри(+1)=лkДt+o(Дt); Віри(-1)=мkДt+o(Дt).

Вірогідність нуля народжень 1 – лkДt+o(Дt), а нуля загибелі 1– мkДt+o(Дt).

Таким чином, вірогідність того, що стан до збережетьсянезмінним, буде рівна твору [1 – лkДt+o(Дt)] [1 – мkДt+o(Дt)].

Тоді рівняння Чепмена-Колмогорованабувають вигляд

/>

Розкриваючи дужки і проводячи розподіл на Дt, отримаємо:

/>

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

/>

У відповідність цій системі рівнянь можна поставити наочнудіаграму интенсивностей переходів, якааналогічна діаграмі переходів для дискретних ланцюгів Маркова (Мал. 2)

/>

Мал.2. Діаграма интенсивностей переходів дляпроцесу розмноження і загибелі

Овалам тут відповідають дискретні стани, а стрілки визначаютьінтенсивності потоків вірогідності (а не вірогідність!) переходів від одногостану до іншого.

Має місце своєрідний «закон збереження»:

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

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

Прирівнюючи похідну за часом нулю, одержуємо системурізницевих рівнянь

/>

Вважаючи, що інтенсивності л‑1 =л-2 =л‑3 =.0; м0 = м‑1 = м‑2 = м‑3<sub/>=.=0, другерівняння виписувати не буде окремо далі потрібно. Отже, стаціонарний режим вланцюзі Маркова описуватиметься системою різницевих рівнянь і умовою нормуваннядля вірогідності

/>

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

/>.

Інтенсивність потоку вірогідності в стан до рівнаінтенсивності потоку з цього стану.

Вирішувати рівняння балансу можна, спочатку визначивши при до=0 значення

/>.

Потім,побудувавши систему рівнянь для до =1, можна отримати

/>.

Далі одержуємо

/>

Зумови нормування: />.

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

/>.

Для більшості реальних систем масового обслуговування цянерівність виконується.

Класифікаціясистем масового обслуговування

Використовується трьох -, чотирьох -, шести – компонентнесимволічне позначення системи масового обслуговування, запропоноване Кендаллом(Candall) і розвинуте вроботах Г.П. Барашина.

а/b/c:d/e/f

а – розподіл потоку запитів, що поступає.

b – закон розподілу часу обслуговування.

Типові умовні позначення:

М – експоненціальний (Марківське) розподіл

D – детермінований розподіл

Тіньк – ерланговський розподіл к-го порядку

HMk – гиперекспониціональне

HEk – гиперерлангівське розподіл порядку до

GI – довільний розподіл незалежних проміжківміж заявками

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

з – структура системи обслуговування(звичайно число серверів).

d – дисципліна обслуговування (параметрипісля двокрапки іноді опускають).

Звичайно використовується скороченесимволічне позначення, наприклад FF замість FIFO, LF, PR і т. п.

e – максимальне число запитів, сприйманесистемою, може вживатися символ ¥.

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

В деяких публікаціях останніми символамивідображають якісні характеристики системи обслуговування. Деякі загальнірезультати і основи математичного апарату, необхідного для аналізу можнаотримати, розглядаючи системи G/G/m.

ФормулаЛіттла (Little)

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

/>

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

Взагальному випадку ясно, що із збільшенням числа вимог росте час очікування.Встановимо співвідношення між середнім числом вимог в системі, інтенсивністюпотоку і середнього часу перебування в системі. Позначимо число поступають впроміжку часу (0, t) вимог як функцію часу б(t).

Число витікаючих з системи заявок (обслужених) на цьомуінтервалі позначимо д(t). На малюнку 4 показані прикладифункціональної залежності цих двох випадкових процесів від часу.

/>

Мал. 4. Залежність між середнім числом вимог всистемі, інтенсивністю потоку і середнім часу перебування в системі

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

/>.

Площа між двома даними кривими від 0 до t –дає загальний час, проведений всіма заявками в системі за час t.

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

/>.

Нарешті, визначимо середнє число вимог в системі в проміжку(0, t): />.

З останніх трьох рівнянь виходить, що: /> (де />).

Якщо в СМО існує стаціонарний режим, топри t>?, матимуть місце співвідношення:

/>

/>

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

Цікаво, що як СМО можна розглянути тільки чергу із заявок вбуфері. Тоді формула Літтла придбаває інше значення – середня довжина чергирівна твору інтенсивності вхідного потоку заявок на середній час очікування вчерзі: />.

Якщо навпаки розглядати СМО тільки яксервери, то формула Літтла дає:

/>,

де /> –середнє число заявок в серверах, а/>– середній час обробки в сервері.

У будь-якому випадку: />.

Одним з основних параметрів, які використовуються при описіСМО, є коефіцієнт використовування (utilization factor). Це фундаментальнийпараметр, оскільки він визначається як відношення інтенсивності вхідного потокудо пропускної спроможності системи. Оскільки пропускна спроможність СМО міститьm серверів може бути визначений як: />, то коефіцієнт використовування може бути визначений як />.

Неважко бачити, що коефіцієнт використовування рівний вточності інтенсивності навантаження, якщо СМО з одним сервером і в m раз меншедля систем з m серверами. Величина коефіцієнта використовування рівнасередньому значенню від частки зайнятих серверів і />.

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