Modeling and Simulation of Discrete Event Systems

Computer modeling and simulation (M&S) allows engineers to study and analyze complex systems. Discrete-event system (DES)-M&S is used in modern management, industrial engineering, computer science, and the military. As computer speeds and memory capacity increase, so DES-M&S tools become more powerful and more widely used in solving real-life problems.

Based on over 20 years of evolution within a classroom environment, as well as on decades-long experience in developing simulation-based solutions for high-tech industries, Modeling and Simulation of Discrete-Event Systems is the only book on DES-M&S in which all the major DES modeling formalisms ? activity-based, process-oriented, state-based, and event-based ? are covered in a unified manner:

• A well-defined procedure for building a formal model in the form of event graph, ACD, or state graph
• Diverse types of modeling templates and examples that can be used as building blocks for a complex, real-life model
• A systematic, easy-to-follow procedure combined with sample C# codes for developing simulators in various modeling formalisms
• Simple tutorials as well as sample model files for using popular off-the-shelf simulators such as SIGMA®, ACE®, and Arena®
• Up-to-date research results as well as research issues and directions in DES-M&S

Modeling and Simulation of Discrete-Event Systems is an ideal textbook for undergraduate and graduate students of simulation/industrial engineering and computer science, as well as for simulation practitioners and researchers.

PREFACE xvii

ABBREVIATIONS xix

PART I BASICS OF SYSTEM MODELING AND SIMULATION 1

1. Overview of Computer Simulation 3

1.1 Introduction 3

1.2 What Is a System? 4

1.3 What Is Computer Simulation? 6

1.4 What Is Discrete-Event Simulation? 9

1.5 What Is Continuous Simulation? 11

1.6 What Is Monte Carlo Simulation? 12

1.7 What Are Simulation Experimentation and Optimization? 15

1.8 Review Questions 16

2. Basics of Discrete-Event System Modeling and Simulation 17

2.1 Introduction 17

2.2 How Is a Discrete-Event Simulation Carried Out? 17

2.3 Framework of Discrete-Event System Modeling 23

2.4 Illustrative Examples of DES Modeling and Simulation 32

2.5 Application Frameworks for Discrete-Event System Modeling and Simulation 38

2.6 What to Cover in a Simulation Class 40

2.7 Review Questions 42

PART II FUNDAMENTALS OF DISCRETE-EVENT SYSTEM MODELING AND SIMULATION 43

3. Input Modeling for Simulation 45

3.1 Introduction 45

3.2 Empirical Input Modeling 46

3.3 Overview of Theoretical Distribution Fitting 48

3.4 Theoretical Modeling of Arrival Processes 50

3.5 Theoretical Modeling of Service Times 53

3.6 Input Modeling for Special Applications 57

3.7 Review Questions 59

4. Introduction to Event-Based Modeling and Simulation 69

4.1 Introduction 69

4.2 Modeling and Simulation of a Single Server System 70

4.3 Execution Rules and Specifications of Event Graph Models 72

4.4 Event Graph Modeling Templates 75

4.5 Event Graph Modeling Examples 82

4.6 Execution of Event Graph Models with SIGMA 91

4.7 Developing Your Own Event Graph Simulator 99

4.8 Review Questions 106

5. Parameterized Event Graph Modeling and Simulation 107

5.1 Introduction 107

5.2 Parameterized Event Graph Examples 108

5.3 Execution Rules and Specifications of the Parameterized Event Graph 110

5.4 Parameterized Event Graph Modeling of Tandem Lines 112

5.5 Parameterized Event Graph Modeling of Job Shops 115

5.6 Execution of Parameterized Event Graph Models Using SIGMA 122

5.7 Developing Your Own Parameterized Event Graph Simulator 137

5.8 Review Questions 142

6. Introduction to Activity-Based Modeling and Simulation 143

6.1 Introduction 143

6.2 Definitions and Specifications of an Activity Cycle Diagram 145

6.3 Activity Cycle Diagram Modeling Templates 150

6.4 Activity-Based Modeling Examples 156

6.5 Parameterized Activity Cycle Diagram and Its Application 163

6.6 Execution of Activity Cycle Diagram Models with a Formal Simulator ACE® 171

6.7 Review Questions 183

7. Simulation of ACD Models Using Arena 184

7.1 Introduction 184

7.2 Arena Basics 185

7.3 Activity Cycle Diagram-to-Arena Conversion Templates 197

7.4 Activity Cycle Diagram-Based Arena Modeling Examples 209

7.5 Review Questions 223

8. Output Analysis and Optimization 224

8.1 Introduction 224

8.2 Framework of Simulation Output Analyses 225

8.3 Qualitative Output Analyses 228

8.4 Statistical Output Analyses 230

8.5 Linear Regression Modeling for Output Analyses 234

8.6 Response Surface Methodology for Simulation Optimization 241

8.7 Review Questions 247

PART III ADVANCES IN DISCRETE-EVENT SYSTEM MODELING AND SIMULATION 253

9. State-Based Modeling and Simulation 255

9.1 Introduction 255

9.2 Finite State Machine 256

9.3 Timed Automata 261

9.4 State Graphs 267

9.5 System Modeling with State Graph 271

9.6 Simulation of Composite State Graph Models 283

10. Advanced Topics in Activity-Based Modeling and Simulation 299

10.1 Introduction 299

10.2 Developing Your Own Activity Cycle Diagram Simulators 300

10.3 Modeling with Canceling Arc 310

10.4 Cycle Time Analysis of Work Cells via an Activity Cycle Diagram 313

10.5 Activity Cycle Diagram Modeling of a Flexible Manufacturing System 322

10.6 Formal Model Conversion 329

11. Advanced Event Graph Modeling for Integrated Fab Simulation 338

11.1 Introduction 338

11.2 Flat Panel Display Fabrication System 339

11.3 Production Simulation of a Flat Panel Display Fab 343

11.4 Integrated Simulation of a Flat Panel Display Fab 350

11.5 Automated Material Handling Systems-Embedded Integrated Simulation of Flat Panel Display Fab 362

12. Concepts and Applications of Parallel Simulation 371

12.1 Introduction 371

12.2 Parallel Simulation of Workflow Management System 372

12.3 Overview of High-Level Architecture/Run-Time Infrastructure 378

12.4 Implementation of a Parallel Simulation with High-Level Architecture/Run-Time Infrastructure 383

REFERENCES 395

INDEX 400

Byoung Kyu Choi is a professor in the Department of Industrial and Systems Engineering, KAIST, in Korea and a distinguished adjunct professor of Computer Science at KAU in Saudi Arabia. He received his PhD in Manufacturing Systems Engineering from Purdue University. Since 1983, he has taught and researched in the areas of CAD/CAM and system modeling at KAIST.

Donghun Kang received his PhD in Industrial and Systems Engineering from KAIST and has been working as a postdoctoral researcher at KAIST since February 2011.