Основи дискретно-подійного моделювання СМО.

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

Простір станів СМО. 

Розглянемо діаграму станів СМО з одним пристроєм обслуговування (мал.2.5), наприклад, магазин з одним продавцем-касиром.

Мал. 2.5

На вхід системи в моменти часу надходять вимоги. Момент початку обслуговування пристроєм вимоги позначено як , а момент закінчення – . Момент виходу вимоги із системи – . Він збігається з моментом закінчення обслуговування вимоги . Якщо в момент надходження вимоги в систему пристрій обслуговування зайнятий, то вимога стає в чергу (наприклад, вимоги 2, 4, 5, 6, 7, 8). Стан черги визначається кількістю вимог у ній і позицією кожної вимоги в черзі. Після звільнення пристрою перша вимога із черги надходить на обслуговування. Таким чином, простір станів СМО визначається станами пристрою обслуговування й станами черги. Зміна станів системи пов’язана з подіями надходження нової вимоги й заняттям або звільненням пристрою обслуговування. Стан черги також залежить від стану пристрою обслуговування.

З кожною вимогою  зв’язано кілька подій: поява вимоги – , початок обслуговування – , закінчення обслуговування – . Тоді впорядкована безліч подій  у модельному часі описує поводження СМО.

На мал. 2.6 процес обслуговування вимог у СМО з одним пристроєм для обслуговування зображений більш детально.

Якщо пристрій обслуговування зайнятий у момент надходження ї вимоги, то ця вимога змушена ставати в чергу й чекати певний час:

 (функція дії ОЧІКУВАННЯ – яка залежить від умови зайнятості пристрою ). Час обслуговування визначається як  (функція дії ОБСЛУГОВУВАННЯ – яка пов’язана з умовою звільнення пристрою ).

Мал. 2.6

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

Аналогічно можна визначити процес надходження вимог у СМО як впорядковані пари значень  Тут  (функція дії НАДХОДЖЕННЯ –  яка пов’язана з умовою появи вимоги ). Умовою початку дії є умова перевірки стану системи (пристрій зайнятий або вільний, надійшла вимога чи ні). Отже, процес починається тільки тоді, коли змінюється стан системи й виконуються функції дій.

Зміна стану характеризується появою певної події, а початок виконання функції дії – виконанням певних умов.

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

Алгоритм моделювання СМО.

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

Приведемо алгоритм її роботи:

1.Створити динамічний об’єкт «покупець». Такий об’єкт – це структура даних, що містить у собі такі поля: номер покупця – , момент його приходу – , а також, якщо необхідно, властивості покупця або його атрибути (наприклад, пріоритет покупця). Потрібно також запланувати подію приходу покупця на момент часу , тобто записати повідомлення про подію в список майбутніх подій (СМП).

2. Запланувати наступну подію для покупця – запит-призначення ресурсу  (пристрій для обслуговування – продавець) на момент часу . Запланувати прихід наступного об’єкта покупця , тобто визначити подію приходу наступного покупця.

Наступна підпрограма – це підпрограма запиту й призначення ресурсу  вимозі  (у мові GPSS цій підпрограмі відповідає блок SEIZE). Алгоритм її роботи такий:

а) Якщо ресурс  (продавець) може бути відразу призначений вимозі (покупцеві) , то змінити стан ресурсу  на «зайнятий». Запам'ятати момент початку обслуговування вимоги й передати керування підпрограмі обслуговування вимоги

б) Якщо ресурс  зайнятий, то поставити вимогу  в чергу до ресурсу .

Третя підпрограма – підпрограма обслуговування вимоги  (у мові GPSS цій підпрограмі відповідає блок ADVANCE). Алгоритм її роботи дуже простий. Вона повинна визначити подію, що наступає після закінчення обслуговування вимоги  як:

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

Четверта підпрограма – це підпрограма звільнення ресурсу  вимогою  (у мові GPSS цій підпрограмі відповідає блок RELEASE). Алгоритм її роботи такий:

а) Змінити стан ресурсу  на «вільний». Передати керування підпрограмі знищення вимоги.

б) Перевірити наявність у черзі вимог до ресурсу . Якщо вони є, то вибрати вимогу із черги й запланувати для неї подію запиту – призначення ресурсу .

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

Крім вищенаведених підпрограм потрібна підпрограма керування всім процесом моделювання (ПУМ), що запускає процес моделювання й контролює переміщення кожної вимоги («життєвий цикл») під час моделювання шляхом виклику зазначених підпрограм обробки окремих подій. Інше призначення цієї програми - вести список упорядкованих у часі подій - СМП і просувати годинник модельного часу від події до події. У мові GPSS функцію ПУМ виконує програма інтерпретатор.

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

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

На початок моделювання подія, пов’язана з моментом часу  є майбутньою подією й ця подія відбудеться першою. Після того, як показання годинника модельного часу зміниться з на , перша подія видаляється з СМП і виконується підпрограма цієї події. Далі наступає подія 2 і виконується підпрограма цієї події. І так далі до закінчення моделювання.

Структуру імітаційної моделі можна представити у вигляді
(мал. 2.7):

Мал. 2.7

Закінчення процесу моделювання може бути встановлено одним із трьох способів:

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

2. Якщо потік покупців від генератора необмежений, то моделювання можна закінчити після проходження через модель досить великої кількості покупців (наприклад, 1000). Для цього в підпрограмі знищення ставиться лічильник покупців і коли він нарахує потрібну кількість покупців, моделювання припиняється. У мові GPSS такий лічильник організується за допомогою команди START.

3. Задається певний час моделювання, наприклад 480 хв. У цьому випадку поточний модельний час зрівнюється із зазначеним (480 хв.) і як тільки вони стануть рівними, моделювання припиняється.

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

Мережі СМО.

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

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

У загальному вигляді мережу СМО можна зобразити у вигляді графа, вершинами якого є одноканальні або багатоканальні СМО, а дуги вказують напрямок переміщення потоків вимог. Найпростіша мережа СМО зображена на мал. 2.8:

Мал. 2.8

Таку мережу ще називають багатофазною СМО.

Розрізняють замкнутій розімкнуті мережі. У замкнутій мережі немає зовнішніх джерел вимог. У ній завжди є однакова кількість вимог. У розімкнутій мережі є джерела й стоки вимог. На мал. 2.8 зображена розімкнута СМО. На мал. 2.9 показана найпростіша замкнута мережа, що має всього два вузли.

Мал. 2.9

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

У сталому режимі роботи мережі для потоків вимог справедливі закони про сумарні потоки (мал. 2.10):

Мал. 2.10

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