1 00:00:07,500 --> 00:00:12,200 Hi, my name is Alexander Verbraeck, full professor of systems and simulation at 2 00:00:12,230 --> 00:00:14,119 Delft University of Technology. 3 00:00:14,119 --> 00:00:18,340 Today I'm going to cover the topic of discrete event simulation with you. 4 00:00:18,340 --> 00:00:21,860 Topics I'm going to focus on are: What is a discrete event simulation? 5 00:00:21,860 --> 00:00:23,480 Where does it fit historically? 6 00:00:23,480 --> 00:00:27,300 How does it differ from other types of simulation, such as agent based simulation 7 00:00:27,300 --> 00:00:29,390 and continuous simulation? 8 00:00:29,390 --> 00:00:34,200 What are the steps in a simulation study and what are the important aspects of simulation 9 00:00:34,230 --> 00:00:37,280 for infrastructure studies? 10 00:00:37,280 --> 00:00:42,719 According to Shannon, 1975, simulation is a process of designing a model 11 00:00:42,719 --> 00:00:47,789 of a concrete system and conducting experiments with this model in order to understand the 12 00:00:47,789 --> 00:00:53,800 behavior of the system and/or to evaluate various strategies for the operation of the system. 13 00:00:53,839 --> 00:00:57,280 In this definition, we see a couple of very important words. 14 00:00:57,280 --> 00:01:01,409 One is: it is a process to conduct experiments. 15 00:01:01,409 --> 00:01:05,950 Experimentation is key to simulation and especially to discrete event simulation. 16 00:01:05,950 --> 00:01:12,039 Secondly, we need to use the simulation to understand the behavior of a system or to 17 00:01:12,039 --> 00:01:13,329 evaluate strategies. 18 00:01:13,329 --> 00:01:15,539 That means also we can use it for design. 19 00:01:15,539 --> 00:01:19,829 In that sense, simulation is a 'what if study'. 20 00:01:19,829 --> 00:01:25,900 We change parameters to the simulation model and look at the effect on the output of the simulation. 21 00:01:26,049 --> 00:01:28,900 Why do we use discrete event simulation? 22 00:01:28,950 --> 00:01:32,950 One is that it is an instrument to evaluate alternative systems designs, 23 00:01:32,950 --> 00:01:36,280 to compare alternative solutions, to predict system performance. 24 00:01:36,280 --> 00:01:41,060 Often, it is used for infrastructure problems and logistical problems, 25 00:01:41,060 --> 00:01:43,530 especially when we have limited capacity resources. 26 00:01:43,530 --> 00:01:48,469 For instance, in energy networks, transportation systems and logistics systems. 27 00:01:48,469 --> 00:01:51,479 Sometimes, we also use it for more advanced simulation, 28 00:01:51,479 --> 00:01:56,179 such as sensitivity analysis or optimization. 29 00:01:56,179 --> 00:02:00,249 If we look historically, discrete event simulation started already 30 00:02:00,249 --> 00:02:03,189 pretty early as one of the modelling techniques. 31 00:02:03,189 --> 00:02:06,810 Round the 1950-ties, the first discrete event simulation models 32 00:02:06,810 --> 00:02:07,649 were built. 33 00:02:07,649 --> 00:02:11,270 In that particular time, especially for military simulations, 34 00:02:11,270 --> 00:02:14,720 transportation simulations and energy simulations. 35 00:02:14,720 --> 00:02:21,720 Later, continuous simulations and agent based simulations joint the set of simulation studies 36 00:02:21,800 --> 00:02:25,440 that can be executed for infrastructures. 37 00:02:25,440 --> 00:02:30,560 There are a couple of similarities and differences between discrete event simulation and continuous 38 00:02:30,560 --> 00:02:31,660 simulation. 39 00:02:31,660 --> 00:02:39,100 One is that we very much look at the state of the system over time but in this particular 40 00:02:39,100 --> 00:02:41,960 case we do it at discrete moments. 41 00:02:41,960 --> 00:02:45,950 It's not that the system's state changes continuously over time, 42 00:02:45,950 --> 00:02:49,770 but more that the system state changes at discrete events, 43 00:02:49,770 --> 00:02:53,200 concurring at an instant. 44 00:02:53,200 --> 00:02:57,440 In continuous models states, and the state variables are a continuous function 45 00:02:57,440 --> 00:02:58,690 of time. 46 00:02:58,690 --> 00:03:05,570 This means, that and the state variables have a value for each point in time and the variables 47 00:03:05,570 --> 00:03:08,490 change at every instant of time. 48 00:03:08,490 --> 00:03:14,270 This is in sharp contrast with discrete-event models where the state is a piecewise constant 49 00:03:14,270 --> 00:03:15,760 function over time. 50 00:03:15,760 --> 00:03:19,150 So not continuous, but constant. 51 00:03:19,150 --> 00:03:23,450 Only at discrete instances, the function changes its value. 52 00:03:23,450 --> 00:03:28,700 And we can see that, for instance, at the instance of time 17, time 27, 53 00:03:28,700 --> 00:03:31,470 time 70 and around time 95. 54 00:03:31,470 --> 00:03:36,820 The values change exactly at that point in time and don't change in between. 55 00:03:36,820 --> 00:03:43,730 It also makes the discrete event simulation models pretty fast because the state only 56 00:03:43,730 --> 00:03:46,510 has to be changed and these point in time. 57 00:03:46,510 --> 00:03:49,730 This makes it very useful for cueing systems, for resource systems, 58 00:03:49,730 --> 00:03:53,730 for transportation and logistics but also for control systems. 59 00:03:53,730 --> 00:03:57,480 For all these systems we only have to focus on events: 60 00:03:57,480 --> 00:04:02,890 starts and ends of processes rather than the evolution of processes themselves. 61 00:04:02,890 --> 00:04:05,560 So how do we build these types of simulations? 62 00:04:05,560 --> 00:04:09,970 The simulations are very much built based on models. 63 00:04:09,970 --> 00:04:14,810 Models for the current situation and models for potential future situations. 64 00:04:14,810 --> 00:04:20,430 The models have to be identified based on states and information we can get from the 65 00:04:20,430 --> 00:04:22,970 infrastructure system itself. 66 00:04:22,970 --> 00:04:25,950 We build a model, diagnose the problem, 67 00:04:25,950 --> 00:04:31,150 test whether the model is corresponding to the real system (validation), 68 00:04:31,150 --> 00:04:35,010 build alternative models to evaluate them for solutions. 69 00:04:35,010 --> 00:04:42,000 And hopefully we find solutions we can implement in a new situation in the actual system. 70 00:04:42,000 --> 00:04:49,000 The steps we take for this are called conceptualization, specification, verification and validation, 71 00:04:49,000 --> 00:04:52,270 experimentation and analysis. 72 00:04:52,270 --> 00:04:56,440 These steps are often carried out in a more iterative manner. 73 00:04:56,440 --> 00:05:01,490 That means that we go back to earlier steps that we have not yet carried out, 74 00:05:01,490 --> 00:05:06,240 or to earlier steps that we have already carried out. 75 00:05:06,240 --> 00:05:11,030 Often, we use a traditional water full model for this. 76 00:05:11,030 --> 00:05:14,070 This is also will be seen many textbooks. 77 00:05:14,070 --> 00:05:15,889 First conceptualization, then specifications, 78 00:05:15,889 --> 00:05:19,660 then data collection and verification, etc. 79 00:05:19,660 --> 00:05:23,760 More and more, iterative modelling becomes normal in discrete 80 00:05:23,760 --> 00:05:25,280 event simulation. 81 00:05:25,280 --> 00:05:29,180 This means that we build a model, we go to specification, 82 00:05:29,180 --> 00:05:32,660 we go to data collection, we find in the data collection that maybe 83 00:05:32,660 --> 00:05:38,300 we need to make some changes and then we go back to one of the earlier phases to adapt the model. 84 00:05:38,590 --> 00:05:46,500 However, an incremental model is lately seen as the best way to build discrete-event simulation models. 85 00:05:46,990 --> 00:05:48,760 It means that we start small. 86 00:05:48,760 --> 00:05:55,120 We start with a tiny model that models the core of the problem or of the infrastructure 87 00:05:55,120 --> 00:05:56,680 we are looking at. 88 00:05:56,680 --> 00:05:59,950 Step by step, we extend to model in a number of steps where 89 00:05:59,950 --> 00:06:03,740 we go through all the phases of the model cycle again. 90 00:06:03,740 --> 00:06:08,780 It means that we analyze, diagnose, conceptualize specified data collection etc. 91 00:06:08,780 --> 00:06:11,650 a couple of times after another. 92 00:06:11,650 --> 00:06:17,610 Starting small and extending it step by step to a bigger model. Especially for larger infrastructure 93 00:06:17,610 --> 00:06:23,090 models this is an excellent way to do it because we don't have to make the model all at once 94 00:06:23,090 --> 00:06:27,010 leading to all kinds of bug finding and mistakes. 95 00:06:27,010 --> 00:06:29,030 So what are these different phases? 96 00:06:29,030 --> 00:06:30,960 Let's start with the conceptualization. 97 00:06:30,960 --> 00:06:34,360 Conceptualization, for discrete event simulation modeling, 98 00:06:34,360 --> 00:06:38,169 is especially aimed at demarcation of the system. 99 00:06:38,169 --> 00:06:43,950 It means that we find the system boundaries and we determine what goes into the system, 100 00:06:43,950 --> 00:06:49,520 when it goes into the system and what belongs to the system and what belongs to the environment? 101 00:06:49,520 --> 00:06:55,240 We also establish the components, the objects the entities that are in the model 102 00:06:55,240 --> 00:06:57,630 and the processes that we see in the model. 103 00:06:57,630 --> 00:07:02,010 Sometimes, we also look at a time based aspects. 104 00:07:02,010 --> 00:07:08,650 The conceptualization is often carried out in some kind of diagramming technique that 105 00:07:08,650 --> 00:07:11,330 makes it clear what the models look like. 106 00:07:11,330 --> 00:07:15,040 This is, for example, a model of parts of the infrastructure of 107 00:07:15,040 --> 00:07:22,040 a large airport and with this we can look how we built up the model from smaller pieces. 108 00:07:22,070 --> 00:07:25,960 We can also look at the flow of the model, for instance in a process model, 109 00:07:25,960 --> 00:07:28,160 such as a flow diagram. 110 00:07:28,160 --> 00:07:34,460 In this case aimed at queuing theory and inventory theory. 111 00:07:34,460 --> 00:07:37,590 The specification, the next step in the model phase, 112 00:07:37,590 --> 00:07:43,930 is aimed at leading to a working model that one can experiment with. 113 00:07:43,930 --> 00:07:49,479 The first step is reduction of the model, also seen as one of the most difficult steps. 114 00:07:49,479 --> 00:07:53,740 Reduction means that we leave out everything that's not needed to complete the model and 115 00:07:53,740 --> 00:07:56,150 to run a successful simulation study. 116 00:07:56,150 --> 00:08:01,550 We specify the model, we gather data and we build the model. 117 00:08:01,550 --> 00:08:05,680 An example how to build a model is shown here in one of the simulation modelling packages 118 00:08:05,680 --> 00:08:11,520 called SIMIO that's available and often used in university surroundings. 119 00:08:11,520 --> 00:08:15,250 We built a model based on a number of standard building blocks that are available on the 120 00:08:15,250 --> 00:08:19,430 left hand side of the screen in a so-called library. 121 00:08:19,430 --> 00:08:23,930 With these building blocks, we very quickly built up the model connected 122 00:08:23,930 --> 00:08:26,110 by, in this case path, 123 00:08:26,110 --> 00:08:31,490 and we have a generation of entities, a server that serve the entities and a sink 124 00:08:31,490 --> 00:08:33,579 in which the entities again disappear. 125 00:08:33,579 --> 00:08:38,249 The model has both two dimensional and three dimensional representations and one can see 126 00:08:38,249 --> 00:08:42,959 that in one minute one builds a queuing model that would normally take, 127 00:08:42,959 --> 00:08:46,829 if you would have to program it, a much, much longer time. 128 00:08:46,829 --> 00:08:50,600 One of the interesting things is also that the model of course generates a lot of output. 129 00:08:50,600 --> 00:08:53,800 To give an example, you can see from this very small model that 130 00:08:53,800 --> 00:08:59,480 quite a lot of output is generated for later analysis and it's this analysis that so important 131 00:08:59,480 --> 00:09:06,200 also for discrete event simulation because the models are aimed at generating this particular output. 132 00:09:08,600 --> 00:09:13,119 What kind of data do we need to fill these kind of models? 133 00:09:13,119 --> 00:09:19,529 Especially generators and sinks at the sources and ends of the model are very important. 134 00:09:19,529 --> 00:09:23,579 Means that we have to know when entities enter the model and when an entities leave the model. 135 00:09:23,579 --> 00:09:27,439 We also have to know how long processes take and when resources are available. 136 00:09:27,439 --> 00:09:30,189 We can gather it in many, many different ways. 137 00:09:30,189 --> 00:09:37,189 For instance, expert opinions, measurements, or historical sources like databases. 138 00:09:38,740 --> 00:09:43,249 One of the steps that's extremely key in discrete event simulation modelling is verification 139 00:09:43,249 --> 00:09:45,009 and validation. 140 00:09:45,009 --> 00:09:49,459 We need to know that our model is a valid representation of reality and there are different 141 00:09:49,459 --> 00:09:52,410 ways to test that. 142 00:09:52,410 --> 00:09:58,410 Verification looks at the translation of our conceptual model into a simulation model. 143 00:09:58,410 --> 00:10:03,589 Validation looks at the relationship between our simulation model and reality. 144 00:10:03,589 --> 00:10:06,209 There are different ways to validate models. 145 00:10:06,209 --> 00:10:11,439 One is to test hypotheses using statistics, where we compare output from our simulation 146 00:10:11,439 --> 00:10:15,879 model and output from reality under similar circumstances. 147 00:10:15,879 --> 00:10:19,509 But we can also look at expert opinions about our simulation, 148 00:10:19,509 --> 00:10:24,800 for instance by having experts look at our animations. 149 00:10:24,800 --> 00:10:30,470 There are many relationships and many types of validation that we can carry out. 150 00:10:30,470 --> 00:10:36,019 And in principle every step that we take in the simulation modelling study has to be followed 151 00:10:36,019 --> 00:10:40,869 by a validation or a verification step where we test the correctness and the accuracy of 152 00:10:40,869 --> 00:10:45,699 the model that we just created and to look whether the model is still really fit for 153 00:10:45,699 --> 00:10:50,459 purpose for what we try to accomplish with the model. 154 00:10:50,459 --> 00:10:54,350 When the model is considered to be valid and verified, 155 00:10:54,350 --> 00:10:56,249 we want to look at experiments of course. 156 00:10:56,249 --> 00:10:59,970 Because, if we look back at the definition of Shannon, 157 00:10:59,970 --> 00:11:02,249 the model is to be experimented with. 158 00:11:02,249 --> 00:11:07,259 We want to look at the behavior of the model as a representation of our system under all 159 00:11:07,259 --> 00:11:09,649 kinds of different circumstances. 160 00:11:09,649 --> 00:11:14,660 But, the question of course is: how do we exactly do that? 161 00:11:14,660 --> 00:11:21,309 Do we really need to test the system only with one particular run or would it be statistically 162 00:11:21,309 --> 00:11:23,800 more valid if we use multiple runs? 163 00:11:23,800 --> 00:11:29,360 Would it be better to test model for longer time or a shorter time? 164 00:11:29,360 --> 00:11:32,920 This is exactly what experiment specification is about. 165 00:11:32,920 --> 00:11:37,459 We determine the run controlled conditions under which the model is experimented with 166 00:11:37,459 --> 00:11:42,579 and thereby we can establish a statistical validity of our model. 167 00:11:42,579 --> 00:11:47,619 When we have done a number of experiments, of course we want to compare alternatives. 168 00:11:47,619 --> 00:11:52,829 We want to do statistical analyses and we might look at bottlenecks or do a sensitivity 169 00:11:52,829 --> 00:11:59,079 analysis on the stability of the results for some of the input variables. 170 00:11:59,079 --> 00:12:05,160 This is what we do in analysis and diagnosis, where we use the model to calculate results 171 00:12:05,160 --> 00:12:08,300 that are statistically valid and from which we can draw conclusions 172 00:12:08,300 --> 00:12:10,920 about our infrastructure models. 173 00:12:10,920 --> 00:12:16,660 An example is to export model results to, for instance SPSS, 174 00:12:16,660 --> 00:12:21,739 or one of the statistical packages and analyze it in detail. 175 00:12:21,739 --> 00:12:27,660 With this we can test hypotheses about the differences or the similarities between different 176 00:12:27,660 --> 00:12:28,900 model runs. 177 00:12:28,900 --> 00:12:35,679 If we look at infrastructure simulation, discrete event simulation is very much suited 178 00:12:35,699 --> 00:12:39,769 because we can represent model components one to one and, 179 00:12:39,769 --> 00:12:43,939 in the form of entities or building blocks in our simulation model. 180 00:12:43,939 --> 00:12:48,670 We use hierarchy very often to build a model more bottom up. 181 00:12:48,670 --> 00:12:54,339 That means that all kinds of components, as we have seen in the example from SIMIO, 182 00:12:54,339 --> 00:12:59,230 can be dragged into our model - using drag and drop interface- from which we can build 183 00:12:59,230 --> 00:13:04,369 more complex model or even build more complex components that can then again be used in 184 00:13:04,369 --> 00:13:06,189 the model again. 185 00:13:06,189 --> 00:13:11,040 We use libraries of components, sometimes specifically aimed at a particular 186 00:13:11,040 --> 00:13:14,170 type of infrastructure. 187 00:13:14,170 --> 00:13:18,879 Infrastructure simulations are very often aimed at capacity usage. 188 00:13:18,879 --> 00:13:22,509 How much capacities there are available, for instance on the transportation network 189 00:13:22,509 --> 00:13:25,869 and energy network, and how much do we use? 190 00:13:25,869 --> 00:13:29,970 The types of simulations that have been built for infrastructure simulation and for discrete 191 00:13:29,970 --> 00:13:34,660 event simulation show lots of similarities and therefore discrete-event simulation is 192 00:13:34,660 --> 00:13:38,329 used very often for infrastructure testing. 193 00:13:38,329 --> 00:13:43,809 The animation can help in building, debugging and presenting the model. 194 00:13:43,809 --> 00:13:45,220 Conclusions. 195 00:13:45,220 --> 00:13:50,629 Discrete-event simulation very much focuses on events. 196 00:13:50,629 --> 00:13:54,749 Events are times when the stage changes. 197 00:13:54,749 --> 00:13:59,540 The state is continuous between those different events. 198 00:13:59,540 --> 00:14:02,319 And this leads to very fast execution of the models. 199 00:14:02,319 --> 00:14:07,459 That means that we can build quite complex models that still have very acceptable runtimes. 200 00:14:07,459 --> 00:14:11,119 And that means that we can model our infrastructure in quite some detail. 201 00:14:11,119 --> 00:14:16,700 We have also looked at the model cycle, where we focused on incremental building and building blocks. 202 00:14:16,799 --> 00:14:20,689 But we also will see later, in some of the examples for discrete event 203 00:14:20,689 --> 00:14:26,839 simulation in one of the next presentations, is that we focus very much on hierarchy, 204 00:14:26,839 --> 00:14:31,610 where we can build up models in a hierarchical fashion and that means that the modeler always 205 00:14:31,610 --> 00:14:35,559 keeps overview of the model itself. 206 00:14:35,559 --> 00:14:37,549 Modeling is quite data intensive. 207 00:14:37,549 --> 00:14:42,730 This means that we have to very carefully look at the boundaries of our system and conceptualization 208 00:14:42,730 --> 00:14:48,079 and the reduction our system in the specification to make sure that we have the right input 209 00:14:48,079 --> 00:14:51,509 for the model and we can collect the data. 210 00:14:51,509 --> 00:14:53,329 Thank you very much for your attention.