Diszkrét esemény szimuláció - Discrete-event simulation

A diszkrét-esemény szimuláció ( DES ) modellek a művelet egy rendszer , mint egy ( diszkrét ) események sorrendjét az időben. Minden esemény bekövetkezik egy adott időpillanatban, és jeleket a változás állami rendszerben. Az egymást követő események között feltételezzük, hogy a rendszerben nem történik változás; így a szimulációs idő közvetlenül a következő esemény bekövetkezési idejére ugorhat, amelyet a következő esemény időbeli progressziójának nevezünk .

A következő esemény időbeli progressziója mellett létezik egy alternatív megközelítés is, az úgynevezett fix növekményű idő progresszió , ahol az időt apró időszeletekre bontjuk, és a rendszer állapotát az adott időben zajló események / tevékenységek halmazának megfelelően frissítjük. szelet. Mivel nem minden egyes szeletet kell szimulálni, a következő esemény időszimulációja általában sokkal gyorsabban futtatható, mint egy megfelelő fix növekedésű időszimuláció.

A DES mindkét formája ellentétben áll a folyamatos szimulációval , amelyben a rendszer állapota az idő folyamán folyamatosan változik az állapotváltozók változásának sebességét meghatározó differenciálegyenletek halmaza alapján .

Példa

A diszkrét eseményszimulációk felépítésének elsajátításának egyik gyakori gyakorlata a sor modellezése , például az ügyfelek egy bankhoz érkeznek, hogy egy pénztár szolgáljon. Ebben a példában a rendszer entitások: Ügyfél-várólista és Tellerek . A rendszeresemények: Ügyfél-Érkezés és Ügyfél-Távozás . (A Teller-Begins-Service esemény része lehet az érkezési és indulási események logikájának.) A rendszerállapotok, amelyeket ezen események megváltoztatnak, a várólisták száma a sorban (egész szám 0-tól n) és Teller-Status (foglalt vagy tétlen). A rendszer sztochasztikus modellezéséhez meg kell jellemezni a véletlenszerű változókat : Ügyfél-Interrrival-Time és Teller-Service-Time . Az optimista párhuzamos diszkrét eseményszimulátor teljesítménymodellezésének ügynökalapú keretrendszere egy másik példa a diszkrét eseményszimulációra.

Alkatrészek

A rendszeresemények bekövetkezésének logikája mellett a diszkrét eseményszimulációk a következőket tartalmazzák:

  • Prioritási sor,
  • Animációs eseménykezelő és
  • Idő újra normalizálás kezelő (amikor a szimuláció fut, az időváltozók pontossága elvész. Egy idő után az összes időváltozót normalizálni kell az utolsó feldolgozott eseményidő kivonásával).

Állapot

A rendszerállapot olyan változók összessége, amely rögzíti a vizsgált rendszer kiemelkedő tulajdonságait. Az S (t) időbeli állapotpálya matematikailag ábrázolható egy lépésfüggvénnyel, amelynek értéke változhat, amikor egy esemény bekövetkezik.

Óra

A szimulációnak nyomon kell követnie az aktuális szimulációs időt, bármilyen mértékegységben alkalmas a modellezendő rendszerre. Diszkrét eseményszimulációkban a folyamatos szimulációkkal ellentétben az idő „ugrál”, mert az események pillanatnyiak - az óra a szimuláció előrehaladtával a következő esemény kezdési időpontjára ugrik.

Események listája

A szimuláció fenntartja a szimulációs események legalább egy listáját. Ezt néha függőben lévő eseménykészletnek hívják, mert felsorolja azokat az eseményeket, amelyek korábban szimulált esemény eredményeként függőben vannak, de amelyeket még maguknak nem kell szimulálniuk. Az eseményeket az esemény bekövetkezésének időpontja és típusa írja le, megjelölve az esemény szimulálásához használt kódot. Gyakori, hogy az eseménykódot paraméterezzük, ebben az esetben az eseményleírás az eseménykód paramétereit is tartalmazza.

Ha az események pillanatnyiak, akkor az idővel kiterjedő tevékenységeket eseménysorozatokként modellezik. Egyes szimulációs keretrendszerek lehetővé teszik egy esemény idejének intervallumként történő megadását, megadva az egyes események kezdési és befejezési idejét.

A pillanatnyi eseményeken alapuló egyszálú szimulációs motoroknak csak egy aktuális eseményük van. Ezzel szemben a többszálas szimulációs motorok és az intervallumalapú eseménymodellt támogató szimulációs motorok több aktuális eseményt is tartalmazhatnak. Mindkét esetben jelentős problémák vannak az aktuális események szinkronizálásával.

A függő esemény halmaz általában szervezett, mint a prioritási sor , rendezve az esemény időpontját. Vagyis, függetlenül az események hozzáadásának sorrendjétől az eseményhalmazba, szigorúan időrendben kerülnek eltávolításra. Különböző prioritási sorok megvalósítását tanulmányozták a diszkrét eseményszimuláció keretében; A vizsgált alternatívák közé tartoztak a fák , az átugrási listák , a naptári és a létra sorok. A masszívan párhuzamos gépek , mint például a multi-core vagy többmagos CPU-k, a függőben lévő esemény halmaz lehet végrehajtani támaszkodva nem blokkoló algoritmusok , annak érdekében, hogy csökkentse a költségeit közötti szinkronizáció a konkurens szálak.

Általában az eseményeket dinamikusan ütemezik a szimuláció előrehaladtával. Például a fent említett banki példában a C ÜGYFEL-ÉRKEZÉS esemény t időpontban, ha a CUSTOMER_QUEUE üres és a TELLER tétlen lenne, a t + s időpontban bekövetkező későbbi CUSTOMER-DEPARTURE esemény létrehozását tartalmazná, ahol s a SERVICE-TIME disztribúcióból generált szám.

Véletlenszám-generátorok

A szimulációnak különféle véletlenszerű változókat kell generálnia , a rendszer modelljétől függően. Ezt egy vagy több ál-véletlenszerű számgenerátor valósítja meg . Az ál-véletlenszerű számok használata a valódi véletlenszámokkal szemben előnyös, ha egy szimulációhoz pontosan ugyanolyan viselkedésű ismétlésre van szükség.

A diszkrét eseményszimulációban alkalmazott véletlenszám-eloszlások egyik problémája az, hogy az eseményidők állandó állapotú eloszlása ​​nem biztos, hogy előre ismert. Ennek eredményeként a függőben lévő eseménykészletbe helyezett események kezdeti halmazának nem lesz az egyensúlyi eloszlást reprezentáló érkezési ideje. Ezt a problémát általában a szimulációs modell rendszerindításával oldják meg. Csak korlátozott erőfeszítéseket tesznek arra, hogy reális időket rendeljenek a függőben lévő események kezdeti halmazához. Ezek az események azonban további eseményeket ütemeznek, és az idő múlásával az események eloszlása ​​megközelíti állandó állapotát. Ezt nevezzük a szimulációs modell bootstrapelésének . A futó modellből származó statisztikák összegyűjtésekor fontos, hogy figyelmen kívül hagyjuk az egyensúlyi állapot elérése előtt bekövetkező eseményeket, vagy elég hosszú ideig futtassuk a szimulációt, hogy a rendszerindítási viselkedést elnyomja az egyensúlyi állapot viselkedése. (A bootstrapping kifejezésnek ez a használata szembeállítható a statisztikákban és a számítástechnikában egyaránt ).

Statisztika

A szimuláció általában nyomon követi a rendszer statisztikáit , amelyek számszerűsítik az érdekes szempontokat. A banki példában érdekes az átlagos várakozási idők nyomon követése. Egy szimulációs modellben a teljesítménymutatók analitikusan nem a valószínűségeloszlásokból származnak , hanem a replikációk átlagaként , vagyis a modell különböző futtatásaként. A konfidencia intervallumokat általában úgy hozzák létre, hogy segítsenek a kimenet minőségének értékelésében.

Befejező feltétel

Mivel az események rendszerindítás alatt állnak, elméletileg egy diszkrét eseményszimuláció örökké futhat. Tehát a szimuláció tervezőjének el kell döntenie, hogy a szimuláció mikor fejeződik be. A tipikus választási lehetőségek a „t időpontban” vagy „n eseményszám feldolgozása után”, vagy általánosabban: „amikor az X statisztikai mérőszám eléri az x értéket”.

Háromfázisú megközelítés

Pidd (1998) a diszkrét eseményszimuláció háromfázisú megközelítését javasolta. Ebben a megközelítésben az első szakasz a következő kronológiai eseményre ugrás. A második szakasz az összes olyan esemény végrehajtása, amely feltétel nélkül bekövetkezik abban az időben (ezeket B-eseményeknek nevezzük). A harmadik fázis az összes feltételesen bekövetkező esemény végrehajtása (ezeket C-eseményeknek nevezzük). A háromfázisú megközelítés az eseményalapú megközelítés finomítása, amelyben az egyidejű eseményeket úgy rendezik meg, hogy a lehető leghatékonyabban használják ki a számítógépes erőforrásokat. A háromfázisú megközelítést számos kereskedelmi szimulációs szoftvercsomag használja, de a felhasználó szempontjából az alapul szolgáló szimulációs módszer sajátosságai általában rejtettek.

Általános felhasználások

Folyamatproblémák diagnosztizálása

A szimulációs megközelítések különösen jól felszereltek ahhoz, hogy segítsenek a felhasználóknak összetett környezetekben diagnosztizálni a problémákat. A korlátozások elmélete szemlélteti a rendszer szűk keresztmetszeteinek megértésének fontosságát. A szűk keresztmetszetek azonosítása és eltávolítása lehetővé teszi a folyamatok és az egész rendszer javítását. Például a feldolgozóipari vállalkozásoknál szűk keresztmetszeteket okozhat a túlzott készlet, a túltermelés , a folyamatok változékonysága és az útválasztás vagy a sorrendezés változékonysága. A rendszer pontos dokumentálásával egy szimulációs modell segítségével madártávlatból lehet képet kapni a teljes rendszerről.

A rendszer működő modellje lehetővé teszi a menedzsment számára, hogy megértse a teljesítményvezérlőket. Egy szimuláció felépíthető úgy, hogy tetszőleges számú teljesítménymutatót tartalmazzon, például a munkavállalók kihasználtságát, az időben történő kézbesítési arányt, a selejtarányt, a készpénzforgalmat stb.

Kórházi alkalmazások

A műtőt általában több sebészeti tudományág osztja meg. Ezen eljárások természetének jobb megismerése révén növelhető a beteg áteresztőképessége. Példa: Ha egy szívműtét átlagosan négy órát vesz igénybe, a műtő beosztásának megváltoztatása nyolc rendelkezésre álló óráról kilencre nem növeli a beteg áteresztőképességét. Másrészt, ha a sérveljárás átlagosan húsz percet vesz igénybe, egy további óra biztosítása szintén nem eredményezhet megnövekedett áteresztőképességet, ha nem vesszük figyelembe a helyreállítási helyiségben töltött kapacitást és átlagos időt.

Laboratóriumi teszt teljesítményjavító ötletek

Számos rendszerfejlesztési ötlet szilárd alapelvekre épül, bevált módszerek ( Lean , Six Sigma , TQM stb.) Mégsem képesek javítani a teljes rendszeren. A szimulációs modell lehetővé teszi a felhasználó számára, hogy megértse és tesztelje a teljesítménynövelés ötletét a teljes rendszer összefüggésében.

A tőkebefektetési döntések értékelése

Lásd még: Monte Carlo-módszerek a pénzügyekben , vállalati pénzügyek § Tőkebefektetési döntések és Vállalati pénzügyek § A bizonytalanság számszerűsítése

A potenciális beruházások modellezésére általában szimulációs modellezést alkalmaznak. A befektetések modellezésével a döntéshozók megalapozott döntéseket hozhatnak és értékelhetik a lehetséges alternatívákat.

Hálózati szimulátorok

Fő cikk: Hálózati szimuláció

A diszkrét eseményszimulációt a számítógépes hálózatban új protokollok, különböző rendszerarchitektúrák (elosztott, hierarchikus, központosított, P2P) szimulálására használják a tényleges telepítés előtt. Lehetőség van különböző értékelési mutatók meghatározására, mint például a szolgáltatás ideje, a sávszélesség, az eldobott csomagok, az erőforrás-fogyasztás stb.

Lásd még

Rendszermodellezési megközelítések:

Számítási technikák:

Szoftver:

Szakterületek:

Hivatkozások

További irodalom

  • Myron H. MacDougall (1987). Számítógépes rendszerek szimulálása: technikák és eszközök . MIT Press.
  • William Delaney; Erminia Vaccari (1988). Dinamikus modellek és diszkrét eseményszimuláció . Dekker INC.
  • Roger W. McHaney (1991). Számítógépes szimuláció: gyakorlati szempont . Academic Press.
  • Michael Pidd (1998). Számítógépes szimuláció a menedzsment tudományban - negyedik kiadás . Wiley.
  • A, Alan Pritsker, Jean J. O'Reilly (1999). Szimuláció a Visual SLAM és az AweSim segítségével . Wiley.CS1 maint: több név: szerzők listája ( link )
  • Averill M. Law; W. David Kelton (2000). Szimulációs modellezés és elemzés - harmadik kiadás . McGraw – Hill.
  • Bernard P. Zeigler; Herbert Praehofer; Tag Gon Kim (2000). Modellezés és szimuláció elmélete: Diszkrét események és folyamatos komplex dinamikus rendszerek integrálása - második kiadás . Academic Press.
  • Jerry Banks; John Carson; Barry Nelson; David Nicol (2005). Diszkrét eseményrendszer-szimuláció - negyedik kiadás . Pearson.
  • James J. Nutaro (2010). Szimulációs szoftver építése: elmélet és algoritmusok, C ++ alkalmazással . Wiley.