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

РОЗДІЛ 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), то таке обслуговування називається рекурентним. Основні аналітичні результати в теорії мереж МО одержані для випадку, коли перетворення Лапласа функції розподілу часу обслуговування

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