Дискретно-подійне моделювання
Дискретно-подійне моделювання (англ. discrete-event simulation, DES) моделює роботу системи як (дискретної) хронологічної послідовності подій. Кожна подія відбувається у визначений момент часу і відбивається у зміні стану системи[1]. Вважається, що між послідовними подіями не відбувається жодних змін у системі; таким чином, під час моделювання можна безпосередньо перейти до часу виникнення наступної події, яка називається подією наступною у часі (англ. next-event time progression).
Крім підходу заснованого на подіях наступних у часі, існує також альтернативний підхід, який називається послідовністю подій з фіксованим збільшенням часу (англ. fixed-increment time progression), коли час розбивається на невеликі часові відрізки, а стан системи оновлюється відповідно до набору подій / заходів, що відбуваються у фіксований проміжок часу[2]. Оскільки не кожен проміжок часу потрібно імітувати, то моделювання події наступної у часі зазвичай може працювати набагато швидше, ніж відповідне моделювання часу з фіксованим збільшенням.
Обидві форми ДПМ контрастують з безперервним моделюванням, в якому стан системи постійно змінюється з часом відповідно до набору диференціальних рівнянь, які визначають швидкість зміни параметрів стану.
Приклад
Поширеною вправою при навчанні побудові дискретно-подійної моделі є моделювання черги, в якій клієнти приїжджають у банк, щоб їх обслуговував касир. У цьому прикладі системними об'єктами є Черга-Клієнтів та Касири. Системні події — це «Прибуття-Клієнта» та «Від'їзд-Клієнта». (Подія Касир-Починає-Обслуговувати може бути частиною логіки подій прибуття та вид'їзду.) Системні стани, які змінюються цими подіями — це Кількість-Клієнтів-у-Черзі (ціле число від 0 до n) та Статус-Касира (зайнятий або вільний). Випадкові змінні, які потрібно охарактеризувати для стохастичного моделювання цієї системи, — це «Час-між-прибуттям-замовників» та «Час-Обслуговування-Касиром». Агентський підхід, який використовується для моделювання продуктивності оптимальної паралельної дискретно-подійної моделі є ще одним прикладом моделювання дискретних подій[3].
Компоненти системи дискретно-подійного моделювання
Крім змінних, що визначають стан системи, і логіки, що визначає, як відреагує система на якусь певну подію, система дискретно-подійного моделювання містить такі компоненти:
Стан
Стан системи — це набір змінних, що описують характеристики системи. Траєкторія стану в часі може бути представлена у вигляді східчастої функції, значення якої змінюється в момент виникнення події.
Годинник
Основний компонент системи, що синхронізує зміни в системі (виникнення подій).
Список подій
Система моделювання підтримує щонайменше один список подій моделювання. Його ще називають списком очікування подій, оскільки в ньому містяться події, які є результатом попередніх, але самі вони ще повинні бути змодельовані. Подія описується часом, в який вона відбулася та типом.
Засновані на миттєвих подіях однопотокові системи моделювання мають лише одну поточну подію. У свою чергу, багатопотокові системи моделювання та системи моделювання, що підтримують інтервальні події можуть мати кілька поточних подій. Обидва випадки передбачають значні складнощі у синхронізації між поточними подіями.
Список подій зазвичай побудований у вигляді черги з пріоритетом, впорядкованої за часом події. Відповідно, згідно з порядком додавання подій до черги, вони видаляються у строго хронологічному порядку. Існує кілька загальних алгоритмів для черг з пріоритетом, що довели свою ефективність для дискретно-подійного моделювання, зокрема розширюване дерево. Серед сучасніших доробок виділяються зокрема список з пропусками, календарні черги та східчасті черги.
Генератори випадкових чисел
У процесі моделювання повинні генеруватись випадкові значення залежно від типу моделі. Це досягається з використанням одного чи кількох генераторів псевдовипадкових чисел.
Одна з проблем, пов'язаних з генерацією випадкових чисел у дискретно-подійному моделюванні, полягає у тому, що стаціонарний розподіл часу подій може не бути наперед відомим. Як наслідок, початкові події, розміщені у списку очікування подій, не матимуть відповідного до стаціонарного розподілу часу виникнення. Ця проблема зазвичай вирішується заданням початкових даних для моделі. Ці дані визначають додаткові події, і з часом розподіл часу подій досягає стійкого стану. При збиранні статистичних даних про модель важливо або ігнорувати події, що відбулись до досягнення стану стійкості, або проводити спостереження достатньо довго, щоб задана початкова поведінка була перекрита поведінкою у стані стійкості.
Дискретно-подійні моделі поділяються на детерміновані і стохастичні залежно від того, яким чином генеруються події та основні характеристики черг: час, коли відбуваються події, тривалість обслуговування, кількість кієнтів, що поступають в чергу за одиницю часу. Стохастичні дискретно-подійні моделі відрізняються від моделей Монте-Карло наявністю годинника.
Статистика
Основні дані, які збираються в системах дискретно-подійного моделювання:
- Середня зайнятість (доступність) ресурсів
- Середня кількість клієнтів у черзі
- Середній час очікування в черзі
Умови завершення
Умовами для завершення можуть бути:
- Виникнення заданої події (наприклад, досягнення 10-хвилинного часу очікування в черзі)
- Проходження заданої кількості циклів годинником у системі моделювання
Логіка моделювання
Основний цикл моделювання дискретних подій є приблизно таким:
Старт
- Ініціалізувати Умову Завершення зі значенням FALSE.
- Ініціалізувати змінні стану системи.
- Ініціалізувати Годинник (зазвичай починається з нульового часу).
- Запланувати початкову подію (тобто внести якусь початкову подію до Списку Подій).
Цикл виконання
Поки (Умову Завершення має значення FALSE), виконувати наступне:
- Встановити Годинник на час наступної події.
- Зробіть наступну подію та видалити зі Списку Подій.
- Оновити Статистику.
Кінець
- Створити статистичний звіт.
Трифазний підхід
Pidd (1998) запропонував трифазний підхід до дискретного моделювання подій. При такому підході перша фаза полягає у переході до наступної хронологічної події. Другий етап полягає у виконанні всіх подій, які безумовно відбуваються в цей час (вони називаються Б-подіями). Третя фаза полягає у виконанні всіх подій, які умовно відбуваються в цей час (вони називаються У-подіями). Трифазний підхід — це уточнення підходу на основі подій, в якому одночасні події впорядковані так, щоб максимально ефективно використовувати комп'ютерні ресурси. Трифазний підхід використовується у ряді програмних пакетів комерційного моделювання, але, з точки зору користувача, специфіка базового методу моделювання, як правило, прихована.
Реалізація
Системи дискретно-подійного моделювання — це найчастіше предметно-орієнтовані мови програмування або бібліотеки для високорівневих мов. Серед найбільш відомих: Arena, AnyLogic, SIMSCRIPT, SLAM, SIMAN, AweSim, GPSS.
Застосування
Проблеми процесу діагностики
Підхід імітаційного моделювання доволі добре оснащений, щоб допомагати користувачам виявляти проблеми в комплексних середовищах. Роман «Ціль» засновника теорії обмежень Еліяху Моше Голдрата ілюструє важливість розуміння «вузьких місць» системи. Тільки процес покращення цих «вузьких місць» допоможе покращити систему в цілому. В багатьох організаціях такими вузькими місцями стають приховані надмірні запаси, перевиробництво чи змінність процесів. За допомогою ретельного документування системи всередині моделі можна побачити цілісний вигляд всієї системи.
Додатки для лікарень
Зазвичай, операційна кімната поділена між кількома хірургічними відділеннями. Детальне розуміння цієї процедури дозволить збільшити кількість пацієнтів, яку вона зможе прийняти. Наприклад, якщо операція на серці триває чотири години, то збільшення тривалості роботи операційної з восьми до дев'яти годин не підвищить її пропускну здатність. З іншого боку, процедура видалення грижі займає в середньому 20 хвилин і додаткова година роботи теж не принесе значного покращення, якщо не врахувати місткість і середній час, що проводять пацієнти в післяопераційному відділенні.
Ідеї щодо покращення продуктивності лабораторних тестів
Багато ідей покращення систем побудовані на озвучених принципах, проте доведені технології (Lean, Six Sigma, TQM тощо) нездатні покращити цілу систему. Імітаційна модель дозволяє користувачу розуміти і тестувати ідеї покращення продуктивності в контексті цілої системи.
Оцінка інвестицій
Імітаційне моделювання широко використовується для моделювання потенціалу інвестицій. Використовуючи дискретно-подійне моделювання для інвестицій, можна отримати прогнозовані рішення і оцінити потенційні альтернативи.
Симулятори мереж
Дискретно-подійне моделювання використовується в комп'ютерних мережах для симуляції нових протоколів для різних сценаріїв трафіку перед розгортанням.
Див. також
Примітки
- Stewart Robinson (2004). Simulation – The practice of model development and use. Wiley.
- Matloff, Norm. Introduction to Discrete-Event Simulation and the SimPy Language. Процитовано 24 січня 2013.
- Aditya Kurve; Khashayar Kotobi; George Kesidis (2013). An agent-based framework for performance modeling of an optimistic parallel discrete event simulator. Complex Adaptive Systems Modeling 1: 12. doi:10.1186/2194-3206-1-12.
Джерела
- Жерновий, Ю. В. (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.