Моделювання процесу обслуговування в СМО

⇐ Назад

ВСТУП

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

Дані методичні вказівки містять шість лабораторних робіт, розрахованих на 24 години.

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

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

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

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

Вивчення другого розподілу Ерланга з найпростішим потоком вимог і характеристик якості СМО з очікуванням проводиться під час виконання п'ятої лабораторної роботи.

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

1 МОДЕЛЮВАННЯ ПУАССОНІВСЬКОГО ПОТОКУ ВИМОГ

1.1 Мета роботи

Мета роботи – вивчити властивості й характеристики пуассонівського (найпростішого) потоку. Порівняти теоретичні та модельні значення отриманих характеристик.

1.2. Короткі теоретичні відомості

Найпростіший потік має такі властивості: стаціонарність, ординарність і відсутність післядії.

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

, (1.1)

де – ймовірність надходження k вимог.

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

. (1.2)

Властивість відсутності післядії означає незалежність імовірнісних характеристик потоку від попередніх подій. Іншими словами, імовірність надходження k вимог у проміжок [t1,t2] залежить від кількості, часу надходження й тривалості обслуговування вимог до моменту t1. Для випадкового потоку без післядії умовна ймовірність надходження вимог у проміжку [t1,t2], обчислена при будь-яких припущеннях про протікання процесу обслуговування вимог до моменту t1, дорівнює безумовній

. (1.3)

До основних характеристик випадкового потоку відносять провідну функцію, параметр та інтенсивність. Провідна функція випадкового потоку є математичне очікування кількості вимог у проміжку [0, t). Функція – невід’ємна, неубутна, у практичних завданнях теорії розподілу інформації безперервна й приймає тільки кінцеві значення.

Параметр потоку в момент часу t є межа відношення ймовірності надходження не менше однієї вимоги в проміжку до величини цього проміжку при

. (1.4)

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

. (1.5)

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

. (1.6)

Інтенсивність стаціонарного потоку є математичне очікування кількості вимог в одиницю часу.

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

1.3 Моделювання найпростішого потоку

Для найпростішого потоку вимог довжини проміжків часу між послідовними вимогами потоку розподілені за показовим законом із тим самим параметром :

(1.7)

Це твердження дозволяє моделювати найпростіший потік вимог на заданому проміжку часу за допомогою методу Монте-Карло, в основі якого лежить така теорема:

якщо – випадкові числа, рівномірно розподілені на , то можливе значення одержуваної випадково безперервної величини Х з заданою функцією розподілу F(х), що відповідає , є коренем рівняння

. (1.8)

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

(1.9)

Вирішуючи це рівняння відносно , маємо

(1.10)

або

(1.11)

Порядок виконання роботи

1. Згенерувати випадкові рівномірно розподілені числа .

2. Обчислити l = 10×m/N_n (вимог/хв); де N_n – номер у журналі, m-номер групи.

3. По формулою , де i=1, 2, .., одержати для проміжків між вимогами.

4. На проміжку [T₁, T₂], T₁ = N+1, T₂ =N+5 хв., одержати послідовність моментів надходження вимог, де доти, поки £ T₂ .

Отримані результати занести в таблицю 1.1.

Таблиця 1.1

r_i	Z_i	t_k
r₁	z₁	t₁
r₂	z₂	t₂
.	.	.

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

(мін).

Для кожного проміжку визначити x (t) – кількість вимог, що потрапили в проміжок довжиною t, занести в таблицю 1.2.

Таблиця 1.2

Номер інтервалу			. . .
x(t )

З таблиці 1.2 визначити параметри статистичного розподілу випадкової величини й занести їх у таблицю 1.3.

Таблиця 1.3

x_k(t )				. . .	k
n_k	n₁	n₂	n₃	. . .	k

å n_k = N, де n_k – кількість інтервалів, з k вимогами.

6. Визначити модельне значення параметра потоку:

– мат. очікування кількості вимог в k інтервалі, звідси

7. Для заданого (l) і модельного значення ( ) визначити:

а) імовірність відсутності вимоги P₀( t ) за проміжок t = T₂ - T₁;

б) імовірність надходження однієї вимоги P₁( t );

в) імовірність надходження чотирьох вимог P₄( t );

г) імовірність надходження не менше п'яти вимог P_³₅ ( t )=1-( P₀ + P₁ + P₂ + P₃ + P₄ );

ґ) імовірність надходження менше трьох вимог P_<3 ( t )= P₀ + P₁ + P₂ ;

д) імовірність надходження не більше семи вимог P_£₇ ( t )= P₀ + . . . + P₇;

е) імовірність, що проміжок між вимогою z_k P[ 0,1 < z_k < 0,5 ] = F(0,5) - F(0,1).

8. Висновок.

1.5 Контрольні запитання і завдання

1. За якими властивостями класифікуються випадкові потоки?

2. Дати визначення властивостям: стаціонарність; ординарність; відсутність післядії.

3. Дати визначення числовим характеристикам випадкових потоків: параметр потоку ; інтенсивність потоку ; провідна функція потоку.

4. Для яких потоків збігаються значення параметра потоку й інтенсивності: = ?

5. За яким законом розподілений проміжок між сусідніми вимогами в найпростішому потоці?

6. За яким законом розподілена випадкова величина, що характеризує кількість вимог найпростішого потоку, що потрапили в деякий проміжок?

2 ПІДСУМОВУВАННЯ ВИПАДКОВИХ ПОТОКІВ

2.1 Мета роботи

Мета роботи – дослідити суму двох найпростіших потоків і визначити характеристики результуючого потоку.

2.2 Короткі теоретичні відомості

Підсумовування й роз'єднання найпростіших потоків

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

Експериментальна перевірка відповідності реального потоку найпростішому

У найпростішому потоці проміжки z між сусідніми вимогами розподілені по показовому (експонентному) закону з параметром .

Визначимо математичне очікування, дисперсію й середньоквадратичне відхилення проміжку z:

; (2.1)

; (2.2)

. (2.3)

Отриманий збіг величин M_z і характерний для показового розподілу. Ця властивість на практиці використовується як критерій для первісної перевірки відповідності гіпотези про показовий розподіл отриманим статистичним даним.

Інший спосіб перевірки ґрунтується на тому, що кількість вимог найпростішого потоку, що потрапили в інтервал часу t, описується розподілом Пуассона:

. (2.4)

Визначимо математичне очікування М_i і дисперсію D_i кількості вимог за проміжок t:

;

Збіг математичного очікування й дисперсії кількості вимог за проміжок t означає відповідність реального потоку найпростішому. Припустимо, для деякого реального потоку отримано ряд чисел x₁, x₂, …, x_n, що характеризує кількість вимог, що надходять в n проміжків довжиною t. Звичайно приймають t=15 хв. Розраховуються середнє значення й незміщена оцінка дисперсії величини x:

; .

Залежно від ступеня збігу величин і D_x, робиться висновок про прийнятність моделі найпростішого потоку.

Порядок виконання роботи

1. Використовуючи методику виконання першої лабораторної роботи,
пп. 1–6, промоделювати два найпростіших потоки з й , де m – номер групи, Nn – номер за списком. Отримані дані занести в таблицю 2.1.

Таблиця 2.1

Номер інтервалу	. . .	N
x₁(t )
x₂(t )
x₁+x₂

2. Одержати сумарний потік, складаючи x(t) відповідних інтервалів. Побудувати графіки х₁(n), x₂(n), x(n), де n – номер інтервалу, х₁, x₂, x – кількість викликів, що потрапили в інтервал для I, II і сумарного потоку відповідно.

3. Використовуючи методику п. 7 першої лабораторної роботи, одержати l_сум модельне для сумарного потоку x(n).

4. Порівняти отримане значення l_сум й ₁+ ₂ .

5. Розрахувати оцінки дисперсії й математичного очікування випадкової величини x(t) – кількість викликів сумарного потоку, що потрапили в інтервал t.

6. Висновок.

2.4 Контрольні запитання

1. Який потік утвориться при об'єднанні n найпростіших потоків?

2. Чому дорівнюють параметри потоків, що утворилися при роз'єднанні найпростішого потоку?

3. Який спосіб перевірки відповідності реального потоку найпростішому, використовують:

а) якщо виміряні проміжки між вимогами потоку;

б) якщо підраховано кількість вимог, що потрапили в проміжки рівної довжини.

3 ДОСЛІДЖЕННЯ СМО З ВІДМОВАМИ

3.1 Мета роботи

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

3.2 Короткі теоретичні відомості

N-канальна СМО з відмовами – це система, у якій у момент приходу вимоги всі вузли обслуговування зайняті й вимога одержує відмову й відразу залишає систему. Для такої системи ймовірність усіх станів системи (у сталому режимі) дає перший розподіл Ерланга:

де – навантаження СМО, – інтенсивність надходження вимог, – інтенсивність обслуговування.

До основних характеристик якості обслуговування розглянутої СМО відносяться:

імовірність відмови

;

середня кількість зайнятих вузлів обслуговування

;

середня кількість вільних вузлів обслуговування

У системах з відмовами події відмови й обслуговування становлять повну групу подій, звідси

З наведеного вище виразу відносна, пропускна здатність визначається за формулою

Абсолютна пропускна здатність СМО з відмовами дорівнює

Коефіцієнт зайнятості вузлів обслуговування визначається відношенням середньої кількості зайнятих каналів до загальної кількості каналів:

Порядок виконання роботи

1. Побудувати графік розподілу P_k для N-канальної СМО з відмовами, якщо на вхід системи надходить найпростіший потік вимог із інтенсивністю та обслуговування вимог виконується з інтенсивністю , де m – номер групи, N-кількість каналів обслуговування, Nn – номер за списком. Кількість каналів обслуговування визначається за варіантами з таблиці 3.1.

Таблиця 3.1

N_п,	1,5,9,13,17,21	2,6,10,14,18,22	3,7,11,15,19,23	4,8,12,16,20,24
N

Наприклад. Для СМО з відмовами графік розподілу P_k, побудований у системі Mathlab, показаний на рис. 3.1.

Рисунок 3.1 – Графік імовірностей P_k

2. Визначити характеристики якості обслуговування:

а) імовірність відмови Р_відм;

б) середня кількість зайнятих вузлів М_зайн;

в) середня кількість вільних вузлів М_вільн;

г) відносна пропускна здатність Q;

ґ) абсолютна пропускна здатність А;

д) коефіцієнт зайнятості вузлів Кз.

3. Висновки.

3.4 Контрольні завдання

1. Дати поняття навантаження системи.

2. Дати поняття коефіцієнта зайнятості вузлів.

3. Навести формулу першого розподілу Ерланга.

4. Дати поняття ймовірності відмови.

5. Дати визначення характеристикам якості СМО з відмовами.

4 МОДЕЛЮВАННЯ РЕАЛЬНОГО ПРОЦЕСУ ОБСЛУГОВУВАННЯ
СМО З ВІДМОВАМИ

4.1 Мета роботи

Мета роботи – порівняти значення характеристик якості СМО з явними втратами, отриманими в результаті моделювання й розрахованими за першою формулою Ерланга.

Моделювання процесу обслуговування в СМО

Функція розподілу проміжку між вимогами , а функція розподілу тривалості обслуговування . Програма моделювання містить два генератори випадкових величин і відповідно до заданих функцій A(t) і B(t), змінні t₀для зберігання моменту надходження чергової вимоги й t₁, t₂,..., t для зберігання моменту звільнення k-го ( ) каналу.

Для спрощення пояснень приймемо N=3 і проаналізуємо роботу алгоритму з моменту надходження п'ятої вимоги. Перший генератор формує чергове випадкове число z₅, що відповідає надходженню п'ятої вимоги . Припустимо, що до моменту перший канал був зайнятий четвертою вимогою, а другий і третій відповідно другою і третьою. Тоді , , . Кожне із чисел t₁ , t₂, t₃ визначає момент звільнення відповідного каналу.

При послідовному занятті каналів значення t₀ по черзі порівнюється з t₁ , t₂,…, t_N, поки не виявляється комірка з моментом звільнення . Нехай виявиться, що й , а . Це означає, що до моменту надходження п'ятої вимоги перший і другий канал залишалися зайнятими, а третій уже звільнився й може прийняти на обслуговування п'яту вимогу. Тоді t₃ прирівнюється t₀. Потім генерується випадкове число , що визначає тривалість обслуговування п'ятої вимоги й додається до t₃.

Шостий цикл починається з генерації випадкового числа z₆. Як і раніше, t₀=t₀+z₆. Потім здійснюється почергове порівняння вмісту нульової комірки із умістом інших комірок. Якщо тепер виявиться, що , і , то шоста вимога загубиться й на цьому цикл закінчиться.

Для підрахунку кількості К_над, що надійшли, і загублених К_заг вимог використовуються два лічильники. У перший додається одиниця при кожній генерації числа z, а в другий – при кожній втраті вимоги. Відношення К_над / К_заг дасть по закінченню чергової серії статистичну оцінку втрат вимог.

Порядок виконання роботи

1 Початкові умови моделювання.

Параметр вступника потоку (викл/хв), де N_n – номер у журналі, m – номер групи, N – кількість каналів.

Середній час обслуговування й кількість каналів визначається варіантом з табл. 4.1.

Таблиця 4.1

N_п, вар	1,7,13	2,8,14	3,9,15	4,10,16	5,11,17	6,12,18
N
h,сек

На початку моделювання в системі зайнято два канали.

2 Порядок моделювання

Моделювання здійснювати на інтервалі [t₁,t₂] хв., де t₁=N_n+1, t₂=N_n+200, а N_n – номер у журналі.

Надходження виклику моделюється аналогічно першій лабораторній роботі, запам'ятовується в масиві змінної t_пост і підраховується лічильником К_над.

Процес обслуговування моделюється за показовим законом розподілу відповідно до виразу

; .

Час звільнення каналу визначається так: .

Отриманими даними заповнюється таблиця 4.2.

Таблиця 4.2

r	z	t_пост	T_звіл	Номер каналу
r1	-	-
r2	-	-
r3	z1	tn1
				Втрата

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

3. Визначити модельну ймовірність відмови вимоги:

де К_заг – кількість загублених вимог; К_викл – загальна кількість вимог.

Визначити Р_відм за першою формулою Ерланга:

де .

4. Висновки.

4.4 Контрольні завдання

1. Визначити пропускну здатність окремих каналів при:

а) випадковому зайнятті;

б) послідовному зайнятті.

5 ДОСЛІДЖЕННЯ N - КАНАЛЬНОЇ СМО З ОЧІКУВАННЯМ

5.1 Мета роботи

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

5.2 Короткі теоретичні відомості

СМО з N-каналами обслуговує найпростіший потік вимог. При зайнятості всіх n вузлів обслуговування вимога, що надійшла, ставиться в чергу й обслуговується після деякого очікування. Загальна кількість вимог, що перебувають у системі на обслуговуванні й у черзі, позначимо й назвемо станом системи. При величина k характеризує кількість зайнятих каналів у системі, при кількість зайнятих каналів дорівнює , а різниця визначає довжину черги. Параметр інтенсивності обслуговування потоку v визначається кількістю зайнятих вузлів, і в першому випадку залежить від стану системи k, а в другому має постійне значення v.

Введемо поняття завантаження системи r, яке дорівнює відношенню інтенсивності вхідного потоку до інтенсивності обслуговування:

Відзначимо, що при інтенсивності поступаючого навантаження r, рівного або більшого за кількість вузлів обслуговування системи N, з імовірністю, рівній 1, постійно будуть зайняті всі вузли обслуговування й довжина черги буде нескінченною – явище «вибуху». Тому, щоб система могла функціонувати нормально й черга не росла безмежно, необхідно виконати умову .

Імовірність того, що система в сталому режимі перебуває в стані k (P_k), визначаємо за формулою (другий розподіл Ерланга)

, (5.1)

де .

До основних характеристик якості обслуговування СМО з очікуванням відносять такі:

Імовірність наявності черги P_чер є ймовірність того, що кількість вимог у системі більше кількості вузлів:

Імовірність зайнятості всіх вузлів системи P_зайн

Середня кількість вимог у системі М_вим

Середня довжина черги M_чер

Середня кількість вільних вузлів М_вільн

Середня кількість зайнятих вузлів М_зайн

Середній час очікування початку обслуговування Т_оч для вимоги, що поступили в систему

Загальний час, що проводять у черзі всі вимоги, що надійшли в систему за одиницю часу, Т_з.оч

Середній час Т_вим, що вимога проводить у системі обслуговування

Сумарний час, що у середньому проводять у системі всі вимоги, що надійшли за одиницю часу, Т_с.вим

Порядок виконання роботи

1. Побудувати графік імовірності станів P_k від k для N-канальної СМО з очікуванням, якщо на вхід надходить найпростіший потік вимог з інтенсивністю та обслуговування вимог проводиться з інтенсивністю , де N_п – номер за списком, m – номер групи, N – кількість каналів обслуговування. Кількість каналів обслуговування визначається з таблиці 5.1.