Дискретно-подійне моделювання

Дискретно-подійне моделювання (англ. discrete-event simulation, DES) моделює роботу системи як (дискретної) хронологічної послідовності подій. Кожна подія відбувається у визначений момент часу і відбивається у зміні стану системи^[en][1]. Вважається, що між послідовними подіями не відбувається жодних змін у системі; таким чином, під час моделювання можна безпосередньо перейти до часу виникнення наступної події, яка називається подією наступною у часі (англ. next-event time progression).

Крім підходу заснованого на подіях наступних у часі, існує також альтернативний підхід, який називається послідовністю подій з фіксованим збільшенням часу (англ. fixed-increment time progression), коли час розбивається на невеликі часові відрізки, а стан системи оновлюється відповідно до набору подій / заходів, що відбуваються у фіксований проміжок часу^[2]. Оскільки не кожен проміжок часу потрібно імітувати, то моделювання події наступної у часі зазвичай може працювати набагато швидше, ніж відповідне моделювання часу з фіксованим збільшенням.

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

Поширеною вправою при навчанні побудові дискретно-подійної моделі є моделювання черги, в якій клієнти приїжджають у банк, щоб їх обслуговував касир. У цьому прикладі системними об'єктами є Черга-Клієнтів та Касири. Системні події — це «Прибуття-Клієнта» та «Від'їзд-Клієнта». (Подія Касир-Починає-Обслуговувати може бути частиною логіки подій прибуття та вид'їзду.) Системні стани, які змінюються цими подіями — це Кількість-Клієнтів-у-Черзі (ціле число від 0 до n) та Статус-Касира (зайнятий або вільний). Випадкові змінні, які потрібно охарактеризувати для стохастичного моделювання цієї системи, — це «Час-між-прибуттям-замовників» та «Час-Обслуговування-Касиром». Агентський підхід, який використовується для моделювання продуктивності оптимальної паралельної дискретно-подійної моделі є ще одним прикладом моделювання дискретних подій^[3].

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

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

Основний компонент системи, що синхронізує зміни в системі (виникнення подій).

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

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

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

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

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

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

Основні дані, які збираються в системах дискретно-подійного моделювання:

• Середня зайнятість (доступність) ресурсів
• Середня кількість клієнтів у черзі
• Середній час очікування в черзі

Умовами для завершення можуть бути:

• Виникнення заданої події (наприклад, досягнення 10-хвилинного часу очікування в черзі)
• Проходження заданої кількості циклів годинником у системі моделювання

Основний цикл моделювання дискретних подій є приблизно таким:

• Ініціалізувати Умову Завершення зі значенням FALSE.
• Ініціалізувати змінні стану системи.
• Ініціалізувати Годинник (зазвичай починається з нульового часу).
• Запланувати початкову подію (тобто внести якусь початкову подію до Списку Подій).

Поки (Умову Завершення має значення FALSE), виконувати наступне:

• Встановити Годинник на час наступної події.
• Зробіть наступну подію та видалити зі Списку Подій.
• Оновити Статистику.

• Створити статистичний звіт.

Pidd (1998) запропонував трифазний підхід до дискретного моделювання подій. При такому підході перша фаза полягає у переході до наступної хронологічної події. Другий етап полягає у виконанні всіх подій, які безумовно відбуваються в цей час (вони називаються Б-подіями). Третя фаза полягає у виконанні всіх подій, які умовно відбуваються в цей час (вони називаються У-подіями). Трифазний підхід — це уточнення підходу на основі подій, в якому одночасні події впорядковані так, щоб максимально ефективно використовувати комп'ютерні ресурси. Трифазний підхід використовується у ряді програмних пакетів комерційного моделювання, але, з точки зору користувача, специфіка базового методу моделювання, як правило, прихована.

Системи дискретно-подійного моделювання — це найчастіше предметно-орієнтовані мови програмування або бібліотеки для високорівневих мов. Серед найбільш відомих: Arena [Архівовано 18 травня 2017 у Wayback Machine.], AnyLogic, SIMSCRIPT, SLAM, SIMAN, AweSim, GPSS.

Підхід імітаційного моделювання доволі добре оснащений, щоб допомагати користувачам виявляти проблеми в комплексних середовищах. Роман «Ціль» засновника теорії обмежень Еліяху Моше Голдрата ілюструє важливість розуміння «вузьких місць» системи. Тільки процес покращення цих «вузьких місць» допоможе покращити систему в цілому. В багатьох організаціях такими вузькими місцями стають приховані надмірні запаси, перевиробництво чи змінність процесів. За допомогою ретельного документування системи всередині моделі можна побачити цілісний вигляд всієї системи.

Зазвичай, операційна кімната поділена між кількома хірургічними відділеннями. Детальне розуміння цієї процедури дозволить збільшити кількість пацієнтів, яку вона зможе прийняти. Наприклад, якщо операція на серці триває чотири години, то збільшення тривалості роботи операційної з восьми до дев'яти годин не підвищить її пропускну здатність. З іншого боку, процедура видалення грижі займає в середньому 20 хвилин і додаткова година роботи теж не принесе значного покращення, якщо не врахувати місткість і середній час, що проводять пацієнти в післяопераційному відділенні.

Багато ідей покращення систем побудовані на озвучених принципах, проте доведені технології (Lean, Six Sigma, TQM тощо) нездатні покращити цілу систему. Імітаційна модель дозволяє користувачу розуміти і тестувати ідеї покращення продуктивності в контексті цілої системи.

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

Дискретно-подійне моделювання використовується в комп'ютерних мережах для симуляції нових протоколів для різних сценаріїв трафіку перед розгортанням.

• Агентне моделювання
• Системна динаміка
• Імітаційне моделювання
• Математичне моделювання
• Математична модель

• Жерновий, Ю. В. (2007). ІМІТАЦІЙНЕ МОДЕЛЮВАННЯ СИСТЕМ МАСОВОГО ОБСЛУГОВУВАННЯ (Українська) . Львів: Видавничий центр ЛНУ імені Івана Франка. с. 307.
• Myron H. MacDougall (1987). Simulating Computer Systems: Techniques and Tools. MIT Press.
• William Delaney; Erminia Vaccari (1988). Dynamic Models and Discrete Event Simulation. Dekker INC.
• Roger W. McHaney (1991). Computer Simulation: A Practical Perspective. Academic Press.
• Michael Pidd (1998). Computer simulation in management science – fourth edition. Wiley.
• A, Alan Pritsker, Jean J. O'Reilly (1999). Simulation with Visual SLAM and AweSim. Wiley.
• Averill M. Law; W. David Kelton (2000). Simulation modeling and analysis – third edition. McGraw–Hill.
• Bernard P. Zeigler; Herbert Praehofer; Tag Gon Kim (2000). Theory of modeling and simulation: Integrating discrete event and continuous complex dynamic systems – second edition. Academic Press.
• Jerry Banks; John Carson; Barry Nelson; David Nicol (2005). Discrete-event system simulation – fourth edition. Pearson.
• James J. Nutaro (2010). Building software for simulation: theory and algorithms, with applications in C++. Wiley.