作者：Harry Perros
TABLE OF CONTENTS
Chapter 1. Introduction, 1
1.1 The OR approach, 1
1.2 Building a simulation model, 2
1.3 Basic simulation methodology: Examples, 5
1.3.1 The machine interference model, 5
1.3.2 A token-based access scheme, 11
1.3.3 A two-stage manufacturing system, 18
Problems, 22
Computer assignments, 23
Chapter 2. The generation of pseudo-random numbers, 25
2.1 Introduction, 25
2.2 Pseudo-random numbers, 26
2.3 The congruential method, 28
2.3.1 General congruencies methods, 30
2.3.2 Composite generators, 31
2.4 Tausworthe generators, 31
2.5 The lagged Fibonacci generators, 32
2.6 The Mercenne Twister, 33
2.7 Statistical tests of pseudo-random number generators, 36
2.7.1 Hypothesis testing, 37
2.7.2 Frequency test (Monobit test), 38
2.7.3 Serial test, 40
2.7.4 Autocorrelation test, 42
2.7.5 Runs test, 43
2.7.6 Chi-square test for goodness of fit, 45
Problems, 45
Computer assignments, 46
Chapter 3. The generation of stochastic variates, 47
3.1 Introduction, 47
3.2 The inverse transformation method, 47
3.3 Sampling from continuous-time probability distribution, 49
3.3.1 Sampling from a uniform distribution, 49
3.3.2 Sampling from an exponential distribution, 50
ii Computer Simulation Techniques
3.3.3 Sampling from an Erlang distribution, 51
3.3.4 Sampling from a normal distribution, 53
3.4 Sampling from a discrete-time probability distribution, 55
3.4.1 Sampling from a geometric distribution, 56
3.4.2 Sampling from a binomial distribution, 57
3.4.3 Sampling from a Poisson distribution, 58
3.5 Sampling from an empirical probability distribution, 59
3.5.1 Sampling from a discrete-time probability distribution, 59
3.5.2 Sampling from a continuous-time probability distribution, 61
3.6 The Rejection Method, 63
3.7 Monte-Carlo methods, 65
Problems, 66
Computer assignments, 68
Solutions, 69
Chapter 4. Simulation designs, 71
4.1 Introduction, 71
4.2 Event-advance design, 71
4.3 Future event list, 73
4.4 Sequential arrays, 74
4.5 Linked lists, 75
4.5.1 Implementation of a future event list as a linked list, 76
a. Creating and deleting nodes, 76
b. Function to create a new node, 78
c. Deletion of a node, 79
d. Creating linked lists, inserting and removing nodes, 79
e. Inserting a node in a linked list, 80
f. Removing a node from the linked list, 83
4.5.2 Time complexity of linked lists, 86
4.5.3 Doubly linked lists, 87
4.6 Unit-time advance design, 87
4.6.1 Selecting a unit time, 90
4.6.2 Implementation, 91
4.6.3 Event-advance vs. unit-time advance, 91
4.7 Activity based simulation design, 92
4.8 Examples, 94
4.8.1 An inventory system, 94
4.8.2 Round-robin queue, 97
Problems, 101
Computer assignments, 102
Appendix A: Implementing a priority queue as a heap, 104
A.1 A heap, 104
A.1.1 Implementing a heap using an array, 105
a. Maintaining the heap property, 106
A.2 A priority queue using a heap, 109
A.3 Time complexity of priority queues, 112
Table of Contents iii
A.4 Implementing a future event list as a priority queue, 113
Chapter 5. Estimation techniques for analyzing endogenously created data, 115
5.1 Introduction, 115
5.2 Collecting endogenously created data, 115
5.3 Transient state vs. steady-state simulation, 118
5.3.1 Transient-state simulation, 118
5.3.2 Steady-state simulation, 119
5.4 Estimation techniques for steady-state simulation, 120
5.4.1 Estimation of the confidence interval of the mean of a
random variable, 120
a. Estimation of the autocorrelation coefficients, 123
b. Batch means, 128
c. Replications, 129
d. Regenerative method, 131
5.4.2 Estimation of other statistics of a random variable, 138
a. Probability that a random variable lies within a fixed
interval, 138
b. Percentile of a probability distribution, 140
c. Variance of the probability distribution, 141
5.5 Estimation techniques for transient state simulation, 142
5.6 Pilot experiments and sequential procedures for achieving a
required accuracy, 143
5.6.1 Independent replications, 144
5.6.2 Batch means, 144
Computer assignments, 145
Chapter 6. Validation of a simulation model, 149
Computer assignments, 150
Chapter 7. Variance reduction techniques, 155
7.1 Introduction, 155
7.2 The antithetic variates technique, 156
7.3 The control variates technique, 162
Computer assignments, 165
Chapter 8. Simulation projects, 166
8.1 An advance network reservation system – blocking scheme, 166
