Reviewed by
Juan de Lara Jaramillo
ETS Informática,
Universidad Autónoma de Madrid, Spain.
This book covers the whole life cycle of the discrete-event simulation process: modelling (process and event centred), coding (in SIMSCRIPT II.5 and Arena/SIMAN), preparing the input, experimenting and interpreting and analysing the output. Other important topics for simulation such as sampling from diverse probability distributions and pseudo-random number generation are also covered.
The book is 537 pages long and is divided in ten chapters, in which the author gives an excellent and complete introduction to all aspects related to discrete-event computer simulation. Although the author uses a clear language and does not pre-suppose any discrete-event simulation knowledge from the reader, some background in probability theory, statistics and calculus is necessary to feel comfortable with the book.
This work may be of interest for the JASSS readers, as it provides a strong background in the theory behind discrete-event modelling and simulation. For example, the lessons learned in the book are immediately applicable to agent-based simulation of the kind so common in the articles of this journal. Moreover, although theoretical, the book is full of examples and in most of the chapters the author provides a considerable number of exercises. Some of these are followed throughout the book, augmenting them at each stage with questions specific to the current chapter. This makes the book appropriate for a course on computer simulation at the graduate or undergraduate level. A more detailed explanation of each chapter's contents follows.
A
Detailed View of the BookChapter one (Simulation in Perspective) gives an overview of the basic concepts in discrete-event simulation (buffers, resources, scheduling, open and closed-loop queuing systems, etc.) using different examples. The chapter also presents the basic elements that can be analysed in the simulation output (utilisation, waiting time, queue length) and the methods by which they can be analysed (means and exceedance probabilities). Several examples are presented to illustrate these concepts. Later, the author gives a rationale for using discrete-event simulation and presents the two main paradigms to model discrete-event systems: the event scheduling and the process-interaction approach. (These are described in more detail later.) To conclude the chapter the author gives an overview of the typical characteristics of discrete-event simulation languages, including brief references to object-oriented simulation languages, web-based discrete-event simulation and visual modelling techniques.
Chapter two (Modeling Concepts) begins by presenting the typical steps in a simulation process and introducing some basic vocabulary used throughout the book. This is followed by a discussion about how to model advancing time between events. For the purposes of the simulation, the state of the system remains constant between events, so one is not interested in taking into account this inactive time. Most simulation languages use a next-event approach, which stipulates that when an event has been processed, the simulation time is incremented to the time of the next event and that event is then executed.
The chapter follows by describing in detail the two main approaches to building discrete-event models. The activity scanning approach is also mentioned but, although this view may be simpler conceptually, it is generally more inefficient than the other two and is not further examined in the book. Both the event-scheduling and the process-interaction approach are equivalent, that is, they lead to the same outputs for identical inputs:
Both approaches are illustrated using the example of a airline telephone reservation system and the author introduces a diagrammatic notation to represent the actions to be performed when each type of event happen in the event-scheduling approach and to specify the corresponding processes in the process-interaction approach. The chapter ends with another example of the modelling of a telecommunications network and with some exercises for the reader.
Chapter three (Data Collection and Averages) shows how to use the data generated by the simulation to evaluate the performance of the system under examination. Some of the performance indicators to study are the throughput, queue length, server utilisation, waiting time and system loss rate. As stated before, we can also study means and exceedance probabilities (to investigate extreme behaviour) of these indicators. As simulation time is finite, these indicators are just approximations of the true unknown long-run averages. This chapter also gives an overview of the statistical issues that arise when trying to assess how well the finite sample averages produced by a simulation approximate the long-term averages. These include the choice of the initial state of the system, a warm-up interval (time elapsed before data collection begins, to reduce the influence of the initial state) and the simulation run length. As the run length increases, the approximation error in sample averages diminishes and tends to converge to the values of the true, long run averages. The chapter also discusses the two basic ways to finish a discrete-event simulation: when the simulation reaches a certain time, and when a certain number of actions (such as job completions) have taken place.
Chapter four (Programming and Execution), covers the coding of the simulation model with a programming language and executing the simulation. The chapter illustrates this step using both the SIMSCRIPT II.5 and the ARENA/SIMAN languages. Both of these languages implement the process-interaction paradigm, but SIMSCRIPT II.5 also allows programming via the event-scheduling approach. The capabilities of both languages are illustrated by implementing the airline reservation system already described. In these examples, some hints for getting better simulation results are given. Firstly, maintain a different pseudo-random number stream for each source of stochastic variation. (This will allow more control within a single run and across multiple runs of the simulation and is the basis of the common pseudo-random number streams technique to reduce variance.) Secondly, record the seeds (first and last) for each stream, which makes it easy to reproduce the simulation results.
Chapter five (Search, Space and Time) analyses the computing time and memory size needs of discrete-event simulation programs. Space management and list processing consume a large proportion of the time spent executing a discrete-event simulation program. The chapter gives an overview of the way different simulation systems manage memory and look for events in data structures. Different data structures are commonly used by simulation systems to keep the future event notices, among them single lists, multiple lists (one for each type of event, used by SIMSCRIPT II.5), heaps (used by SIMAN) and the Henriksen's data structure (used by GPSS/H and SLAM). In general, binary Heaps and the Henriksen algorithm give the better results.
Chapter six (Output Analysis) introduces the notions of sampling and systematic errors in simulation outputs. The first one is due to random input, the latter arises from the dependence of the outputs on the initial conditions of the system. The chapter discusses how to assess both of them:
Chapter seven (Making Sense of Output and Increasing Efficiency) describes analysis techniques to facilitate informed decision making based on comparison of the simulation results in different operating scenarios. These may differ in the values assigned to input parameters and in the system-operating rules. The author introduces techniques for credibility analysis to compare the outputs of the different experiments and the simultaneity of multiple confidence statements made about these results. These techniques are illustrated with the simulation of the organisation of photocopying machines in a library, introduced in chapter one. The chapter also shows two methods to reduce the variance in the difference of sample averages from simulations with different input scenarios. The methods are based on using common pseudo-random numbers and choosing optimal sample-path lengths.
Chapter eight (Sampling from Probability Distributions) shows algorithms to sample from many particular probability distributions. The chapter focuses on the better algorithms in computing time, which guarantee a fixed mean computing time or a uniform upper bound. All these methods produce the samples by transforming a sequence of pseudo-random numbers drawn from the uniform distribution in [0,1). The explanations of how to obtain a source of pseudo-random numbers are presented in chapter nine.
In particular this chapter covers the Inverse-Transform, Cutpoint, Composition, Alias, Acceptance-Rejection, Ratio-of-Uniforms andExact-Approximation methods. All of them apply to both continuous and discrete distributions. The chapter also gives algorithms for selected, commonly encountered distributions, such as the Exponential, Normal, Lognormal, Cauchy, Gamma, Beta, Poisson, Binomial, Hypergeometric, Geometric, Negative Binomial and Multinomial. The chapter ends by proposing some exercises for the reader including some programming exercises.
Chapter nine (Pseudo-random Number Generation) describes the implementation of pseudo-random number generators, as all algorithms in the previous chapter made use of them. These generators produce sequences of non-negative integer numbers (Zi) with an upper bound (Zi<M), and use Ui = Zi/M for approximating sequences from the uniform distribution in [0,1). The chapter explains linear congruential generators where each pseudo-random number is calculated as Zi=AZi-1(mod M)), where a seed Z0 is needed. The chapter discusses how to choose Z0, A and M such that the period of the generator is maximum. It discusses the special case of congruential generators with M=2β. The chapter also assess how random pseudo-random numbers are. This is done by estimating the number of hyperplanes on (0,1)k the k-tuples (Ui, ... , Ui+k-1) generated by the pseudo-random generators form. A small distance between hyperplanes is an indicator of randomness. One chooses the multipliers that maximise the period and minimise the maximal distance between successive hyperplanes. The chapter also presents a method to improve the quality of the generators by combining several multiplicative generators.
Chapter ten ( Preparing the Input ) explains how to assign a sampling distribution to each source of variation in the input and numerical values to the distribution parameters. Fitting inputs to a particular distribution can be performed using a combination of expert knowledge and empirical data. If this data record is long enough, it can be an adequate basis for sampling otherwise an appropriate theoretical distribution to fit the input data must be found and its parameters must be assigned a value. The maximum likelihood method provides a way to estimate these parameters. The chapter also discusses the case when input data is dependent. The author illustrates these concepts with the library photocopying and waste generation examples both presented in chapter one.
How Does This Book Compare to Others?There are lots of discrete-event simulation books. Inevitably, each one of them stresses different aspects of the modelling and simulation process. The present book for example, dedicates a complete chapter to space and future event set management which is not common in this kind of book and where much smaller sections are usually assigned (Banks et al. 1996, Law and Kelton 1991). Sampling from probability distributions and pseudo-random number generation are also extensively covered in chapters eight and nine, where algorithms in pseudo-code for all the methods are explained.
In the very short list of objections, and of course subject to my personal taste, I missed additional material in the sections dealing with the modelling phase and could have accepted less in the section dealing with the coding phase. Although the author presented a graphical modelling notation for both the process-interaction and the event-scheduling approaches, it might have been interesting to show examples expressed in the form of GPSS block diagrams for the process-interaction approach or as event-graphs in the event-scheduling approach (Schruben 1983). The reason is that the visual nature of these kinds of diagrams makes it very easy to understand the models and help the simulator in "thinking" in event-scheduling or process-interaction terms, abstracting the key elements of the model.
In chapter four I also missed examples expressed in some Object-Oriented simulation language such as MODSIM III. One must not forget that the first Object Oriented Programming was carried out in SIMULA, a discrete-event simulation language. On the positive side, I was pleased not to find the examples in this chapter coded in a general programming language such as Fortran or C, since to my mind these languages do not contribute much to an understanding of the discrete-event or process-interaction approaches. I also regret the absence (possibly in chapter two) of a more detailed discussion and comparison between activity scanning (and its modification the three-phase approach which was not mentioned in the book) with the other two world views: the event-scheduling and the process-interaction approaches.
ConclusionIn brief, this book is highly recommendable either to be used as a text for a course on discrete-event simulation or as a reference for discrete-event simulation practitioners, as it provides a balance between theoretical and practical issues, including coding in different simulation languages and plentiful examples which are well developed throughout the book.
ReferencesBANKS J., J. S. Carson and B. L. Nelson 1996. Discrete-Event System Simulation, second edition. Prentice-Hall, Englewood Cliffs, NJ.
GORDON G. 1996. System Simulation, second edition. Prentice-Hall, Englewood Cliffs, NJ.
LAW A. and W. D. Kelton 1991. Simulation Modeling and Analysis, second edition. McGraw-Hill, New York, NY.
SCHRUBEN L. W. 1983. Simulation modeling with event graphs. Communications of the ACM, 26:957-963.
Return
to Contents of this issue
© Copyright Journal of Artificial Societies and Social Simulation, 2002