Symulacja zdarzeń dyskretnych - Discrete-event simulation

Symulacji dyskretne zdarzenia ( DES ) modele działania z systemem jako ( dyskretnego ) sekwencji zdarzeń w czasie. Każde zdarzenie występuje w określonym momencie i oznacza zmianę stanu w systemie. Zakłada się, że pomiędzy kolejnymi zdarzeniami nie nastąpi żadna zmiana w systemie; w ten sposób czas symulacji może bezpośrednio przeskoczyć do czasu wystąpienia następnego zdarzenia, co nazywa się postępem czasowym następnego zdarzenia .

Oprócz progresji czasowej następnego zdarzenia istnieje również alternatywne podejście, zwane progresji czasowej ze stałym przyrostem , w którym czas jest dzielony na małe przedziały czasowe , a stan systemu jest aktualizowany zgodnie z zestawem zdarzeń/działań zachodzących w czasie plasterek. Ponieważ nie każdy wycinek czasu musi być symulowany, symulacja czasu następnego zdarzenia może zwykle przebiegać znacznie szybciej niż odpowiadająca jej symulacja czasu o stałym przyroście.

Obie formy DES kontrastują z symulacją ciągłą, w której stan systemu zmienia się w sposób ciągły w czasie na podstawie układu równań różniczkowych określających szybkości zmian zmiennych stanu.

Przykład

Typowym ćwiczeniem w nauce tworzenia symulacji zdarzeń dyskretnych jest modelowanie kolejki , na przykład klientów przychodzących do banku w celu obsługi przez kasjera. W tym przykładzie encje systemowe to Customer-queue i Tellers . Zdarzenia systemowe to Klient-Przyjazd i Klient-Wyjazd . (Zdarzenie Teller-Begins-Service może być częścią logiki zdarzeń przyjazdu i wyjazdu). Stany systemu, które są zmieniane przez te zdarzenia, to liczba klientów w kolejce (liczba całkowita z 0 do n) i stan kasjera (zajęty lub bezczynny). Te zmienne losowe , które muszą charakteryzować się model systemu stochastycznie są klienta Częstotliwość generowania-Time i Tellera-Service-Time . Oparta na agentach platforma do modelowania wydajności optymistycznego równoległego symulatora zdarzeń dyskretnych to kolejny przykład symulacji zdarzeń dyskretnych.

składniki

Oprócz logiki tego, co dzieje się, gdy wystąpią zdarzenia systemowe, dyskretne symulacje zdarzeń obejmują następujące elementy:

  • Kolejka priorytetowa,
  • Obsługa zdarzeń animacji i
  • Obsługa ponownej normalizacji czasu (w miarę przebiegu symulacji zmienne czasowe tracą precyzję. Po pewnym czasie wszystkie zmienne czasowe powinny zostać ponownie znormalizowane przez odjęcie czasu ostatniego przetworzonego zdarzenia).

Stan

Stan systemu to zbiór zmiennych, które przechwytują istotne właściwości badanego systemu. Trajektoria stanu w czasie S(t) może być matematycznie reprezentowana przez funkcję skokową, której wartość może się zmieniać za każdym razem, gdy wystąpi zdarzenie.

Zegar

Symulacja musi śledzić bieżący czas symulacji, w dowolnych jednostkach miary odpowiednich dla modelowanego systemu. W symulacjach zdarzeń dyskretnych, w przeciwieństwie do symulacji ciągłych, czas „przeskakuje”, ponieważ zdarzenia są natychmiastowe – zegar przeskakuje do czasu rozpoczęcia następnego zdarzenia w miarę postępu symulacji.

Lista wydarzeń

Symulacja utrzymuje co najmniej jedną listę zdarzeń symulacji. Jest to czasami nazywane zestawem zdarzeń oczekujących, ponieważ zawiera listę zdarzeń oczekujących w wyniku wcześniej symulowanego zdarzenia, które jeszcze nie zostały zasymulowane. Zdarzenie jest opisane przez czas, w którym występuje, oraz typ, wskazujący kod, który zostanie użyty do zasymulowania tego zdarzenia. Często zdarza się, że kod zdarzenia jest sparametryzowany, w takim przypadku opis zdarzenia zawiera również parametry do kodu zdarzenia.

Gdy zdarzenia są natychmiastowe, działania, które rozciągają się w czasie, są modelowane jako sekwencje zdarzeń. Niektóre struktury symulacyjne pozwalają na określenie czasu zdarzenia jako interwału, podając czas rozpoczęcia i czas zakończenia każdego zdarzenia.

Silniki symulacyjne jednowątkowe oparte na zdarzeniach chwilowych mają tylko jedno zdarzenie bieżące. W przeciwieństwie do tego, wielowątkowe silniki symulacyjne i silniki symulacyjne obsługujące model zdarzeń oparty na interwałach mogą mieć wiele bieżących zdarzeń. W obu przypadkach występują znaczne problemy z synchronizacją między bieżącymi wydarzeniami.

Zestaw oczekujących zdarzeń jest zwykle zorganizowany jako kolejka priorytetowa , posortowana według czasu zdarzenia. Oznacza to, że niezależnie od kolejności, w jakiej zdarzenia są dodawane do zestawu zdarzeń, są one usuwane w ściśle chronologicznej kolejności. Różne implementacje kolejek priorytetowych były badane w kontekście symulacji zdarzeń dyskretnych; zbadane alternatywy obejmowały drzewa splay , listy pomijania , kolejki kalendarza i kolejki drabinkowe . Na maszynach masowo równoległych , takich jak procesory wielordzeniowe lub wielordzeniowe , oczekujący zestaw zdarzeń można zaimplementować w oparciu o algorytmy nieblokujące , w celu zmniejszenia kosztów synchronizacji między współbieżnymi wątkami.

Zazwyczaj wydarzenia są planowane dynamicznie w miarę postępu symulacji. Na przykład we wspomnianym powyżej przykładzie banku zdarzenie KLIENT-PRZYJAZD w czasie t, gdyby KOLEJKA_KLIENTA była pusta, a TELER był bezczynny, obejmowałoby utworzenie kolejnego zdarzenia KLIENT-WYJAZD, które miałoby nastąpić w czasie t+s, gdzie s to numer wygenerowany z dystrybucji SERVICE-TIME.

Generatory liczb losowych

Symulacja wymaga generowania zmiennych losowych różnego rodzaju, w zależności od modelu systemu. Jest to realizowane przez jeden lub więcej generatorów liczb pseudolosowych . Użycie liczb pseudolosowych w przeciwieństwie do prawdziwych liczb losowych jest zaletą, jeśli symulacja wymaga ponownego uruchomienia z dokładnie takim samym zachowaniem.

Jednym z problemów związanych z rozkładami liczb losowych używanymi w symulacji zdarzeń dyskretnych jest to, że rozkłady czasu zdarzeń w stanie ustalonym mogą nie być znane z góry. W rezultacie początkowy zestaw zdarzeń umieszczony w zestawie zdarzeń oczekujących nie będzie miał czasów przybycia reprezentatywnych dla rozkładu stanu ustalonego. Ten problem jest zazwyczaj rozwiązywany przez ładowanie początkowe modelu symulacyjnego. Dokłada się jedynie ograniczonego wysiłku, aby przypisać realistyczne czasy do początkowego zestawu oczekujących wydarzeń. Zdarzenia te jednak planują dodatkowe zdarzenia iz czasem rozkład czasów zdarzeń zbliża się do stanu ustalonego. Nazywa się to ładowaniem początkowym modelu symulacyjnego. Podczas zbierania statystyk z działającego modelu ważne jest, aby albo pominąć zdarzenia, które występują przed osiągnięciem stanu ustalonego, albo uruchomić symulację na tyle długo, aby zachowanie ładowania początkowego zostało przytłoczone zachowaniem stanu ustalonego. (To użycie terminu bootstrapping można skontrastować z jego użyciem zarówno w statystyce, jak i informatyce ).

Statystyka

Symulacja zazwyczaj śledzi statystyki systemu , które określają ilościowo interesujące aspekty. W przykładzie z bankiem interesujące jest śledzenie średniego czasu oczekiwania. W modelu symulacyjnym metryki wydajności nie są wyprowadzane analitycznie z rozkładów prawdopodobieństwa , ale raczej jako średnie z replikacji , czyli z różnych przebiegów modelu. Przedziały ufności są zwykle konstruowane, aby pomóc w ocenie jakości wyników.

Warunek zakończenia

Ponieważ zdarzenia są inicjowane, teoretycznie symulacja zdarzeń dyskretnych może trwać wiecznie. Projektant symulacji musi więc zdecydować, kiedy symulacja się zakończy. Typowe wybory to „w czasie t” lub „po przetworzeniu n liczby zdarzeń” lub, bardziej ogólnie, „gdy miara statystyczna X osiągnie wartość x”.

Podejście trójfazowe

Pidd (1998) zaproponował trójfazowe podejście do symulacji zdarzeń dyskretnych. W tym podejściu pierwszą fazą jest przeskoczenie do następnego wydarzenia chronologicznego. Druga faza polega na wykonaniu wszystkich zdarzeń, które bezwarunkowo zachodzą w tym czasie (są to tak zwane zdarzenia B). Trzecia faza polega na wykonaniu wszystkich zdarzeń, które warunkowo zachodzą w tym czasie (nazywane są one zdarzeniami C). Podejście trójfazowe jest udoskonaleniem podejścia opartego na zdarzeniach, w którym jednoczesne zdarzenia są uporządkowane tak, aby jak najefektywniej wykorzystać zasoby komputera. Podejście trójfazowe jest stosowane w wielu komercyjnych pakietach oprogramowania symulacyjnego, ale z punktu widzenia użytkownika specyfika podstawowej metody symulacji jest na ogół ukryta.

Typowe zastosowania

Diagnozowanie problemów procesowych

Podejścia symulacyjne są szczególnie dobrze przygotowane do pomocy użytkownikom w diagnozowaniu problemów w złożonych środowiskach. Teoria ograniczeń ilustruje znaczenie zrozumienia wąskich gardeł w systemie. Identyfikowanie i usuwanie wąskich gardeł pozwala usprawnić procesy i cały system. Na przykład w przedsiębiorstwach produkcyjnych wąskie gardła mogą być tworzone przez nadmierne zapasy, nadprodukcję , zmienność procesów i zmienność w routingu lub sekwencjonowaniu. Dzięki dokładnemu udokumentowaniu systemu za pomocą modelu symulacyjnego można uzyskać widok całego systemu z lotu ptaka.

Działający model systemu umożliwia kierownictwu zrozumienie czynników wpływających na wydajność. Można zbudować symulację obejmującą dowolną liczbę wskaźników wydajności, takich jak wykorzystanie pracowników, terminowość dostaw, odsetek odpadków, cykle kasowe i tak dalej.

Zastosowania szpitalne

Sala operacyjna jest zazwyczaj podzielona na kilka dyscyplin chirurgicznych. Dzięki lepszemu zrozumieniu natury tych procedur możliwe jest zwiększenie liczby pacjentów. Przykład: Jeśli operacja serca trwa średnio cztery godziny, zmiana harmonogramu sali operacyjnej z ośmiu dostępnych godzin na dziewięć nie zwiększy liczby pacjentów. Z drugiej strony, jeśli procedura przepukliny trwa średnio dwadzieścia minut, zapewnienie dodatkowej godziny może również nie przynieść zwiększenia przepustowości, jeśli nie weźmie się pod uwagę pojemności i średniego czasu spędzonego na sali pooperacyjnej.

Pomysły na poprawę wydajności testów laboratoryjnych

Wiele pomysłów na ulepszenie systemów opiera się na solidnych zasadach, sprawdzonych metodologiach ( Lean , Six Sigma , TQM , itp.), ale nie poprawia całego systemu. Model symulacyjny pozwala użytkownikowi zrozumieć i przetestować pomysł na poprawę wydajności w kontekście całego systemu.

Ocena decyzji dotyczących inwestycji kapitałowych

Zobacz też: Metody Monte Carlo w finansach , Finanse przedsiębiorstw § Decyzje dotyczące inwestycji kapitałowych , oraz Finanse przedsiębiorstw § Ilościowe określenie niepewności

Modelowanie symulacyjne jest powszechnie stosowane do modelowania potencjalnych inwestycji. Dzięki modelowaniu inwestycji decydenci mogą podejmować świadome decyzje i oceniać potencjalne alternatywy.

Symulatory sieciowe

Główny artykuł: symulacja sieci

Dyskretna symulacja zdarzeń jest wykorzystywana w sieci komputerowej do symulacji nowych protokołów, różnych architektur systemu (rozproszonych, hierarchicznych, scentralizowanych, P2P) przed faktycznym wdrożeniem. Możliwe jest zdefiniowanie różnych metryk oceny, takich jak czas usługi, przepustowość, odrzucone pakiety, zużycie zasobów i tak dalej.

Zobacz też

Podejścia do modelowania systemu:

Techniki obliczeniowe:

Oprogramowanie:

Dyscypliny:

Bibliografia

Dalsza lektura

  • Myron H. MacDougall (1987). Symulacja systemów komputerowych: techniki i narzędzia . MIT Naciśnij.
  • Williama Delaneya; Erminia Vaccari (1988). Modele dynamiczne i symulacja zdarzeń dyskretnych . Dekker INC.
  • Roger W. McHaney (1991). Symulacja komputerowa: perspektywa praktyczna . Prasa akademicka.
  • Michaela Pidda (1998). Symulacja komputerowa w naukach o zarządzaniu – wydanie czwarte . Wileya.
  • A, Alan Pritsker, Jean J. O'Reilly (1999). Symulacja z Visual SLAM i AweSim . Wileya.CS1 maint: wiele nazwisk: lista autorów ( link )
  • Averill M. Prawo; W. Davida Keltona (2000). Modelowanie i analiza symulacyjna – wydanie trzecie . McGraw-Hill.
  • Bernarda P. Zeiglera; Herberta Praehofera; Tag Gon Kim (2000). Teoria modelowania i symulacji: Integracja zdarzeń dyskretnych i ciągłych złożonych układów dynamicznych – wydanie drugie . Prasa akademicka.
  • Jerry Banks; Johna Carsona; Barry'ego Nelsona; David Nicol (2005). Symulacja systemu zdarzeń dyskretnych – wydanie czwarte . Osoba.
  • James J. Nutaro (2010). Budowanie oprogramowania do symulacji: teoria i algorytmy, z aplikacjami w C++ . Wileya.