Discrete Event Simulation - PoliTO
Discrete Event Simulation Tecniche di Programmazione – A.A. 2019/2020
Strategy Decision makers need to evaluate beforehand the impact of a strategic or tactical move But some process are just “too complex” Mathematical models is too abstract Building real systems with multiple configurations is too expensive Simulation is a good compromise 2 Tecniche di programmazione A.A. 2019/2020
Simulation Simulation is the process of designing a model of a real system and conducting experiments with this model for the purpose either of understanding the behavior of the system or of evaluating various strategies (within the limits imposed by a criterion or set of criteria) for the operation of a system – Shannon 3 Tecniche di programmazione A.A. 2019/2020
What-if analysis A data-intensive simulation whose goal is to inspect the behavior of a complex system under some given hypotheses (called “scenarios”) What-if analysis Forecasting scenario 4 results Tecniche di programmazione A.A. 2019/2020
Disadvantages Simulation can be expensive and time consuming Each model is unique Managers must choose solutions they want to try in scenarios Overfitting vs. non-repeatability 5 Tecniche di programmazione A.A. 2019/2020
Simulation tools Spreadsheets Excel Calc Numbers Ad-hoc 6 Applix TM1 Powersim QlikView SAP BPS SAS Forecast S. Tecniche di programmazione A.A. 2019/2020
Simulation tools Write your own simulator! 7 from scratch in Java Tecniche di programmazione A.A. 2019/2020
Taxonomy Deterministic or Stochastic Does the model contain stochastic components? Static or Dynamic Is time a significant variable? Continuous or Discrete 8 Does the system state evolve continuously or only at discrete points in time? Tecniche di programmazione A.A. 2019/2020
Discrete Event Simulation (DES) Discrete event simulation is dynamic and discrete It can be either deterministic or stochastic Changes in state of the model occur at discrete points in time The model maintains a list of events (“event list”) 9 At each step, the scheduled event with the lowest time gets processed (i.e., the event list is a priority queue) The event is processed, new events are scheduled Tecniche di programmazione A.A. 2019/2020
Discrete Event Simulation (DES) Event list new events next event Simulation core 10 Tecniche di programmazione A.A. 2019/2020
Discrete Event Simulation (DES) Event list new events next event W World status R Simulation core 11 Tecniche di programmazione A.A. 2019/2020
Discrete Event Simulation (DES) Event list new events next event W World status R Scenario parameters Simulation core Key measures 12 Tecniche di programmazione A.A. 2019/2020
The event list An event contains at least two fields of information time of occurrence (timestamp): time when the event should happen (in the “simulated future”) what the event represents 7 EVL e1 9 time e2 . 20 en event Simulation terminates when the event list is empty Conceptually endless simulations, like weather, terminate at some arbitrary time 13 Tecniche di programmazione A.A. 2019/2020
The event list An event contains at least two fields of information time of occurrence (timestamp): time when the event should May have additional data happen (in the “simulated future”) what the event represents 7 EVL e1 9 time e2 . 20 en event Simulation terminates when the event list is empty Conceptually endless simulations, like weather, terminate at some arbitrary time 14 Tecniche di programmazione A.A. 2019/2020
Simulator architecture E E E Queue World status Simulator Main / Model setParameterXXX(v) void loadQueue(initial events) void run() Double getMeasureXxx() private void processEvent(e) 15 Tecniche di programmazione A.A. 2019/2020 E E
World Status A set of variables / collections / graphs / that represent the current state (the present) of the simulation The simulation makes the world status evolve, through a series of events The world status may influence / constrain how the events are processed The world status includes the measures of interest. 16 Tecniche di programmazione A.A. 2019/2020
General behavior: Simulator setParameterXXX: defines the simulation strategy and parameters, and initializes the World Status loadQueue: defines the initial contents of the simulation queue, at time zero run: executes the simulation loop Can also be in the Simulator constructor extract an event from the queue processEvent(e) getMeasureXXX: allows to access the results of the simulated variables, after the completion of the loop 17 Tecniche di programmazione A.A. 2019/2020
processEvent(e) Analyzes e.getType() Depending on: The simulation parameters (constants) and strategy The type of event The value(s) associated with the event The current world status It performs actions: 18 (Optional) updates the current world status (Optional) generates and inserts new events (in the future) (Optional) updates the measures of interest Tecniche di programmazione A.A. 2019/2020
Handling time Synchronous Events (all/most/some) correspond to the passing of time Asyncronous Easy to generate systematically (all at the beginning, or each one generates the next) When a new day/hour/months ticks, something needs to be done May be intermixed by other events, at arbitrary times 19 Something happens in the simulated world May happen at any time instant The simulated time will «jump» to the nearest interesting event Tecniche di programmazione A.A. 2019/2020
Handling Randomness Deterministic Stochastic All actions are purely deterministic (initial events, event processing) Repeating the simulation, with equal parameters, will yield the same result. Always. 20 Random initial events (times, values, types) Randomness in event processing (eg. in 10% of the cases simulate a fault) Repeating the simulation will yield different measures Simulation should be repeated and the measures should be averaged Tecniche di programmazione A.A. 2019/2020
Example 1 Discrete Event Simulation
Example: Car Sharing We want to simulate a deposit of shared cars. A new client comes every T IN minutes Initially we have NC cars If there are available cars, he lends one care, for a duration of T TRAVEL minutes If there are no cars, he is a dissatisfied client Computer the number of dissatisfied clients, at the end of the day, as a function of NC. T IN 10 minutes T TRAVEL random (1 hour, 2 hours, 3 hours) 22 Tecniche di programmazione A.A. 2019/2020
Simulator data Events Client arrives Client returns car World model 23 Number of total cars Number of available cars Number of clients served Number of dissatisfied clients Tecniche di programmazione A.A. 2019/2020
Variants Remember “who” is the client, at return time Model different kinds of cars (A, B, C). A client wants one kind of car, but he may accept a “better” car (cost for the company) Model different car rental locations 24 A car is taken at location “x” and returned at location “y” Tecniche di programmazione A.A. 2019/2020
Example 2 Discrete Event Simulation
Example: Emergency We simulate the behavior of an Emergency department in an hospital. The department in organized in two sections 26 A single Triage, where patients are received, quickly examined, and assigned a severity code A number NS of doctor studios, that operate in parallel. Each doctor will receive the next patient, act on him, and then release him The severity code gives priority in accessing the doctors. Patients with the same severity, will be called in arrival order. Tecniche di programmazione A.A. 2019/2020
Severity codes WHITE: not urgent, may wait without problems YELLOW: serious but not urgent After YELLOW TIMEOUT, if not served, becomes RED RED: serious and urgent, risking life, must be served as soon as possible After WHITE TIMEOUT, if not served, goes home After RED TIMEOUT, if not served, becomes BLACK BLACK: dead. No need to be served. 27 Tecniche di programmazione A.A. 2019/2020
Timing Phase Required time Example Triage DURATION TRIAGE 5 minutes Handling a White patient DURATION WHITE 10 minutes Handling a Yellow patient DURATION YELLOW 15 minutes Handling a Red patient DURATION RED 30 minutes Handling a Black patient N/A not needed 28 Tecniche di programmazione A.A. 2019/2020
Patients workflow STUDIO 1 TRIAGE WAIT STUDIO 2 STUDIO 3 29 Tecniche di programmazione A.A. 2019/2020 OUT
World Model Collection of patients For each patient: 30 Patient status Tecniche di programmazione A.A. 2019/2020
Evolution of patient status WAI TIN G TRIAGE NE W TIMEOUT FREE STUDIO WAI TIN G TIMEOUT WAI TIN G TIMEOUT 31 TRE ATI NG OU T BLA CK Tecniche di programmazione A.A. 2019/2020
Simulation goals Input Parameter: NS Initial events: Output NP patients arriving every T ARRIVAL minutes with a round-robin severity (white/yellow/red/white/ ) Number of patients dismissed Number of patients that abandoned Number of patients dead Simulate from 8:00 to 20:00 32 Tecniche di programmazione A.A. 2019/2020
Randomizing Input arrival times every T ARRIVAL random% Input severity probabilities (PROB WHITE, PROB YELLOW, PROB RED) Variable processing time (DURATION TRIAGE, DURATION WHITE, DURATION YELLOW, DURATION RED random%) Etc 33 Tecniche di programmazione A.A. 2019/2020
Licenza d’uso Queste diapositive sono distribuite con licenza Creative Commons “Attribuzione - Non commerciale - Condividi allo stesso modo (CC BY-NC-SA)” Sei libero: Alle seguenti condizioni: di riprodurre, distribuire, comunicare al pubblico, esporre in pubblico, rappresentare, eseguire e recitare quest'opera di modificare quest'opera Attribuzione — Devi attribuire la paternità dell'opera agli autori originali e in modo tale da non suggerire che essi avallino te o il modo in cui tu usi l'opera. Non commerciale — Non puoi usare quest'opera per fini commerciali. Condividi allo stesso modo — Se alteri o trasformi quest'opera, o se la usi per crearne un'altra, puoi distribuire l'opera risultante solo con una licenza identica o equivalente a questa. http://creativecommons.org/licenses/by-nc-sa/3.0/ 34 Tecniche di programmazione A.A. 2019/2020
Discrete Event Simulation (DES) 9 Tecniche di programmazione A.A. 2019/2020 Discrete event simulation is dynamic and discrete It can be either deterministic or stochastic Changes in state of the model occur at discrete points in time The model maintains a list of events ("event list") At each step, the scheduled event with the lowest time gets
Event 406 - Windows Server 2019 58 Event 410 58 Event 411 59 Event 412 60 Event 413 60 Event 418 60 Event 420 61 Event 424 61 Event 431 61 Event 512 62 Event 513 62 Event 515 63 Event 516 63 Event 1102 64 Event 1200 64 Event 1201 64 Event 1202 64 Event 1203 64 Event 1204 64
2. Benefits of Discrete Event Simulation Discrete Event Simulation has evolved as a powerful decision making tool after the appearance of fast and inexpensive computing capacity. (Upadhyay et al., 2015) Discrete event simulation enables the study of systems which are discrete, dynamic and stoc
7 www.teknikindustri.org 2009 Discrete-change state variable. 2. Discrete Event Simulation 8 www.teknikindustri.org 2009. Kejadian (Event) . pada langkah i, untuk i 0 sampai jumlah discrete event Asumsikan simulasi mulai pada saat nol, t 0 16 www.teknikindustri.org 2009 0 t1: nilai simulation clock saat discrete eventpertama dalam
2.1 Discrete-Event Simulation To discuss the area of DES, we rst need to introduce the concept of a discrete-event system. According to Cassandras et al. [4], two characteristic properties describing a given system as a discrete-event system are; 1.The state space is a discrete set. 2.The state transition mechanisms are event-driven.
A discrete-event simulation is the modeling over time of a system all of whose state changes occur at discrete points in time those points when an event occurs. A discrete-event simulation (hereafter called a simulation) proceeds by producing a sequence of system snapshots (or system images) which represent t
Network Security, WS 2008/09, Chapter 9IN2045 – Discrete Event Simulation, WS 2011/2012 10 Discrete Event Simulation A Discrete Event Simulation (DES) is the reproduction of the behaviour of a system over time by means of a model where the state variables of the models change
simulation system state via direct computing, yet without loss of simulation accuracy. As the traditional discrete event network simulator (such as NS[4]) obtains all the changes of simulation system state via discrete events, this method can cut down the number of discrete events and reduce the simulation running time compared with the
Jazz Piano, ABRSM Publishing: Level 1, Level 2, Level 3, Level 4, Level 5 Jazz Piano from Scratch, Dr. Charles Beale Shelton Berg: Jazz Improv: Goal-Note (Book/Cd), Shelton Berg Bill Boyd: Jazz Keyboard Basics, Bill Boyd An Introduction To Jazz Chord Voicing For Keyboard, Bill Boyd Intermediate Jazz Chord Voicing For Keyboard, Bill Boyd Exploring Traditional Scales And Chords For Jazz Keyboard .
