Discrete event simulation/cs

Úvod

Diskrétní simulace (discrete-event simulation) modeluje chod systému jako diskrétní (nespojitý) sled událostí v čase. Každá událost se objevuje v konkrétním časovém okamžiku a značí změnu stavu v systému. Mezi dvěma po sobě jdoucími událostmi se nepředpokládá žádná změna systému, takže simulace může přímo přeskočit v čase z jedné události na druhou.

Diskrétní simulace je opakem spojité simulace, která kontinuálně zaznamenává dynamiku systému v čase. Spojitá simulace může být také označena jako simulace založená na činnostech. Čas je rozdělen na malé intervaly a stav systému je aktualizován na základě množiny činností, které se odehrávají v daném časovém intervalu. Protože diskrétní simulace nemusí zpracovávat každý časový interval, mohou běžet mnohem rychleji než odpovídající spojité simulace.

Jinou alternativou k simulaci založené na událostech je procesně založená simulace. V tomto přístupu každá činnost koresponduje s odděleným procesem, kde proces je typicky simulován vláknem v simulačním programu. V tomto případě diskrétní události reprezentované vlákny způsobují pozastavení nebo aktivaci jiných vláken a aktualizaci systémového stavu.

Diskrétní simulace se využívá pro dynamickou simulaci business procesů (modely front). Narozdíl od statických procesních diagramů, které jen znázorňují určitý proces, mohou být modely front určeny i pro analýzu vlastností a výkonnosti procesů. V modelech front procházejí systémem jednotky systémové produkce, což mohou být výrobky, faktury, zákazníci apod. Většina reálných problémů je příliš složitá nato, aby byla řešitelná analytickými metodami, lze je tak řešit jen simulací. Simulace umožňuje pozorování průchodu jednotek systémem a odhalování míst, kde se průchod zbržďuje (tzv. úzkých míst - bottlenecks), identifikaci neefektivností, vzájemné srovnávání různých úprav systému atd.

Zatímco procesní diagramy se zaměřují na strukturu, jsou víceméně obecné, vyžadují relativně méně hlubokou analýzu a jejich použití je snadnější, dynamické modely front se zaměřují na parametry, jsou detailnější, poskytují numerický výstup a můžeme je tak porovnat s reálnými daty.

Spojitá simulace se pak využívá v přírodních vědách (fyzice, meteorologii) nebo pro systémovou dynamiku v sociálních vědách.

Základní modelovací konstrukty

Plnohodnotné softwarové nástroje s GUI pro tvorbu diskrétních simulací spojuje určitá množina modelovacích prvků, pomocí kterých lze zkonstruovat výsledný model. Následuje výčet a popis obvyklých základních skupin konstruktů, v závorce pojmenování v modelovacích nástrojích (Arena, ExtendSim, Simprocess).

• Vytváření entit (Create/Generate) – vytváří entity vstupující do modelu, a to na základě určitého rozvrhu, náhodně, za určitých podmínek apod.

• Rušení entit (Dispose/Exit) – zahazuje entity, které prošly modelem, umožňuje sběr statistických dat o entitách

• Čekání ve frontě, zpoždění (Queue, Delay) – entity mohou být zařazovány do fronty, dokud není naplněna jejich kapacita. Fronty mohou být typu FIFO, LIFO nebo řazeny podle priority či hodnoty atributu. Entita pak může být v procesu zpožděna, lze přitom sbírat statistická data apod.

• Zpracování entit, transformace, složení, rozdělení, vytvoření kopie, převod apod. (Processing, Transform, Assemble, Split, Join, Clone, Transfer, ...) - zajištění zpracování entit, může se jednat např. o složení entity z více jiných entit pocházejících z různých zdrojů, transformaci z jedné entity na jinou, rozdělení a případně opětovné seskupení, vytvoření kopie entity, přenesení entity do jiné části modelu nebo do jiného modelu atd.

• Směrování entit, rozhodování, větvení, sloučení, brána (Routing, Decide, Branch, Merge, Gate) – stará se o směrování entit, reprezentuje proces rozhodování na základě určitých podmínek nebo pravděpodobnostních hodnotách. Cesty, kterými entity proudí, mohou být podle těchto charakteristik rozvětveny. Sloučení (Merge) umožňuje sloučení více spojovacích konektorů do jednoho, konstrukt Brána (Gate) pak shromažďuje entity do fronty dokud není obdržen určitý signál, který uvolní entity pro další událost.

• Vytvoření a rušení dávky (Batch, Unbatch/Separate) – umístí určitý počet entit do dávky k jejich hromadnému zpracování. Entity jsou řazeny při tvorbě dávky do fronty dokud není shromážděn potřebný počet entit a vytvořena jedná entita reprezentující dávku. Pokud je dávka dočasná, je potřeba dávku později zrušit a jednotlivé entity oddělit.

• Nastavení atributu (Assign) – přiřadí nebo změní hodnotu proměnné, atributu entity nebo modelu

• Práce se zdroji (Resources) – zpracování zdrojů v modelu, může zahrnovat jejich získání, uvolnění, spotřebu, zaznamenání jejich ceny, stavu apod.

Mezi další modelovací prvky patří synchronizace vstupů, uskladnění entit, konstrukty pro práci s externími soubory a jiné.

Komponenty diskrétní simulace

Kromě reprezentace systémových stavových proměnných obsahuje diskrétní simulace tyto prvky:

• Hodiny – je potřeba časově zachytit jednotlivé kroky simulace, narozdíl od simulace v reálném čase se přeskakuje po vykonání jedné události na začátek události následující

• Seznam událostí – pro simulaci je třeba mít aspoň jeden seznam událostí, které se mají provést. V angličtině se pro seznam událostí vžil pojem Pending event set. Událost je určena časem, ve kterém se projeví, a svým typem. Seznam událostí je obvykle organizován jako prioritní fronta.

• Generátor náhodných čísel – v simulaci je potřeba generovat náhodná čísla různého druhu, odvislé od typu modelovaného systému. To je obvykle řešeno jedním nebo více generátory pseudonáhodných čísel.

• Statistiky – kvantifikují aspekty, které jsou ústředním předmětem zájmu

• Koncové podmínky – musí být stanoveny podmínky, za kterých simulace končí. Protože start událostí je založen na samospouštěcích mechanismech, může běžet diskrétní simulace teoreticky donekonečna. Je proto na tvůrci simulace, aby určil, kdy simulace končí, tedy, obecně řečeno, kdy statistická veličina X dosahuje hodnoty x.

Využití

Simulace je nezbytná pro porozumění, analyzování a předpovídání chování komplexních a velkokapacitních systémů. Slouží k porozumění o fungování existujících systému nebo pomáhá navrhovat ještě neexistující systémy. V následující tabulce jsou shrnuty obory, oblasti použití a druhy aplikací diskrétních simulací:

Obor	Oblast použití	Druh aplikace
Výroba	letecký průmysl, biotechnologie, zemědělství, potravinářství, polovodičový, automobilový a farmaceutický průmysl, spotřebitelské produkty	management zásob a zdrojů aplikace metod Lean a Six Sigma, rozvrhování, kapacitní plánování, vyhodnocování procedur
Služby	maloobchod, bankovnictví, finančnictví, pohostinství, hoteliérství, pojišťovnictví, veřejné služby	vylaďování úrovně služeb, analýza průchodu, rozvrhování, vyhodnocování procedur, aplikace metod Lean a Six Sigma, analýza toku zakázek
Komunikace / sítě	call centra, satelitní, pozemní a vzdušné komunikační systémy	kapacitní plánování, vyhodnocování výkonnosti, analýza průchodu, určování spolehlivosti a chybové tolerance
Doprava / manipulace se zbožím	aerolinky, železnice, doprava, pošta, logistika, skladování	havarijní plánování, rozvrhování, vylaďování úrovně služeb, aplikace metod Lean a Six Sigma

Přehled nástrojů pro diskrétní simulaci

Open source software

• adevs – knihovna jazyka C++ pro tvorbu diskrétních simulací, adevs je založen na DEVS (Discrete Event System Specification) a modelovacích formalismech Dynamic DEVS, podporuje paralelní diskrétní simulace a běhové prostředí pro jazyk OpenModelica

• CPN_tools – vysokoúrovňový nástroj pro analýzu modelu front, loistických modelů. Umožňuje modelování Petriho sítí, podporuje základní, časové a barevné Petriho sítě

• Facsimile – knihovna pro 3D diskrétní simulace, využitelná pro průmyslové simulační projekty v inženýrském nebo výrobním prostředí

• Galatea – platforma pro tvorbu různých druhů simulací

• MASON – zkratka pro Multi-Agent Simulator Of Neighborhoods (nebo také Networks), knihovna pro tvorbu rozsáhlých rychlých diskrétních multiagentních simulací v Javě, výstupy MASONu jsou platformově nezávislé. Knihovna obsahuje 2D a 3D nástroje pro vizualizaci, která může být kdykoli přidána odstraněna nebo změněna. Modely jsou na vizualizaci nezávislé. Modely mohou být obnovovány na základě kontrolních bodů. Umožňuje vytváření tabulek, grafů, výstupních datových proudů, PNG snímků, videí ve formátu Quicktime.

• PowerDEVS – softwarový nástroj pro modelování podle DEVS (Discrete Event System Specification) a simulace orientované na hybridní systémy

• SimPy – freewarový, procesní, objektově-orientovaný jazyk založený na Pythonu pro tvorbu diskrétních simulací. Poskytuje modelovací nástroj s komponentami pro tvorbu simulačních modelů, pro aktivní entity jako jsou zákazníci, zprávy apod. Dále pak pro pasivní komponenty, které vytváří body přetížení s omezenou kapacitou jako jsou servery, kontrolní přepážky, tunely apod. V SimPy existují dva druhy vyrovnávacích prvků (Buffers), úrovně (Levels) k uložení kvantitativních veličin a sklady (Stores) k uložení množin objektů. Obsahuje příkazy pro podporu interakce mezi entitami. Poskytuje objekty k podpoře sběru statistických dat.

• SystemC – sada tříd a maker pro C++ poskytujících rozhraní pro tvorbu diskrétních simulací

• Tortuga – softwarový framework pro diskrétní simulace v Javě. Simulace v Tortuze může být napsána ve formě interaktivních procesů nebo plánovaných událostí

Komerční nástroje

diskrétní simulace v prostředí ExtendSim

• AnyLogic – grafický nástroj pro tvorbu simulací s podporou diskrétních událostí, systémové dynamiky a agentního modelování. U diskrétních simulací praktikuje stejný přístup jako GPSS (General Purpose Simulation System), ale poskytuje některé další rysy: kombinování různých přístupů, dynamickou animaci, přístup k databázovému systému, možnost importu DXF (Drawing Exchange Format) souborů

• Arena – nástroj pro vytváření diskrétních simulací. Využívá simulační jazyk SIMAN. Od verze 14 podporuje 3D vizualizaci. Arena umožňuje uživateli vytvářet model umísťováním modulů v podobě okének různých tvarů. Moduly reprezentují procesy nebo logiku modelu. Propojení modulů zajišťují spojovací linky, dohromady tak určují tok entit modelem. Program umožňuje zaznamenávat statistická data, přičemž jejich výstup je zprostředkován pomocí reportů. Arenu používají pro tvorbu simulací i velké společnosti, které potřebují simulovat pokročilé business procesy.

• CLASS (Configurable Layout and Simulation System) – navržen pro logistický sektor, umožňuje rychlé a jednoduché 2D a 3D modelování velkoobchodů, dopravního provozu, automobilové logistiky apod.

• Enterprise dynamics – simulační software, který umožňuje drag-and-drop modelování, 2D a 3D animaci

• ExtendSim – program pro modelování diskrétních, spojitých i agentově-založených simulací i kombinaci spojitých a diskrétních simulací. S mnoha vlastností programu lze zmínit např. podporu 2D a 3D animace, dynamické přizpůsobení nastavení při běhu simulace nebo evoluční optimalizaci. Pomocí zabudovaných API lze přistupovat ke kódům vytvořeným v různých programovacích jazycích.

• Flexsim – software pro diskrétní simulace

• GoldSim – kombinuje systémovou dynamiku s prvky diskrétní simulace

• Lanner L-SIM Server – nástroj založený na Javě pro simulaci procesních modelů založených na BPMN 2.0

• Lanner WITNESS – platforma pro diskrétní simulace, s grafickým 2D, 3D a skriptovacím rozhraním pro modelování procesů

• MS4 Modeling Environment – softwarové prostředí založené na metodologii DEVS pro diskrétní a hybridní modely. Kombinace frameworků DEVS a SES (System Entity Structure) umožňuje prototypování, modelování SoSE (System of Systems Engineering) a simulace.

• NetSim – software pro simulaci sítí se zabudovaným vývojovým prostředím

• Plant Simulation – software pro simulaci a optimalizaci výrobních systémů a procesů

• Process Playground – webový program pro tvorbu diskrétních simulací pro zlepšení výrobních procesů. Pomocí objektů, vstupů a automatizovaných prvků pomáhá definovat existující procesní toky, rozhodovací pravidla a datové vstupy a simulovat procesní konfiguraci

• ProModel – software pro vytváření diskrétních simulací určený pro plánování, návrh a vylepšování nových a existujících výrobních procesů, optimalizaci dodavatelského řetězce aj. Metodologie ProModelu staví na třech základních krocích – vizualizaci, analýze a optimalizaci. ProModel umožňuje efektivně předpovídat požadavky na zdroje, přehledně vizuálně demonstrovat vylepšovací procesy, umožňuje tvorbu customizovaných front-end a back-end rozhraní, podporuje ActiveX apod.

• Renque – software pro tvorbu diskrétních simulací s integrovaným skriptováním v jazyce Visual Basic a grafickým rozhraním pro návrh

• SAS Simulation Studio – software pro tvorbu diskrétních simulací, mj. umožňuje i integraci se SAS

• Simcad Pro – software pro dynamické diskrétní a spojité simulace. Pouze vizuální rozhraní, podporuje 2D a 3D animace a mapování toku hodnot (Value stream mapping)

• SimEvents – přidává možnost tvorby diskrétních simulací do MATLABu

• Simio – nástroj pro diskrétní simulaci, který poskytuje objektově založené 3D modelovací prostředí

• Simprocess – nástroj pro tvorbu diskrétních simulací, poskytuje bohaté grafické rozhraní, procesy jsou popsány jako řetězce aktivit, které jsou spojeny s určitou spotřebou zdrojů. V modelu jsou entity, jejichž charakteristiky jsou při průchodu modelem zaznamenávány a poměřovány. Procesy jsou v Simprocessu řízeny generátory náhodných čísel.

• Simul8 – software pro tvorbu diskrétních simulací. Slouží jako nástroj pro plánování, návrh, optimalizaci a reengineering reálné výroby, logistiku apod.

Zastoupení nástrojů pro tvorbu diskrétních simulací ve vyhledávačích

Následující tabulka uvádí absolutní a relativní zastoupení nástrojů pro tvorbu diskrétních simulací podle počtu odkazů ve vyhledávači Google a v aplikaci Google Scholar. Pravá část velké vnější tabulky je pak průměrem podílů odkazů v rámci všeobecné komerční sféry (Google) a akademické sféry (Google Scholar):

Google (k 16.6.2013)	Google Scholar (k 16.6.2013)	Průměr podílů Google a Google Scholar (k 16.6.2013)
Open source nástroje Počet odkazů Podíl SimPy 352000 31,43% Facsimile 58200 5,20% MASON 34800 3,11% SystemC 20100 1,79% PowerDEVS 10400 0,93% Tortuga 6700 0,60% CPN Tools 4410 0,39% adevs 4130 0,37% Galatea 3300 0,29% Komerční nástroje Počet odkazů Podíl ProModel 208000 18,57% ExtendSim 175000 15,63% Arena 91000 8,13% SAS Simulation Studio 44100 3,94% AnyLogic 14900 1,33% Simul8 13700 1,22% Flexsim 12500 1,12% Simio 9890 0,88% Plant Simulation 9820 0,88% Lanner L-SIM Server 8660 0,77% Enterprise dynamics 7680 0,69% Simevents 6510 0,58% Goldsim 5870 0,52% Simprocess 4190 0,37% Simcad Pro 3290 0,29% Netsim 2700 0,24% MS4 Modeling Environment 2430 0,22% Renque 2220 0,20% Lanner WITNESS 1530 0,14% CLASS 1330 0,12% Process Playground 500 0,04%	Open source nástroje Počet odkazů Podíl MASON 2200 14,08% SystemC 1100 7,04% SimPy 323 2,07% Facsimile 225 1,44% CPN Tools 143 0,92% adevs 89 0,57% PowerDEVS 67 0,43% Galatea 27 0,17% Tortuga 25 0,16% Komerční nástroje Počet odkazů Podíl Arena 5710 36,54% ProModel 1510 9,66% Simio 870 5,57% Simul8 757 4,84% AnyLogic 628 4,02% Plant Simulation 449 2,87% Flexsim 281 1,80% Simprocess 267 1,71% Simevents 215 1,38% ExtendSim 214 1,37% Enterprise dynamics 207 1,32% Netsim 200 1,28% Goldsim 63 0,40% SAS Simulation Studio 21 0,13% Simcad Pro 18 0,12% Renque 9 0,06% Lanner WITNESS 7 0,04% MS4 Modeling Environment 1 0,01% CLASS 0 0,00% Lanner L-SIM Server 0 0,00% Process Playground 0 0,00%	Open source nástroje Podíl SimPy 16,75% MASON 8,59% SystemC 4,42% Facsimile 3,32% PowerDEVS 0,68% CPN Tools 0,65% adevs 0,47% Tortuga 0,38% Galatea 0,23% Komerční nástroje Podíl Arena 22,33% ProModel 14,12% ExtendSim 8,50% Simio 3,23% Simul8 3,03% AnyLogic 2,67% SAS Simulation Studio 2,04% Plant Simulation 1,88% Flexsim 1,46% Simprocess 1,04% Enterprise dynamics 1,01% Simevents 0,98% Netsim 0,76% Goldsim 0,46% Lanner L-SIM Server 0,39% Simcad Pro 0,20% Renque 0,13% MS4 Modeling Environment 0,11% Lanner WITNESS 0,09% CLASS 0,06% Process Playground 0,02%

Seznam použitých zdrojů

[1] Šalamon, T. Discrete simulation, podklady k předmětům 4IT495 a 4IT496 vyučované na VŠE Praha. Zdroj: Dokumentový server ISIS VŠE Praha

[2] Uživatelská příručka k softwaru Arena [online]. Poslední změna 30.11.2008. URL: http://iiesl.utk.edu/Courses/IE406%20S07/Slides/Arena%20User's%20Guide.pdf

[3] Uživatelská příručka k softwaru ExtendSim 8 [online]. Poslední změna 12.3.2012. URL: http://www.extendsim.com/downloadphp/index.php?ExtendSim8_manuals.zip

[4] Uživatelská příručka k softwaru Simprocess 4 [online]. Poslední změna 30.4.2007. URL: http://lrss.fri.uni-lj.si/sl/teaching/mis/simprocess/GetStart.pdf

[5] Web projektu MASON [online]. Poslední změna 3.5.2013. URL: http://cs.gmu.edu/~eclab/projects/mason/

[6] Web softwaru ExtendSim [online]. Poslední změna 12.3.2012. URL: http://www.extendsim.com/prods_overview.html

[7] Web společnosti ProModel, informace o produktu ProModel [online]. Poslední změna 23.6.2013. URL: http://www.promodel.com/products/promodel/

[8] Wikipedia, the free encyclopedia. Discrete event simulation [online]. Poslední změna 13.6.2013. URL: http://en.wikipedia.org/wiki/Discrete_event_simulation

[9] Wikipedia, the free encyclopedia. List of discrete event simulation software [online]. Poslední změna 15.6.2013. URL: http://en.wikipedia.org/wiki/List_of_discrete_event_simulation_software