Discrete-Event System Simulation

KEY BENEFIT : While most books on simulation focus on particular software tools, Discrete Event System Simulation examines the principles of modeling and analysis that translate to all such tools. This language-independent resource explains the basic aspects of the technology, including the proper collection and analysis of data, the use of analytic techniques, verification and validation of models, and designing simulation experiments. KEY TOPICS : Introduction; Simulation Examples; General Principles; Simulation Software; Statistical Models in Simulation; Queueing Models; Random-number Generation; Random-variate Generation; Input Modeling; VV; Output Analysis for a Single Model; Comparing Multiple Designs; Simulation of Mfg. & MH Systems; Simulation of Computer Systems; Simulation of Communication Systems. MARKET : A useful reference for professionals in operations research, management science, industrial engineering, and information science.

Jerry Banks retired in 1999 as a professor in the School of Industrial and Systems Engineering,

Georgia Institute of Technology, after which he worked as senior simulation technology advisor for Brooks Automation; he is currently a professor at Techno´ogico de Monterrey, M´exico. He is the author, coauthor, editor, or coeditor of twelve books, one set of proceedings, several chapters in texts, and numerous technical papers. His most recent book is RIFD Applied, co-authored with three others, and published by John Wiley in 2007. He is the editor of the Handbook of Simulation, published in 1998 by John Wiley, which won the award for Excellence in Engineering Handbooks from the Professional Scholarly Publishing Division of the Association of American Publishers, Inc. He is also author or coauthor of Getting Started with AutoMod, Second Edition, Introduction to SIMAN V and CINEMA V, Getting Started with GPSS/H, Second Edition, Forecasting and Management of Technology, Second Edition (in preparation) and Principles of Quality Control. He was a founding partner in the simulation-consulting firm Carson/Banks &Associates, Inc., which was purchased by AutoSimulations, Inc. He is a full member of many technical societies, among them the Institute of Industrial Engineers (IIE); he served eight years as that organization’s representative to the Board of the Winter Simulation Conference, including two years as board chair. He is the recipient of the INFORMS College on Simulation Distinguished Service Award for 1999 and was named a Fellow of IIE in 2002. John S. Carson II is an independent simulation consultant. Formerly, he held management and consulting positions in the simulation services and software industry, including positions atAutoSimulations and the AutoMod Group at Brooks Automation. He was the co-founder and president of the simulation services firm Carson/Banks &Associates. He has over 30 years experience in simulation in a wide range of application areas, including manufacturing, distribution, warehousing and material handling, order fulfillment systems, postal systems, transportation and rapid transit systems, port operations (container terminals and bulk handling), and health-care systems. He has taught simulation and operations research at the Georgia Institute of Technology and the University of Florida.

 

Barry L. Nelson is the Charles Deering McCormick Professor and Chair of the Department of Industrial Engineering and Management Sciences at Northwestern University. His research centers on the design and analysis of computer simulation experiments on models of stochastic systems, concentrating on multivariate input modeling and output analysis, optimization via simulation and metamodeling. Application areas include financial engineering, computer performance modeling, quality control, manufacturing and transportation systems. He is the Editor in Chief of Naval Research Logistics, a Fellow of INFORMS, and was simulation area editor of Operations Research, president of the INFORMS (then TIMS) College on Simulation, and Chair of the Board of Directors of the Winter Simulation Conference.

 

David M. Nicol is professor of electrical and computer engineering at the University of Illinois at Urbana-Champaign. He is a long-time contributor in the field of parallel and distributed discrete-event simulations, having written one of the early Ph.D. dissertations on the topic. He has also worked in parallel algorithms, algorithms for mapping workload in parallel architectures, performance analysis, and reliability modeling and analysis. His research contributions extend to 180 articles in leading computer-science journals and conferences. His research is driven largely by problems encountered in industry and government–he has worked closely with researchers at NASA, IBM,AT&T, Bellcore, Motorola, and the Los Alamos, Sandia, and Oak Ridge National Laboratories, as well as a number of aerospace and communication companies. His current interests lie in modeling and simulation of very large systems, particularly communications and other infrastructure, with applications in evaluating system security. From 1997 to 2003 he was the editor-in-chief of the ACM Transactions on Modeling and Computer Simulation. Professor Nicol is a Fellow of the IEEE, a Fellow of the ACM, and the inaugural awardee of the ACM SIGSIM Distinguished Contributions award.

 

I Introduction to Discrete-Event System Simulation 1

Chapter 1 Introduction to Simulation 3

1.1 When Simulation Is the Appropriate Tool 4

1.2 When Simulation Is Not Appropriate 4

1.3 Advantages and Disadvantages of Simulation 5

1.4 Areas of Application 7

1.5 Systems and System Environment 9

1.6 Components of a System 9

1.7 Discrete and Continuous Systems 11

1.8 Model of a System 12

1.9 Types of Models 13

1.10 Discrete-Event System Simulation 13

1.11 Steps in a Simulation Study 14

References 18

Exercises 19

 

Chapter 2 Simulation Examples 21

2.1 Simulation of Queueing Systems 22

2.2 Simulation of Inventory Systems 39

2.3 Other Examples of Simulation 46

2.4 Summary 57

References 57

Exercises 57

 

Chapter 3 General Principles 67

3.1 Concepts in Discrete-Event Simulation 68

3.1.1 The Event Scheduling/Time Advance Algorithm 71

3.1.2 World Views 74

3.1.3 Manual Simulation Using Event Scheduling 77

3.2 List Processing 86

3.2.1 Lists: Basic Properties and Operations 87

3.2.2 Using Arrays for List Processing 88

3.2.3 Using Dynamic Allocation and Linked Lists 90

3.2.4 Advanced Techniques 92

3.3 Summary 92

References 92

Exercises 93

 

Chapter 4 Simulation Software 95

4.1 History of Simulation Software 96

4.1.1 The Period of Search (1955—60) 97

4.1.2 The Advent (1961—65) 97

4.1.3 The Formative Period (1966—70) 97

4.1.4 The Expansion Period (1971—78) 98

4.1.5 Consolidation and Regeneration (1979—86) 98

4.1.6 Integrated Environments (1987—Present) 99

4.2 Selection of Simulation Software 99

4.3 An Example Simulation 102

4.4 Simulation in Java 104

4.5 Simulation in GPSS 112

4.6 Simulation in SSF 117

4.7 Simulation Software 120

4.7.1 Arena 122

4.7.2 AutoMod 123

4.7.3 Extend 124

4.7.4 Flexsim 124

4.7.5 Micro Saint 125

4.7.6 ProModel 125

4.7.7 QUEST 126

4.7.8 SIMUL8 127

4.7.9 WITNESS 128

4.8 Experimentation and Statistical-Analysis Tools 128

4.8.1 Common Features 128

4.8.2 Products 129

References 131

Exercises 132

 

II Mathematical and Statistical Models 147

Chapter 5 Statistical Models in Simulation 149

5.1 Review of Terminology and Concepts 150

5.2 Useful Statistical Models 156

5.3 Discrete Distributions 160

5.4 Continuous Distributions 166

5.5 Poisson Process 186

5.5.1 Properties of a Poisson Process 188

5.5.2 Nonstationary Poisson Process 189

5.6 Empirical Distributions 190

5.7 Summary 193

References 193

Exercises 193

 

Chapter 6 Queueing Models 201

6.1 Characteristics of Queueing Systems 202

6.1.1 The Calling Population 202

6.1.2 System Capacity 204

6.1.3 The Arrival Process 204

6.1.4 Queue Behavior and Queue Discipline 205

6.1.5 Service Times and the Service Mechanism 206

6.2 Queueing Notation 208

6.3 Long-Run Measures of Performance of Queueing Systems 208

6.3.1 Time-Average Number in System L 209

6.3.2 Average Time Spent in System Per Customer w 211

6.3.3 The Conservation Equation: L = λ w 212

6.3.4 Server Utilization 213

6.3.5 Costs in Queueing Problems 218

6.4 Steady-State Behavior of Infinite-Population Markovian Models 220

6.4.1 Single-Server Queues with Poisson Arrivals and Unlimited Capacity: M/G/1 221

6.4.2 Multiserver Queue: M/M/c/∞/∞ 227

6.4.3 Multiserver Queues with Poisson Arrivals and Limited Capacity: M/M/c/N/∞ 233

6.5 Steady-State Behavior of Finite-Population Models (M/M/c/K/K) 235

6.6 Networks of Queues 239

6.7 Summary 241

References 242

Exercises 243

 

III Random Numbers 249

Chapter 7 Random-Number Generation 251

7.1 Properties of Random Numbers 251

7.2 Generation of Pseudo-Random Numbers 252

7.3 Techniques for Generating Random Numbers 253

7.3.1 Linear Congruential Method 254

7.3.2 Combined Linear Congruential Generators 257

7.3.3 Random-Number Streams 259

7.4 Tests for Random Numbers 260

7.4.1 Frequency Tests 261

7.4.2 Tests for Autocorrelation 265

7.5 Summary 267

References 268

Exercises 269

 

Chapter 8 Random-Variate Generation 272

8.1 Inverse-Transform Technique 273

8.1.1 Exponential Distribution 273

8.1.2 Uniform Distribution 276

8.1.3 Weibull Distribution 277

8.1.4 Triangular Distribution 278

8.1.5 Empirical Continuous Distributions 279

8.1.6 Continuous Distributions without a Closed-Form Inverse 283

8.1.7 Discrete Distributions 284

8.2 Acceptance—Rejection Technique 289

8.2.1 Poisson Distribution 290

8.2.2 Nonstationary Poisson Process 293

8.2.3 Gamma Distribution 294

8.3 Special Properties 296

8.3.1 Direct Transformation for the Normal and Lognormal Distributions 296

8.3.2 Convolution Method 298

8.3.3 More Special Properties 299

8.4 Summary 299

References 299

Exercises 300

 

IV Analysis of Simulation Data 305

Chapter 9 Input Modeling 307

9.1 Data Collection 308

9.2 Identifying the Distribution with Data 310

9.2.1 Histograms 310

9.2.2 Selecting the Family of Distributions 313

9.2.3 Quantile—Quantile Plots 316

9.3 Parameter Estimation 319

9.3.1 Preliminary Statistics: Sample Mean and Sample Variance 319

9.3.2 Suggested Estimators 321

9.4 Goodness-of-Fit Tests 326

9.4.1 Chi-Square Test 327

9.4.2 Chi-Square Test with Equal Probabilities 329

9.4.3 Kolmogorov—Smirnov Goodness-of-Fit Test 331

9.4.4 p-Values and “Best Fits” 333

9.5 Fitting a Nonstationary Poisson Process 334

9.6 Selecting Input Models without Data 335

9.7 Multivariate and Time-Series Input Models 337

9.7.1 Covariance and Correlation 337

9.7.2 Multivariate Input Models 338

9.7.3 Time-Series Input Models 340

9.7.4 The Normal-to-Anything Transformation 342

9.8 Summary 344

References 345

Exercises 346

 

Chapter 10 Verification and Validation of Simulation Models 354

10.1 Model-Building, Verification, and Validation 355

10.2 Verification of Simulation Models 356

10.3 Calibration and Validation of Models 361

10.3.1 Face Validity 362

10.3.2 Validation of Model Assumptions 362

10.3.3 Validating Input—Output Transformations 363

10.3.4 Input—Output Validation: Using Historical Input Data 374

10.3.5 Input—Output Validation: Using a Turing Test 378

10.4 Summary 379

References 379

Exercises 381

 

Chapter 11 Output Analysis for a Single Model 383

11.1 Types of Simulations with Respect to Output Analysis 384

11.2 Stochastic Nature of Output Data 387

11.3 Measures of Performance and Their Estimation 390

11.3.1 Point Estimation 390

11.3.2 Confidence-Interval Estimation 392

11.4 Output Analysis for Terminating Simulations 393

11.4.1 Statistical Background 394

11.4.2 Confidence Intervals with Specified Precision 397

11.4.3 Quantiles 399

11.4.4 Estimating Probabilities and Quantiles from Summary Data 400

11.5 Output Analysis for Steady-State Simulations 402

11.5.1 Initialization Bias in Steady-State Simulations 403

11.5.2 Error Estimation for Steady-State Simulation 409

11.5.3 Replication Method for Steady-State Simulations 413

11.5.4 Sample Size in Steady-State Simulations 417

11.5.5 Batch Means for Interval Estimation in Steady-State Simulations 418

11.5.6 Quantiles 422

11.6 Summary 423

References 423

Exercises 424

 

Chapter 12 Comparison and Evaluation of Alternative System Designs 432

12.1 Comparison of Two System Designs 433

12.1.1 Independent Sampling with Equal Variances 436

12.1.2 Independent Sampling with Unequal Variances 438

12.1.3 Common Random Numbers (CRN) 438

12.1.4 Confidence Intervals with Specified Precision 446

12.2 Comparison of Several System Designs 448

12.2.1 Bonferroni Approach to Multiple Comparisons 449

12.2.2 Bonferroni Approach to Selecting the Best 454

12.2.3 Bonferroni Approach to Screening 457

12.3 Metamodeling 458

12.3.1 Simple Linear Regression 459

12.3.2 Testing for Significance of Regression 463

12.3.3 Multiple Linear Regression 466

12.3.4 Random-Number Assignment for Regression 466

12.4 Optimization via Simulation 467

12.4.1 What Does ‘Optimization via Simulation’ Mean? 468

12.4.2 Why is Optimization via Simulation Difficult? 469

12.4.3 Using Robust Heuristics 470

12.4.4 An Illustration: Random Search 473

12.5 Summary 476

References 476

Exercises 477

 

V Applications 483

Chapter 13 Simulation of Manufacturing and Material-Handling Systems 485

13.1 Manufacturing and Material-Handling Simulations 486

13.1.1 Models of Manufacturing Systems 486

13.1.2 Models of Material-Handling 487

13.1.3 Some Common Material-Handling Equipment 488

13.2 Goals and Performance Measures 489

13.3 Issues in Manufacturing and Material-Handling Simulations 490

13.3.1 Modeling Downtimes and Failures 491

13.3.2 Trace-Driven Models 495

13.4 Case Studies of the Simulation of Manufacturing and Material-Handling Systems 496

13.5 Manufacturing Example: A Job-Shop Simulation 499

13.5.1 System Description and Model Assumptions 499

13.5.2 Presimulation Analysis 502

13.5.3 Simulation Model and Analysis of the Designed System 503

13.5.4 Analysis of Station Utilization 503

13.5.5 Analysis of Potential System Improvements 504

13.5.6 Concluding Words 506

13.6 Summary 506

References 506

Exercises 507

 

Chapter 14 Simulation of Computer Systems 517

14.1 Introduction 517

14.2 Simulation Tools 520

14.2.1 Process Orientation 522

14.2.2 Event Orientation 524

14.3 Model Input 525

14.3.1 Modulated Poisson Process 526

14.3.2 Virtual-Memory Referencing 528

14.4 High-Level Computer-System Simulation 534

14.5 CPU Simulation 538

14.6 Memory Simulation 543

14.7 Summary 546

References 546

Exercises 547

 

Chapter 15 Simulation of Computer Networks 550

15.1 Introduction 550

15.2 Traffic Modeling 552

15.3 Media Access Control 555

15.3.1 Token-Passing Protocols 556

15.3.2 Ethernet 559

15.4 Data Link Layer 561

15.5 TCP 562

15.6 Model Construction 569

15.6.1 Construction 569

15.6.2 Example 571

15.7 Summary 573

References 574

Exercises 574

Appendix 576

Index 591