Modeling and Simulation of Discrete Event Systems

✍ Scribed by Byoung Kyu Choi, DongHun Kang

• Publisher: Wiley
• Year: 2013
• Tongue: English
• Leaves: 427
• Edition: 1
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Cover
Title page
Copyright page
Contents
Preface
Abbreviations
Part I: Basics of System Modeling and Simulation
Chapter 1: Overview of Computer Simulation
1.1 Introduction
1.2 What Is a System?
1.2.1 Definitions of Systems
1.2.2 Three Types of Systems
1.2.3 System Boundaries and Hierarchical Structure
1.3 What Is Computer Simulation?
1.3.1 What Is Simulation?
1.3.2 Why Simulate?
1.3.3 Types of Computer Simulation
1.4 What Is Discrete-Event Simulation?
1.4.1 Description of System Dynamics
1.4.2 Simulation Model Trajectory
1.4.3 Collecting Statistics from the Model Trajectory
1.5 What Is Continuous Simulation?
1.5.1 Manual Simulation of the Newtonian Cooling Model
1.5.2 Simulation of the Newtonian Cooling Model Using a Simulator
1.6 What Is Monte Carlo Simulation?
1.6.1 Numerical Integration via Monte Carlo Simulation
1.6.2 Risk Analysis via Monte Carlo Simulation
1.7 What Are Simulation Experimentation and Optimization?
1.8 Review Questions
Chapter 2: Basics of Discrete-Event System Modeling and Simulation
2.1 Introduction
2.2 How Is a Discrete-Event Simulation Carried Out?
2.2.1 Event Routines
2.2.2 Simulation Model Trajectory
2.2.3 Manual Simulation Execution
2.2.4 Flow Chart of Manual Simulation Procedure
2.3 Framework of Discrete-Event System Modeling
2.3.1 What Are Modeling Components and Reference Model?
2.3.2 What Is a Discrete-Event System (DES) Modeling Formalism?
2.3.3 What Is a Formal Model and How Is It Specified?
2.3.4 Integrated Framework of DES Modeling
2.4 Illustrative Examples of DES Modeling and Simulation
2.4.1 How to Build and Simulate an Event Graph Model of a DES
2.4.2 How to Build and Simulate an ACD Model of a DES
2.4.3 How to Build and Simulate a State Graph Model of a DES
2.5 Application Frameworks for Discrete-Event System Modeling and Simulation
2.5.1 How Is the M&S Life Cycle Managed?
2.5.2 Framework for Factory Life-Cycle Support
2.6 What to Cover in a Simulation Class
2.6.1 Event-Based M&S and Event-Graph Simulation with SIGMA®
2.6.2 Activity-Based M&S and Hands-On Modeling Practice with Arena®
2.6.3 State-Based M&S
2.7 Review Questions
Part II: Fundamentals of Discrete-Event System Modeling and Simulation
Chapter 3: Input Modeling for Simulation
3.1 Introduction
3.2 Empirical Input Modeling
3.2.1 Nonparametric Modeling
3.2.2 Empirical Modeling of Individual Data
3.2.3 Empirical Modeling of Grouped Data
3.3 Overview of Theoretical Distribution Fitting
3.3.1 Data Independence Checking
3.3.2 Distribution Function Selection
3.3.3 Parameter Estimation
3.3.4 Goodness-of-Fit Test
3.3.5 Overview of Random Variate Generation
3.4 Theoretical Modeling of Arrival Processes
3.4.1 Theoretical Basis for Arrival Process Modeling
3.4.2 Generation of Inter-Arrival Times for a Constant Arrival Rate
3.4.3 Generation of Inter-Arrival Times for Varying Arrival Rates
3.5 Theoretical Modeling of Service Times
3.5.1 Generation of Service Time in the Absence of Data
3.5.2 Generation of Service Times from Collected Data
3.6 Input Modeling for Special Applications
3.6.1 Interfailure Time Modeling
3.6.2 Inspection Process Modeling
3.6.3 Batch Size Modeling
3.7 Review Questions
Appendix 3A: Parameter Estimation
3A.1 Exponential Distribution
3A.2 Erlang Distribution
3A.3 Beta Distribution
3A.4 Weibull Distribution
3A.5 Normal and Lognormal Distributions
Appendix 3B: Random Variate Generation
3B.1 Exponential Random Variate
3B.2 Erlang Random Variate
3B.3 Beta Random Variate
3B.4 Weibull Random Variate
3B.5 Normal and Lognormal Random Variates
3B.6 Triangular Random Variate
Chapter 4: Introduction to Event-Based Modeling and Simulation
4.1 Introduction
4.2 Modeling and Simulation of a Single Server System
4.2.1 Reference Modeling
4.2.2 Formal Modeling
4.2.3 Model Execution
4.3 Execution Rules and Specifications of Event Graph Models
4.3.1 Event Graph Execution Rules
4.3.2 Tabular Specification of Event Graph Models
4.3.3 Algebraic Specifications of an Event Graph Model
4.4 Event Graph Modeling Templates
4.4.1 Single Queue Models
4.4.2 Tandem Line Models
4.5 Event Graph Modeling Examples
4.5.1 Flexible Multi-Server System with Fluctuating Arrival Rates
4.5.2 Car Repair Shop
4.5.3 Project Management Modeling
4.5.4 Conveyor-Driven Serial Line
4.5.5 Inline-Type Manufacturing Cell Modeling
4.6 Execution of Event Graph Models with SIGMA
4.6.1 Simulation of a Single Server System with SIGMA
4.6.2 Simulation of a Conveyor-Driven Serial Line with SIGMA
4.7 Developing Your Own Event Graph Simulator
4.7.1 Functions for Handling Events and Managing Queues
4.7.2 Functions for Generating Random Variates
4.7.3 Event Routines
4.7.4 Next Event Methodology of Simulation Execution
4.7.5 Single Server System Simulator
4.8 Review Questions
Chapter 5: Parameterized Event Graph Modeling and Simulation
5.1 Introduction
5.2 Parameterized Event Graph Examples
5.2.1 Introducing Index Variables to a Repeating Event-Vertex Pattern
5.2.2 Passing Attribute Values of Each Entity along Event Vertices
5.3 Execution Rules and Specifications of the Parameterized Event Graph
5.3.1 Execution Rules of the PEG Model
5.3.2 Tabular Specifications of the PEG Model
5.3.3 Algebraic Specifications of the PEG Model
5.4 Parameterized Event Graph Modeling of Tandem Lines
5.4.1 PEG Modeling of an Unlimited Buffer Tandem Line
5.4.2 PEG Modeling of a Limited Buffer Tandem Line
5.4.3 PEG Modeling of a Conveyor-Driven Serial Line
5.5 Parameterized Event Graph Modeling of Job Shops
5.5.1 PEG Modeling of a Simple Job Shop without Transport
5.5.2 PEG Modeling of a Job Shop with Transport and Setup Times
5.5.3 PEG Modeling of an Inline Job Shop
5.5.4 PEG Modeling of a Mixed Job Shop
5.6 Execution of Parameterized Event Graph Models using SIGMA
5.6.1 Collecting Sojourn Time Statistics Using SIGMA Functions
5.6.2 Simulating a Simple Service Shop with SIGMA
5.6.3 Simulation of a Three-Stage Tandem Line Using SIGMA
5.6.4 Simulation of the Simple Job Shop with SIGMA
5.7 Developing Your Own Parameterized Event Graph Simulator
5.7.1 Tandem Line PEG Simulator
5.7.2 Simple Job Shop PEG Simulator
5.8 Review Questions
Chapter 6: Introduction to Activity-Based Modeling and Simulation
6.1 Introduction
6.2 Definitions and Specifications of an Activity Cycle Diagram
6.2.1 Definitions of an ACD
6.2.2 Execution Rules and Tabular Specifications of an ACD
6.2.3 Algebraic Specifications of an ACD
6.3 Activity Cycle Diagram Modeling Templates
6.3.1 ACD Template for Flexible Multi-Server System Modeling
6.3.2 ACD Template for Limited Buffer Tandem Line Modeling
6.3.3 ACD Template for Nonstationary Arrival Process
6.3.4 ACD Template for Batched Service Modeling
6.3.5 ACD Template for Joining Operation Modeling
6.3.6 ACD Template for Probabilistic Branching Modeling
6.3.7 ACD Template for Resource Failure Modeling
6.4 Activity-Based Modeling Examples
6.4.1 Activity-Based Modeling of a Worker-Operated Tandem Line
6.4.2 Activity-Based Modeling of an Inspection-Repair Line
6.4.3 Activity-Based Modeling of a Restaurant
6.4.4 Activity-Based Modeling of a Simple Service Station
6.4.5 Activity-Based Modeling of a Car Repair Shop
6.4.6 Activity-Based Modeling of a Project Management System
6.4.7 Activity-Based Modeling of a Conveyor-Driven Serial Line
6.5 Parameterized Activity Cycle Diagram and Its Application
6.5.1 Definition and Specifications of Parameterized ACD
6.5.2 Rules for Executing the P-ACD Model
6.5.3 P-ACD Modeling of Tandem Lines
6.5.4 P-ACD Modeling of Job Shops
6.6 Execution of Activity Cycle Diagram Models with a Formal Simulator ACE®
6.6.1 Simulation of Single Server Model with ACE
6.6.2 Simulation of Probabilistic Branching Model with ACE
6.6.3 Simulation of Resource Failure Model with ACE
6.6.4 Simulation of Simple Service Station Model with ACE
6.7 Review Questions
Chapter 7: Simulation of ACD Models Using Arena®
7.1 Introduction
7.2 Arena Basics
7.2.1 Arena Modeling Environment
7.2.2 Building a Flowchart Model of a Process-Inspect Line
7.2.3 Completing a Static Model of a Process-Inspect Line
7.2.4 Arena Simulation and Output Reports
7.2.5 Arena Modules
7.3 Activity Cycle Diagram-to-Arena Conversion Templates
7.3.1 Template for Fixed Multi-Server Modeling
7.3.2 Template for Flexible Multi-Server Modeling
7.3.3 Template for Balking (Conditional Branching) Modeling
7.3.4 Template for Limited Buffer Tandem Line Modeling
7.3.5 Template for Nonstationary Arrival Process Modeling
7.3.6 Template for Joining Operation Modeling
7.3.7 Template for Inspection (Probabilistic Branching) Modeling
7.3.8 Template for Resource Failure Modeling
7.4 Activity Cycle Diagram-Based Arena Modeling Examples
7.4.1 ACD-Based Arena Modeling of a Worker-Operated Tandem Line
7.4.2 ACD-Based Arena Modeling of Restaurant
7.4.3 ACD-Based Arena Modeling of a Simple Service Station
7.4.4 ACD-Based Arena Modeling of a Project Management System
7.4.5 ACD-Based Arena Modeling of a Job Shop
7.4.6 ACD-Based Arena Modeling of a Conveyor-Driven Serial Line
7.5 Review Questions
Chapter 8: Output Analysis and Optimization
8.1 Introduction
8.2 Framework of Simulation Output Analyses
8.2.1 Verification and Calibration
8.2.2 Simulation Experimentation
8.2.3 Communication and Presentation
8.3 Qualitative Output Analyses
8.4 Statistical Output ANALYSES
8.4.1 Statistical Output Analyses for Terminating Simulations
8.4.2 Statistical Output Analyses for Nonterminating Simulations
8.4.3 Statistical Output Analyses for Comparing Alternative Systems
8.5 Linear Regression Modeling for Output Analyses
8.5.1 Linear Regression Models
8.5.2 Regression Parameter Estimation
8.5.3 Test for Significance of Regression
8.5.4 Linear Regression Modeling Example1
8.5.5 Regression Model Fitting for Qualitative Variables
8.6 Response Surface Methodology for Simulation Optimization
8.6.1 Overview of RSM for Process Optimization
8.6.2 Searching for Optimum Regions with the Steepest Ascent
8.6.3 Second-Order Model Fitting for Optimization
8.7 Review Questions
Appendix 8A: Student’s t-Distribution
8A.1 Definition
8A.2 Derivation of the t-Statistic
8A.3 Table of Critical t-Values with Degrees of Freedom (df)
Appendix 8B: Student’s t-Tests
8B.1 One Sample t-Test
8B.2 Unpaired Two Sample t-Test
Part III: Advances in Discrete-Event System Modeling and Simulation
Chapter 9: State-Based Modeling and Simulation
9.1 Introduction
9.2 Finite State Machine
9.2.1 Existing Definitions of Finite State Machines
9.2.2 Finite State Machine Models
9.2.3 Finite State Machine Modeling of Buffer Storage and Single Server Systems
9.2.4 Execution of Finite State Machine Models
9.3 Timed Automata
9.3.1 Language and Automata
9.3.2 Timed Automata
9.3.3 Timed Automata with Guards
9.3.4 Networks of Timed Automata
9.4 State Graphs
9.4.1 State Variables and Macro States
9.4.2 Timers and System Variables
9.4.3 Conventions for Building State Graphs and State Transition Tables
9.5 System Modeling With State Graphs
9.5.1 State Graph Modeling of Dining Philosophers
9.5.2 State Graph Modeling of a Table Tennis Game
9.5.3 State Graph Modeling of a Tandem Line
9.5.4 State Graph Modeling of a Conveyor-Driven Serial Line
9.5.5 State Graph Modeling of Traffic Intersection Systems
9.6 Simulation of Composite State Graph Models
9.6.1 Framework of a State Graph Simulator
9.6.2 Synchronization Manager
9.6.3 Atomic Simulators
9.6.4 Table Tennis Game Simulator
9.6.5 State Graph Simulator for Reactive Systems
9.6.6 SGS®
Appendix 9A: DEVS
9A.1 Definitions of DEVS
9A.2 DEVS Simulators
Chapter 10: Advanced Topics in Activity-Based Modeling and Simulation
10.1 Introduction
10.2 Developing Your Own Activity Cycle Diagram Simulators
10.2.1 Tocher’s Three-Phase Process
10.2.2 Activity Scanning Algorithm
10.2.3 ACD Simulator
10.2.4 P-ACD Simulator
10.2.5 Collecting Statistics
10.3 Modeling with Canceling Arc
10.3.1 ACD Model of Single Server System with Reneging
10.3.2 ACD Model of Resource Failure
10.3.3 ACD Model of Time-Constrained Processing
10.3.4 Execution of Canceling Arc
10.4 Cycle Time Analysis of Work Cells via an Activity Cycle Diagram
10.4.1 Cycle Time Analysis of Single-Armed Robot Work Cell
10.4.2 Cycle Time Analysis of Single Hoist Plating Line
10.4.3 Cycle Time Analysis of Dual-Armed Robot Cluster Tool
10.5 Activity Cycle Diagram Modeling of a Flexible Manufacturing System
10.5.1 ACD Modeling of Job Flows in FMS
10.5.2 P-ACD Modeling of Job Routing in FMS
10.5.3 P-ACD Modeling of AGV Dispatching Rules in FMS
10.5.4 P-ACD Modeling of Refixture Operation and Heterogeneous FMS
10.6 Formal Model Conversion
10.6.1 Conversion of ACD Models to Event Graph (EG) Models
10.6.2 Conversion of ACD Models to State Graph (SG) Models
10.6.3 Examples of Formal Model Conversion
Appendix 10A: Petri Nets
10A.1 Definitions of Petri Nets
10A.2 Petri-Net State and Execution
10A.3 Extended Petri Nets and the ACD
10A.4 Restricted Petri Nets
10A.5 Modeling with Petri Nets
Chapter 11: Advanced Event Graph Modeling for Integrated Fab Simulation
11.1 Introduction
11.2 Flat Panel Display Fabrication System
11.2.1 Overview of FPD Fab
11.2.2 FPD Processing Equipment
11.2.3 Material Handling System
11.3 Production Simulation of a Flat Panel Display Fab
11.3.1 Modeling of Uni-Inline Job Shop
11.3.2 Modeling of Oven Type Job Shop
11.3.3 Modeling of Heterogeneous Job Shop
11.3.4 Object-Oriented Event Graph Simulator for Production Simulation
11.4 Integrated Simulation of a Flat Panel Display Fab
11.4.1 Modeling of Job Shop for Integrated Simulation
11.4.2 Modeling of Conveyor Operation
11.4.3 Modeling of the Interface between Conveyor and Inline Stocker
11.4.4 Modeling of the Interface between Uni-inline Cells and Inline Stocker
11.4.5 Modeling of the Interface between an Oven and Inline Stocker
11.4.6 Modeling of Inline Stocker Operation
11.4.7 Integrated Fab Simulator
11.5 Automated Material Handling Systems-Embedded Integrated Simulation of Flat Panel Display Fab
11.5.1 Concept of AMHS-Embedded Fab Simulation
11.5.2 Framework of AMHS-Embedded Fab Simulation System
11.5.3 Simulator for AMHS-Embedded Integrated Fab Simulation
11.5.4 IFS®
Chapter 12: Concepts and Applications of Parallel Simulation
12.1 Introduction
12.2 Parallel Simulation of Workflow Management System
12.2.1 Enactment Service Mechanism of WfMS
12.2.2 Framework of Parallel Simulation of WfMS
12.2.3 State Graph Modeling of an Enactment Server and Sync Manager
12.2.4 State Graph Modeling of Participant Simulators
12.2.5 Implementation of a Workflow Simulator
12.3 Overview of High-Level Architecture/Run-Time Infrastructure
12.3.1 Basics of HLA/RTI
12.3.2 HLA Federation Architecture
12.3.3 Overview of Federation Execution
12.4 Implementation of a Parallel Simulation with High-Level Architecture/Run-Time Infrastructure
12.4.1 The Sushi Restaurant Federation
12.4.2 Preparation of an FED File
12.4.3 Preparation of the Federate Code (of the Production Federate)
12.4.4 Executing the Restaurant Federation
References
Index