Методи дослідження мереж масового обслуговування (стр. 1 из 13)

Дипломна робота

Методи дослідження мереж масового обслуговування

РЕФЕРАТ

Дипломна бакалаврська робота: 73 сторінки, 7 джерел, 7 таблиць, 5 рисунків.

Перелік ключових слів: мережа масового обслуговування, рівняння балансу, теорема ВСМР, теорема Нортона, декомпозиція мережі.

Об’єкт дослідження: мережі масового обслуговування.

Мета роботи: огляд методів розрахунку та дослідження мереж МО.

ЗМІСТ

ВСТУП

РОЗДІЛ 1. ОСНОВНІ ПОНЯТТЯ І ОЗНАЧЕННЯ

1.1 Механізм обслуговування

1.2 Дисципліна обслуговування

1.3 Маршрутна матриця і потоки в мережах

1.4 Інші означення

РОЗДІЛ 2. СКЛАДАННЯ РІВНЯННЬ ЛОКАЛЬНОГО БАЛАНСУ ДЛЯ МЕРЕЖМАСОВОГО ОБСЛУГОВУВАННЯ

2.1 Однорідні експоненціальні мережі масового обслуговування

2.1.1 Рівняння глобального балансу для замкнених мереж

2.1.2 Вигляд розв’язку в мультиплікативній формі

2.1.3 Мережі, що залежать від навантаження

2.1.4 Показники якості функціонування однорідних мереж

2.2 Мережі МО з кількома класами повідомлень

2.2.1 Опис змішаної мережі

2.2.2 Теорема ВСМР

2.2.3 Відкриті мережі масового обслуговування з кількома класами повідомлень

2.2.4 Розширення теореми ВСМР

РОЗДІЛ 3. МЕТОД АНАЛІЗУ СЕРЕДНІХ ЗНАЧЕНЬ

3.1 Загальне описання методу

3.2 Однорідна замкнена мережа масового обслуговування, що залежить від навантаження

3.3 Обчислення основних співвідношень

РОЗДІЛ 4. ОБЧИСЛЕННЯ ХАРАКТЕРИСТИК МЕРЕЖ МО

4.1 Метод Бузена

4.2 Обчислення характеристик мережі масового обслуговування

РОЗДІЛ 5. МЕТОД ДЕКОМПОЗИЦІЙНОЇ АПРОКСИМАЦІЇ

5.1 Апроксимація функцій розподілу475.2 Теорема Нортона для аналізу замкнених і розімкнених локально-збалансованих мереж масового обслуговування

5.3 Наближений декомпозиційний алгоритм

5.4 Декомпозиція розімкнених мереж масового обслуговування на рівні перших моментів

РОЗДІЛ 6. МЕТОД ПОЛІНОМІАЛЬНОЇ АПРОКСИМАЦІЇ

6.1 Опис методу

6.2 Оцінка обчислювальної складності

РОЗДІЛ 7. ПРИКЛАД РОЗРАХУНКУ МЕРЕЖІ МАСОВОГО ОБСЛУГОВУВАННЯ

ВИСНОВКИ

ПЕРЕЛІК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

ДОДАТОК

ВСТУП

Одним з розділів теорії масового обслуговування є мережі масового обслуговування. Поява цього розділу пов'язана з вирішенням практичних задач проектування обчислювальних систем та мереж. Перші підходи до аналізу мереж масового обслуговування (МО) були розроблені у 1960-70 pp. математиками Й.Джексоном, В.Гордоном та Ж.Ньюелом. Однак ці роботи не знайшли широкого практичного застосування до появи в 1971 р. роботи Ф.Мура, у якій було показано, що мережі МО є адекватними моделями функціонування обчислювальних систем. Подальший розвиток області застосування теорії мереж МО пов'язаний з удосконалюванням апаратного та програмного забезпечення обчислювальних систем.

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

У роботі основні методи дослідження мереж МО розділені на дві групи – аналітичні та наближені. Розглянутий у розділі 1 метод дослідження локально-збалансованих мереж МО дозволяє отримати розв'язок в зручній мультиплікативній формі. Але пряме обчислення стаціонарних ймовірностей станів та інших характеристик мережі є досить складною процедурою. У зв'язку з цим у розділі 4 розглянуті ефективні рекурентні алгоритми розрахунку мереж МО. Метод аналізу середніх значень дозволяє обчислити такі важливі показники функціонування мережі MO, як середні довжини черг та час дожидання, продуктивність мережі та ін., не удаючись до розрахунку нормалізуючої константи.

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

У роботі також наведений приклад розрахунку мережі масового обслуговування одним із методів та відповідна програма для обчислення характеристик.

РОЗДІЛ Ι. ОСНОВНІ ПОНЯТТЯ ТА ОЗНАЧЕННЯ

Предметом вивчення мереж МО є методи кількісного аналізу черг при взаємодії множини центрів обслуговування і потоків повідомлень.

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

і буфера об'ємом . При центр називають однолінійним, при — нескінченнолінійним. Надалі, якщо спеціально не обумовлено, вважатимемо, що об'єм буфера в центрі обслуговування .

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

1.1 МЕХАНІЗМ ОБСЛУГОВУВАННЯ

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

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

де

- кількість однакових обслуговуючих приладів у і-му центрі.

Нехай

— тривалість обслуговування k-го повідомлення. Якщо випадкові величини незалежні в сукупності і володіють однаковою функцією розподілу F(t), то таке обслуговування називається рекурентним. Основні аналітичні результати в теорії мереж МО одержані для випадку, коли перетворення Лапласа функції розподілу часу обслуговування

є раціональною функцією вигляду

де

— відповідно поліноми степеня d і d₁

Клас функцій розподілу, що володіють раціональним перетворенням Лапласа, є достатньо широкий і включає експоненціальний розподіл, розподіл Ерланга, гіперекспоненціальний розподіл та ін. Характеристики деяких цих розподілів наведені в табл. 1.1.

Таблиця 1.1 Характеристики деяких розподілів

Типрозподілу	Функція розподілу	Математичне сподівання	Дисперсія	Перетворення Лапласа
Експоненціальний
Ерлангаk- го порядку
Гіперекспоненціальний k- гопорядку

Вигляд перетворення Лапласа функції розподілу Ерланга k-го порядку показує, що воно є k- кратною згорткою експоненціального розподілу з середнім 1/kµ. Тому розподіл Ерланга k-го порядку можна інтерпретувати як розподіл тривалості обслуговування повідомлення на k послідовно сполучених однолінійних центрах обслуговування (етапах), причому тривалість обслуговування в кожному однолінійному центрі має експоненціальний розподіл з параметром kµ.