Discrete Event (time) Simulation
The process of designing a model of a real system to understand behavior or evaluate strategies. Types of simulation include static vs. dynamic, deterministic vs. stochastic, and discrete vs. continuous models. Understanding these basics is crucial for implementing a successful discrete event simulation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Discrete Event (time) Simulation 2011.10.26 Kenneth
What is a simulation? What is a 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. -Robert E Shannon 1975 Simulation is the process of designing a dynamic model of an actual dynamic system 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. -Ricki G Ingalls 2002 2
What types of simulation are there? What types of simulation are there? 3
Simulation Types 1. Static or dynamic models 2. Stochastic or deterministic models 3. Discrete or continuous models 4
Static vs. Dynamic Dynamic State variables change over time (System Dynamics, Discrete Event) Static Snapshot at a single point in time (optimization models, etc.) 5
Deterministic vs. Stochastic Deterministic model The behavior is entire predictable. The system is perfectly understood, then it is possible to predict precisely what will happen. Stochastic model The behavior cannot be entirely predicted. 6
Discrete vs. Continuous Discrete model The state variables change only at a countable number of points in time. These points in time are the ones at which the event occurs/change in state. Continuous The state variables change in a continuous way, and not abruptly from one state to another (infinite number of states). 7
Discrete Event Simulation Dynamic Stochastic Discrete 8
How to Implement a Discrete Event Simulation? Consider an example: Airport System A certain airport contains a single runway on which arriving aircrafts must land. Once an aircraft is cleared to land, it will use the runway, during which time no other aircraft can be cleared to land. Once the aircraft has landed, the runway is available for use by other aircraft. The landed aircraft remains on the ground for a certain period of time before departing. 9
An Example: Airport System Single Server Queue Server Queue Customers Ground Customer (aircraft) Entities utilizing the system/resources Server (runway) Resource that is serially reused; serves one customer at a time Queue 10 Buffer holding aircraft waiting to land
An Example: Airport System Single Server Queue Server Queue Customers Ground Performance metrics Average waiting time: average time that an aircraft must wait when arriving at an airport before they are allowed to land. Maximum number of aircraft on the ground: helps to determine the required space of the parking area. 11
Simulation Development Events Events Stochastic model and system attributes System States Relationship among events Time handling Output statistics 12
An Example: Airport System Single Server Queue Server Queue Customers D Sf Ss A Ground Events: an instantaneous occurrence that changes the state of a system Arrival (A) Start Service (Ss) Finish Service (Sf) Departure (D) 13
Stochastic Model and System Attributes Customers Arrival process: schedule of aircraft arrivals Real trace Probability model: distribution of inter-arrival time i.i.d. (Independent and identically distributed ) Uniform, normal, exponential Servers How much service time is needed for each customer? Probability model: i.i.d. and exponential distribution How many servers? 14 Single
Stochastic Model and System Attributes Queue Service discipline - who gets service next? First-in-first-out (FIFO), Last-in-first-out (LIFO), Priority, Weighted-fairness (WFQ), random Preemption? Queue capacity? k or infinite Ground Park time Probability model: i.i.d. and exponential distribution 15
Stochastic Model and System Attributes Uniform Given max and min 0 random() < 1 = min + random() (max - min) Exponential Given rate @p.30 of lec1.ppt Normal Asking Google 16
How to verify the correctness of distribution generator? ANS: you can verity it by using a program, Excel, Matlab, 17
How to verify the correctness of distribution generator via Excel? Inputting or generating sample data Generating pdf Applying Histogram of Data Analysis Data Analysis is in Analysis Toolpack ( ) 18
How to verify the correctness of distribution generator via Excel? Generating Broken-line graph for cdf of xi Generating ground truth of cdf 19
Simulation Development Events Stochastic model and system attributes System States Relationship among events Time handling Output statistics 20
System States System state A collection of variables in any time that describe the system Event An instantaneous occurrence that changes the state of a system State 1 Event Y Event X Event X Event Y State 2 State 3 21
An Example: Airport System Single Server Queue Server Queue Customers D Sf Ss A Ground System States (Q:3 G:2 B:y) Q: # of aircrafts waiting for landing G: # of aircrafts on the ground 22 B: y/n; y if the runway is busy
An Example: Airport System Single Server Queue Server Queue Customers D Sf Ss A Ground Q:3 G:1 B:y D A Q:4 G:2 B:y Q:3 G:2 B:y Q:2 G:3 B:y IF Q>0 Sf Ss Q:3 G:3 B:n 23
Simulation Development Events Stochastic model and system attributes System States Relationship among events Time handling Output statistics 24
Relationships among Events Each Event has a timestamp indicating when it occurs System States Q: # of aircrafts waiting for landing G: # of aircrafts on the ground B: y/n, y if the runway is busy Arrival Event A @ t Start Service Event Ss @ t N B? Y Q+ + B=Y Arrival Event A @ t+ArrivalTime() Finish Service Event Sf @ t+ServiceTime() 25
Relationships among Events Finish Service Event Sf @ t System States Q: # of aircrafts waiting for landing G: # of aircrafts on the ground B: y/n, y if the runway is busy G+ + Start Service Event Ss @ t Y Q > 0? N B=N Q-- Departure Event D @ t+ParkTime() Finish Service Event Sf @ t+ServiceTime() 26
Relationships among Events Departure Event D @ t System States Q: # of aircrafts waiting for landing G: # of aircrafts on the ground B: y/n, y if the runway is busy G-- 27
Simulation Development Events Stochastic model and system attributes System States Relationship among events Time handling Output statistics 28
Time Handling How to progress Simulation time? Time-slices Approach Processing Processing Departure Event D @ 00:59:06 Finish Service Event Sf @ 00:17:49 Processing Processing Processing Processing Finish Service Event Sf @ 01:22:11 Arrival Event A @ 00:48:37 Arrival Event A @ 00:02:19 Simulation time A time-slice=5 min Do Do Do Inefficient Inaccurate t = 00:50Do Nothing Do Do Nothing Do Nothing 29 t = 00:00 t = 00:05 t = 00:10 t = 00:15 t = 00:20 t = 00:25 t = 00:30 t = 00:35 t = 00:40 t = 00:45
Time Handling How to progress Simulation time? Event-driven Approach Processing Processing Departure Event D @ 00:59:06 Finish Service Event Sf @ 00:17:49 Processing Processing Processing Processing Finish Service Event Sf @ 01:22:11 Arrival Event A @ 00:48:37 Arrival Event A @ 00:02:19 Simulation time 30 t = 00:02:19 t = 00:17:49 t = 00:48:37
Simulation Development Events Stochastic model and system attributes System States Relationship among events Time handling Output statistics 31
Output statistics Q G B 0 0 0 N Y 00:02:19 1 1 1 0 N Y 00:59:06 00:48:37 01:22:11 00:17:49 00:48:37 Departure Event D @ 00:59:06 Finish Service Event Sf @ 00:17:49 Finish Service Event Sf @ 01:22:11 Arrival Event A @ 01:12:28 Arrival Event A @ 00:48:37 Arrival Event A @ 00:02:19 Simulation time 32
