Modeling and Simulation of Discrete Event Systems E-Book

Byoung Kyu Choi

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 538

Veröffentlichungsjahr: 2013

Beschreibung

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.

Leseprobe

Table of Contents

Title page

Copyright page

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.3 What Is Computer Simulation?

1.4 What Is Discrete-Event Simulation?

1.5 What Is Continuous Simulation?

1.6 What Is 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.3 Framework of Discrete-Event System Modeling

2.4 Illustrative Examples of DES Modeling and Simulation

2.5 Application Frameworks for Discrete-Event System Modeling and Simulation

2.6 What to Cover in a Simulation Class

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.3 Overview of Theoretical Distribution Fitting

3.4 Theoretical Modeling of Arrival Processes

3.5 Theoretical Modeling of Service Times

3.6 Input Modeling for Special Applications

3.7 Review Questions

Appendix 3A: Parameter Estimation

Appendix 3B: Random Variate Generation

Chapter 4: Introduction to Event-Based Modeling and Simulation

4.1 Introduction

4.2 Modeling and Simulation of a Single Server System

4.3 Execution Rules and Specifications of Event Graph Models

4.4 Event Graph Modeling Templates

4.5 Event Graph Modeling Examples

4.6 Execution of Event Graph Models with SIGMA

4.7 Developing Your Own Event Graph Simulator

4.8 Review Questions

Chapter 5: Parameterized Event Graph Modeling and Simulation

5.1 Introduction

5.2 Parameterized Event Graph Examples

5.3 Execution Rules and Specifications of the Parameterized Event Graph

5.4 Parameterized Event Graph Modeling of Tandem Lines

5.5 Parameterized Event Graph Modeling of Job Shops

5.6 Execution of Parameterized Event Graph Models using SIGMA

5.7 Developing Your Own Parameterized Event Graph 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.3 Activity Cycle Diagram Modeling Templates

6.4 Activity-Based Modeling Examples

6.5 Parameterized Activity Cycle Diagram and Its Application

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

6.7 Review Questions

Chapter 7: Simulation of ACD Models Using Arena®

7.1 Introduction

7.2 Arena Basics

7.3 Activity Cycle Diagram-to-Arena Conversion Templates

7.4 Activity Cycle Diagram-Based Arena Modeling Examples

7.5 Review Questions

Chapter 8: Output Analysis and Optimization

8.1 Introduction

8.2 Framework of Simulation Output Analyses

8.3 Qualitative Output Analyses

8.4 Statistical Output Analyses

8.5 Linear Regression Modeling for Output Analyses

8.6 Response Surface Methodology for Simulation Optimization

8.7 Review Questions

Appendix 8A: Student's t-Distribution

Appendix 8B: Student's t-Tests

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.3 Timed Automata

9.4 State Graphs

9.5 System Modeling With State Graphs

9.6 Simulation of Composite State Graph Models

Appendix 9A: DEVS

Chapter 10: Advanced Topics in Activity-Based Modeling and Simulation

10.1 Introduction

10.2 Developing Your Own Activity Cycle Diagram Simulators

10.3 Modeling with Canceling Arc

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

10.5 Activity Cycle Diagram Modeling of a Flexible Manufacturing System

10.6 Formal Model Conversion

Appendix 10A: Petri Nets

Chapter 11: Advanced Event Graph Modeling for Integrated Fab Simulation

11.1 Introduction

11.2 Flat Panel Display Fabrication System

11.3 Production Simulation of a Flat Panel Display Fab

11.4 Integrated Simulation of a Flat Panel Display Fab

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

Chapter 12: Concepts and Applications of Parallel Simulation

12.1 Introduction

12.2 Parallel Simulation of Workflow Management System

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

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

References

Index

Online Supplements

Numerous supplemental materials including software downloads are provided on the offi cial website of the book at http://VMS-technology.com/book. The supplemental materials are grouped into (1) M&S practices with commercial simulators, (2) developing your own dedicated simulators, and (3) integrated simulation of electronics Fabs. The commercials simulators covered are an event-based simulator SIGMA®, an activity-based simulator ACE®, a statebased simulator SGS®, and an entity-based simulator Arena®.

Cover image: 08-17-09 © Mark Divers (iStock photo ID: 10295380)

Copyright © 2013 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New Jersey

Published simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the Web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permissions.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our website at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Choi, Byoung Kyu, 1949–

Modeling and simulation of discrete-event systems / Byoung Kyu Choi, Donghun Kang.

pages cm

Includes index.

ISBN 978-1-118-38699-6 (cloth)

1. Discrete-time systems–Simulation methods. I. Kang, Donghun, 1981– II. Title.

T57.62.C377 2013

003'.83–dc23

2013013970

Preface

This book provides comprehensive, in-depth coverage of modeling and simulation (M&S) of discrete-event systems (DESs). Here, the term M&S refers to computer simulation, with an emphasis on modeling real-life DESs and executing the models. The current state-of-the-art in DES M&S is a result of the breakthroughs in the following areas: (1) activity-based modeling formalism pioneered by K.D. Tocher in late 1950s; (2) the advent of process-oriented simulation languages, such as GPSS and SLAM, in the early 1970s; (3) state-based modeling formalism, or DEVS, founded by Bernard Zeigler in the mid-1970s; and (4) event-based modeling formalism as matured by Lee Schruben since the early 1980s.

There exists at least one classic textbook in each area—a textbook on activity-based modeling by Carrie, a few books on state-based (DEVS) modeling by Zeigler, a textbook on event-based modeling by Schruben, and a few books on process-oriented languages such as Arena® and ProModel®. In addition, there are quite a few books focusing on statistical notions of computer simulation. The researchers in each area advocate their own views as central to DES M&S. Only a couple of books (e.g., Fishwick) propose an integrated model engineering framework.

This book presents an integrated M&S framework covering all four DES M&S breakthrough areas. It is a product of 30 years of teaching at KAIST, as well as sponsored research and development projects at the authors' lab at KAIST, VMS (virtual manufacturing system) Lab, which has been a government-endowed National Research Lab since 1999. In particular, the practice-oriented theme of this book is a result of the authors' decade-long experience in developing simulation-based scheduling (SBS) solutions for Samsung Electronics and other companies in Korea. Virtually all the Samsung's semiconductor fabrication plants (Fabs) and flat panel display (FPD) Fabs are run utilizing solutions originated by the authors' lab, and upgraded and supported by a spin-off venture company.

This book is divided into three parts: Part I, Basics of System Modeling and Simulation; Part II, Fundamentals of Discrete-Event System Modeling and Simulation; and Part III, Advances in Discrete-Event System Modeling and Simulation. Parts I and II are designed as a primary textbook for an undergraduate level M&S course in Industrial Engineering, Computer Science, and Management Science. With Part III, it is designed as a graduate-level course. This book comprehensively covers the state-of-the art modeling formalisms and execution algorithms in DES M&S thereby serving as a main reference for M&S researchers in academia. This book provides an easy-to-understand guide for simulation practitioners in industry using off-the-shelf simulators such as SIGMA® and Arena®. Finally, this book reveals a number of “secrets” for developing your own simulators: event graph simulator, ACD simulator, state graph simulator, and integrated Fab simulator—making it a valuable resource for M&S solution developers.

The book is largely self-contained, and few prerequisites are needed for understanding its main contents. However, some prior knowledge will help readers understand specific sections:

(1) Basic knowledge of statistics and probability (Chapter 3, Input Modeling);

(2) Basic knowledge of linear algebra (Chapter 8, Output Analysis and Optimization)

(3) Experience with computer programming (Sections on developing your own simulators, e.g. Sections 5.7 and 10.2).

Perhaps the most critical prerequisite for mastering this book is enthusiasm and commitment toward M&S. This book is about the art of M&S, and like other art forms, can only be mastered through persistent practice.

The authors wish to express their special thanks to Prof. K.H. Han of Gyeongsang National University for using part of this book in his class and providing valuable comments that led to its improvement; to Prof. I.K. Moon of Seoul National University and Prof. S.C. Park of Ajou University for their input during the early stage of writing this book; and to Prof. Lee Schruben of Berkeley for his encouragement and support. For developing sample models and exercise problems, and for executing “prototype” simulation models appearing in the book, we would like to thank our graduate students in the VMS Lab at KAIST, especially H.S. Kim, T.J. Choi, and E.H. Song.

Finally, Byoung Choi thanks his wife, Yong, and his son and best friend Samuel, for their support and encouragement. Donghun Kang thanks his parents for their loving care and support.

Byoung Kyu Choi

Donghun Kang

Daejeon, Korea, June 2013

Abbreviations

Part I

Basics of System Modeling and Simulation

We think by “constructing mental models and then simulating them in order to draw conclusions or make decisions.” Thus, modeling and simulation (M&S) constitutes the central part of our thinking process. “I think, therefore I am” is a philosophical statement used by the French philosopher Descartes, which became a foundational element of Western philosophy. Therefore, if we combine the philosophical notion of thinking with the engineering definition of M&S, we may say that “we are engineers and scientists because we can model systems and simulate them.” Furthermore, if our brain is not powerful enough to simulate a given complex system, we rely on computers to perform a computer simulation.

A dictionary definition of simulation is the technique of imitating the behavior of some situation by means of an analogous situation or apparatus to gain information more conveniently or to train personnel, while an academic definition of computer simulation is the discipline of designing a model of a system, simulating the model on a digital computer, and analyzing the execution output. In recent years, the term modeling and simulation (M&S) seems to be preferred to the term for computer simulation, with an emphasis on modeling. Part I of this book has two chapters, and it aims to provide the readers with a basic but comprehensive treatment of computer simulation.

Chapter 1, “Overview of Computer Simulation,” will provide answers to the following basic questions in computer simulation:

1. What is a system?

2. What is computer simulation?

3. What is discrete-event simulation?

4. What is continuous simulation?

5. What is Monte Carlo simulation?

6. What are simulation experimentation and optimization?

Chapter 2, “Basics of Discrete-Event System Modeling & Simulation,” aims to provide answers to the following basic questions in discrete-event system (DES) M&S:

1. How is a discrete-event simulation carried out?

2. What are modeling components and a reference model?

3. What is a discrete-event system modeling formalism?

4. What is a formal model and how it is specified?

5. What is the integrated framework of discrete-event system modeling?

6. How do we build and simulate an event graph or activity cycle diagram (ACD) model of a DES?

7. How is the M&S life cycle managed?

Chapter 1

Overview of Computer Simulation

The wise man is one who knows what he does not know.

—Tao Te Ching

1.1 Introduction

Richmond [2003] defines thinking as “constructing mental models and then simulating them in order to draw conclusions or make decisions.” Namely, he defines thinking as mental simulation. When the situation is too complex to be analyzed by mental simulation alone, we rely on computer simulation. According to Schruben [2012], simulation models provide unlimited virtual power: “If you can think of something, you can simulate it. Experimenting in a simulated world, you can change anything, in any way, at any time—even change time itself.”

Fishwick [1995] defines computer simulation as the discipline of designing a model of a system, simulating the model on a digital computer, and analyzing the execution output. In the military, where computer simulation is extensively used in training personnel (e.g., war game simulation) and acquiring weapon systems (e.g., simulation-based acquisition), the term modeling and simulation (M&S) is used in place of computer simulation. In this book, these two terms are used interchangeably.

The purpose of this chapter is to provide the reader with a basic understanding of computer simulation. After studying this chapter, you should be able to answer the following questions:

1. What are the common characteristics that lead to a conceptual definition of system?

2. What are the three types of systems?

3. What are the three subsystems in a feedback control system?

4. What are the three types of virtual environment simulation?

5. What are the three types of computer simulation?

6. What is the simulation model trajectory of a discrete-event system?

7. What is Monte Carlo simulation?

8. What is sensitivity analysis in simulation experimentation?

This chapter is organized as follows: Definitions and structures of systems are given in Section 1.2. Section 1.3 provides definitions and applications of simulation. The subsequent three sections introduce the three simulation types: discrete-event simulation in Section 1.4, continuous simulation in Section 1.5, and Monte Carlo simulation in Section 1.6. Finally, a basic framework of simulation experimentation is presented in Section 1.7.

1.2 What Is a System?

1.2.1 Definitions of Systems

Systems are encountered everywhere in the world. While those systems differ in their specifics, they share common characteristics that lead to a conceptual definition of a system. In Wu [1992], a system is defined as “a collection of components which are interrelated in an organized way and work together towards the accomplishment of certain logical and purposeful end.” Thus, any portion of the real world may be defined as a system if it has the following characteristics: (1) it has a purpose or purposes, (2) its components are connected in an organized manner, and (3) they work together to achieve common objectives. A system consisting of people is often called a team. Needless to say, a mere crowd of people sharing no common objectives is not a team.

When defining a system, the concept of state variable plays a key role. A state variable is a particular measurable property of an object or system. Examples of state variables are the number of jobs in a buffer, status of a machine, temperature of an oven, etc. A system in which the state variables change instantaneously at discrete points in time is called a discrete-event system, whereas a system in which state variables change continuously over time is called a continuous system.

1.2.2 Three Types of Systems

Our universe, which is full of systems everywhere, may be viewed from the five levels of detail (Fig. 1.1): from the subatomic level to cosmological level. In the subatomic level, interactions among the components of a system are described using quantum mechanics, which is a physical science dealing with the behavior of matter and energy on the scale of atoms and subatomic particles. It is interesting to find that quantum mechanics is also used in modeling a system at the cosmological level [Mostafazadeh 2004]. Thus, a system in the subatomic level or cosmological level may be called a quantum system.

Fig. 1.1. Five levels of details of system definitions in the universe.

A system in the electromechanical level usually has components whose physical dynamics are described using differential equations of effort, such as force and voltage, and flow, such as velocity and current [Karnopp et al. 2000]. The behaviors of ecological systems and socioeconomic systems are usually described using differential equations of flow [Hannon and Ruth 2001]. As a result, these systems are called a continuous system or a differential equation system.

Systems in the middle level are industrial systems which are more conveniently described in terms of discrete events, and they are discrete-event systems. An event is an instance of changes in state variables. A special type of this system is a digital system such as a computer whose states are defined by a finite number of 0s and 1s.

1.2.3 System Boundaries and Hierarchical Structure

Everything in our world is connected to everything else in some way, which is known as the small world phenomenon [Kleinberg 2000]. Thus, in order to define a system, it is first necessary to isolate the components of the system from the remaining world and to enclose them within a system boundary.

A set of isolated components of primary interest is called a target system. The target system may have a number of subsystems, and it may be a subsystem of a higher-level system called a wider system. The wider system is separated from the external environment by a boundary [Wu 1992]. In summary, a typical system consists of a target system (composed of its subsystems) and a wider system (in which the target system is included). The system of interest consisting of a target system and its wider system is often referred to as a source system.

Most dynamic systems in engineering and management are feedback control systems. Key subsystems in a feedback control system are operational, monitoring, and decision-making subsystems. The operational subsystem carries out the system's tasks, and the monitoring subsystem monitors system performances and reports to the decision-making subsystem. The decision-making subsystem is responsible for making decisions and taking corrective actions. The rela­tionships among the target feedback control system, its subsystems, wider system, and external environment are shown in Fig. 1.2 [Wu 1992]. For example, if your simulation study is focused on an emergency room of a hospital, the emergency room would become the target system and the hospital the wider system.

Fig. 1.2. Hierarchical structure of feedback control system.

The wider system influences the target system by setting goals, supporting operations, and checking performances. The target system is subject to disturbances from the external environment. In addition, the external environment provides the wider system with higher-level objectives and other external influences.

Exercise 1.1. Give an example of a feedback control system involving people and identify all the components of the system.

1.3 What Is Computer Simulation?

1.3.1 What Is Simulation?

A dictionary definition of simulation is “the technique of imitating the behavior of some situation by means of an analogous situation or apparatus to gain information more conveniently or to train (or entertain) personnel.” “Some situation” in the definition corresponds to a source system, and an apparatus is a simulator. As elaborated in the definition, there are two types of simulation objectives: one is to gain information and the other is to train or entertain personnel. The former is often called an analytic simulation and the latter a virtual environment simulation [Fujimoto 2000].

The main purpose of an analytic simulation is the quantitative analysis of the source system based on “exact” data. Thus, the simulation should be executed in an as-fast-as-possible manner and be able to precisely reproduce the event sequence of the source system. An analytic simulation is often referred to as a time-stamp simulation. A virtual environment simulation is executed in a scaled real-time while creating virtual environments, and it is often referred to as a time-delay simulation. Shown in Fig. 1.3 are scenes from a war-game simulation and from a computer game.

Fig. 1.3. Examples of virtual environment simulation.

An analytic simulation with human interaction is called a constructive simulation, and one without human interaction an autonomous simulation. If humans interact with the simulation as a participant, it is referred to as human-in-the-loop (HIL) simulation; if machines or software agents interact with the simulation, it is called a machine-in-the-loop (MIL) simulation. A virtual environment simulation without HIL/MIL is often called a virtual simulation; one with HIL only a constructive simulation; one with both HIL and MIL a live simulation. Figure 1.4 shows the classification of computer simulation.

Fig. 1.4. Classification of computer simulation.

1.3.2 Why Simulate?

Modeling and simulation is the central part of our thinking process. When the situation is too complex to be analyzed by mental simulation alone, we use a computer for simulating the situation. Let's consider the following situations:

1. Finding optimal dispatching rules at a modern 300-mm semiconductor Fab

2. Evaluating alternative designs for hospitals, post offices, call centers, etc.

3. Designing the material handling system of a 3 billion dollar thin film transistor–liquid crystal display (TFT-LCD) Fab

4. Planning a wireless network for a telecommunication company

5. Evaluating high-tech weapons systems for a simulation-based acquisition

6. Designing or upgrading the urban traffic system of a big city

7. Evaluating anti-pollution policies to control pollutions in river systems

8. Evaluating risks in project schedules and financial derivatives

For the above real-life situations, simulation may be the only means to tackle the problems. In practice, simulation may be needed because experimenting with the real-life system is not feasible; your budget does not allow you to acquire an expensive prototype; a real test is risky; your customer wants it “yesterday”; your team wants to test several solutions and to compare them; you would like to keep a way to reproduce its performances later.

The simulation of a discrete-event system is called a discrete-event simulation, and that of a continuous system a continuous simulation. A class of computational schemes that rely on repeated random sampling to compute their results is referred to as Monte Carlo simulation. Among the above situations, Situations 1–6 are concerned with a discrete-event simulation. Situation 7 is concerned with a continuous simulation and Situation 8 with a Monte Carlo simulation.

1.3.3 Types of Computer Simulation

As depicted earlier in Fig. 1.1, the dynamic systems in the universe can be classified into five levels and three types. The three types of dynamic systems are: (1) discrete-event systems, (2) continuous systems, and (3) quantum systems. Thus, it is conceivable that there is one type of computer simulation for each system type. Discrete-event simulation and continuous simulation are widely performed on computers, but the direct simulation of quantum systems on classical computers is very difficult because of the huge amount of memory required to store the explicit state of the system [Buluta and Nori 2009].

Continuous simulation is a numerical evaluation of a computer model of a physical dynamic system that continuously tracks system responses over time according to a set of equations typically involving differential equations. Let Q(t) and X(t) denote the system state and input trajectory vectors, respectively. Then, a linear continuous simulation is a numerical evaluation of the linear state transition function dQ(t)/dt = AQ(t) + BX(t), where A and B are coefficient matrices.

Discrete-event simulation is a computer evaluation of a discrete-event dynamic system model where the operation of the system is represented as a chronological sequence of events. In state-based modeling (see Chapter 9), the system dynamics is described by an internal state-transition function (δint: Q→Q) and an external state-transition function (δext: Q × X→Q), where Q is a set of system states and X is a set of input events. Thus, discrete-event simulation can be regarded as a computer evaluation of the internal and external transition functions.

Another type of popular computer simulation is the Monte Carlo simulation, which is not a dynamic system simulation. It is a class of computational algorithms that rely on repeated random sampling to compute the numerical integration of functions arising in engineering and science that are impossible to evaluate with direct analytical methods. In recent years, Monte Carlo simulation has also been used as a technique to understand the impact of risk and uncertainty in financial, project management, and other forecasting models.

1.4 What Is Discrete-Event Simulation?

Figure 1.5 depicts a single server system consisting of a machine and a buffer in a factory. The dynamics of the system may be described as follows: (1) a job arrives at the system with an inter-arrival time of ta, and the job is loaded on the machine if it is idle; otherwise, the job is put into the buffer; (2) the loaded job is processed for a service time of ts and unloaded; (3) when a job is unloaded, the next job is loaded if the buffer is not empty. In Fig. 1.5, the state variables of the system are q and m, where q is the number of jobs in the buffer and m denotes the status (Idle or Busy) of the machine, and the events are Arrive, Load, and Unload.

Fig. 1.5. A single server system model.

1.4.1 Description of System Dynamics

Using the state variables and events, the system dynamics of the single server system may be described more rigorously as follows: (1) when an Arrive event occurs, q is increased by one, the next Arrive event is scheduled to occur after ta time units, and a Load event is scheduled to occur immediately if m ≡ Idle(=0); (2) when a Load event occurs, q is decreased by one, m is set to Busy(=1), and an Unload event is scheduled to occur after ts time units; (3) when an Unload event occurs, m is set to Idle and a Load event is scheduled to occur immediately if q > 0. The dynamics of the single server system may be described as a graph as given in Fig. 1.6, which is called an event graph.

Fig. 1.6. Event graph describing the system dynamics of the single server system.

1.4.2 Simulation Model Trajectory

An executable model of a system is called a simulation model, and the trajectory of the state variables of the model is called the simulation model trajectory. Let {ak} and {sk} denote the sequences of inter-arrival times (ta) and service times (ts), respectively. Then, the simulation model trajectory of the single server system would look like Fig. 1.7, where {ti} are event times, X(t) is input trajectory, and Q(t) = {q(t), m(t)} denotes the trajectory of the system state variables. The “time” here means a simulation time, which is a logical time used by the simulation model to represent physical time of the target system to be simulated.

Fig. 1.7. Simulation model trajectory of the single server system.

At time t1 (=a1), a job J1 arrives at an empty system and is loaded on the idle machine to be processed for a time period of s1. In the meantime, another job J2 arrives at time t2 (=a1 + a2), which will be put into the buffer since the machine is busy. Thus, the buffer will have one job during the time period [t2, t3], which is denoted as a shaded bar in the buffer graph q(t) of Fig. 1.7. At t3 (=t1 + s1), the first job J1 is unloaded and the job J2 in the buffer is loaded on the machine. At t4 (=t3 + s2), J2 is finished and unloaded, which will make the system empty again. Thus, the machine is busy during the time period [t1, t4]. At time t5 (=a1 + a2 + a3), another job J3 arrives at the system and is loaded on the machine, and so on.

1.4.3 Collecting Statistics from the Model Trajectory

When simulating a service system, one may be interested in such items as (1) queue length, (2) waiting time distribution, (3) sojourn time, (4) server utilization, etc. In the case of the single server system, the following statistics can be collected from the model trajectory.

1. Queue length q(t) statistics during t ∈ [t0, t10]: AQL (average queue length) AQL = {(t3 − t2) + (t7 − t6) + 2(t8 − t7) + (t9 − t8) + 2(t10 − t9)}/t10

2. Waiting time {Wj} statistics for the first four jobs: AWT (average waiting time) AWT = {W1 + W2 + W3 + W4}/4 = {0 + (t3 − t2) + 0 + (t8 − t6)}/4 = (t3 − t2 + t8 − t6)/4

3. Sojourn time {Sj} statistics for the first four jobs: AST (average sojourn time) AST = AWT + Average service time = AWT + (s1 + s2 + s3 + s4)/4

4. Server utilization during t ∈ [t0, t10]: U (utilization) U = {(t4 – t1) + (t10 – t5)}/t10

1.5 What Is Continuous Simulation?

As mentioned in Section 1.3.3, continuous simulation is a numerical evaluation of a computer model of a physical system that continuously tracks system responses over time, Q(t), according to a set of equations typically involving differential equations like dQ(t)/dt = f[Q(t), X(t)], where X(t) represents controls or input trajectory.

As an example, consider a Newtonian cooling model [Hannon and Ruth 2001]. Let σ(t) be the cooling rate, then the temperature T(t) changes as dT(t)/dt = –σ(t). The cooling rate is expressed as σ(t) = κ*[T(t) – Ta], where κ is cooling constant and Ta is ambient temperature.

1.5.1 Manual Simulation of the Newtonian Cooling Model

The governing differential equation may be approximated by the following difference equation:

Let's assume T(0) = 37°C, Ta = 10°C, κ = 0.06, and Δt = 0.1, then the temperature curve T(t) may be evaluated as follows:

1.5.2 Simulation of the Newtonian Cooling Model Using a Simulator

The cooling model may be simulated by using a commercial simulator such as STELLA®, as depicted in Fig. 1.8. In STELLA®, the level of state variable is regarded as a stock and the change in state variable as flow. In Fig. 1.8, TEMPERATURE is a stock and COOLING-RATE is a flow. COOLING CONSTANT and AMBIENT TEMPERATURE are parameters. These and other data are provided to the simulator via dialog boxes.

Fig. 1.8. STELLA® block-diagram modeling and output plot of the cooling system.

1.6 What Is Monte Carlo Simulation?

Monte Carlo simulation methods are a class of computational algorithms that rely on repeated random sampling to compute their results. They were developed for performing numerical integration of functions arising in engineering and science that were difficult to evaluate with direct analytical methods. In recent years, Monte Carlo simulation has also been used as a technique to understand the impact of risk and uncertainty in financial, project management, and other forecasting models.

1.6.1 Numerical Integration via Monte Carlo Simulation

As an example of numerical integration, consider the problem of finding the value of π via simulation. I am sure you have memorized the value of π as 3.14159…: but, for the moment, assume that you do not remember the value.

In order to obtain the value of π via a Monte Carlo simulation, let's consider the circle shown in Fig. 1.9. It is a circle with a unit radius (r = 1) and its center is located at (1, 1). Uniform random variables with a range of [0, 2] are generated in pairs and are used as coordinates of points inside the square. Let n = total number of points generated (i.e., inside the square) and m = number of points inside the circle, and let Ac and As denote the areas of the circle and square, respectively. Then, the value of m/n approaches to the ratio Ac/As for a large n. Since we know that Ac = πr2 = π and As = 4, we can compute π from the following relation: m/n = Ac/As = π/4 → π = 4 m/n [Pidd 2004].

Fig. 1.9. A circle of unit radius to compute the value of π via Monte Carlo simulation.

For the reader who may be curious about the execution of the simple Monte Carlo simulation, Java codes for (1) generating uniform random numbers and (2) computing the value of π are given below.

(1) Java code for generating uniform random number U ∼ Uniform[0, 1]

double U = Math.random(); // Java function //

(2) Java code for finding the value of pi:

double m = 0, n = 0;

double max = 10000; // total number of sampling

while (n < max) {

double u1 = Math.random();

double u2 = Math.random();

double x = 2.0 * u1;

double y = 2.0 * u2;

if ( ((x - 1) * (x - 1) + (y - 1) * (y - 1)) <= 1) m++;

n++;

} // end of while

double phi = 4.0*m/n;

Exercise 1.2. Modify the above Monte Carlo simulation program (Java code) to compute the shaded area under the piece-wise linear function in Fig. 1.10.

Fig. 1.10. Area under a piece-wise linear function.

1.6.2 Risk Analysis via Monte Carlo Simulation

Consider a project consisting of three tasks1: Task1, Task2, and Task3. Estimates of the time durations for the individual tasks are given in Table 1.1. We are interested in estimating the risk (or chance) of failing to meet a given project duration, say 15 months.

TABLE 1.1. Range Estimates for Individual Tasks

It is well accepted that the duration times are assumed to follow beta distribution (see Chapter 3). In the Monte Carlo simulation, values for the task duration times are randomly generated from respective beta distributions. The results of 500 simulation runs are summarized in Table 1.2, from which one may conclude that the risk of failing to finish the project within 15 months is about 20%. In recent years, Monte Carlo methods are quite popular in financial derivatives and option pricing evaluations.

TABLE 1.2. Results of 500 Simulation Runs

1.7 What Are Simulation Experimentation and Optimization?

The rules that govern the behavior of the system are called laws, while the rules under our control are called policies. When we experiment to determine the effects of changing the parameters of laws, we are doing a sensitivity analysis. When we experiment with changes in the control factors of policies, we are doing optimization [Schruben and Schruben 2001]. Both the parameters of laws and control factors of policies become handles of simulation experimentation. Both the optimization and sensitivity analysis may be performed in a simulation study. A simulation study should be carried out with

1. clear objectives of the study together with a set of performance measures;

2. output variables that can be mapped into the performance measures;

3. well-defined handles with which the simulation runs are to be controlled.

An experimental frame is a specification of the conditions under which the simulator is experimented with [Zeigler et al. 2000], and it is concerned with simulation optimization. As shown in Fig. 1.11, an experimental frame for simulation optimization consists of five steps: (1) an initial value of each handle is generated; (2) a simulation run is made to compute values of the output variables; (3) performance measures are computed from the output variables; (4) the performance measures are evaluated to see if the results are acceptable; (5) if the results are not acceptable, go back to Step 2 with a revised set of handle values. Steps 3, 4, and 5 are often called transducer, acceptor, and generator, respectively.

Fig. 1.11. Experimental frame for simulation optimization.

1.8 Review Questions

1.1. What are the common characteristics that lead to a conceptual definition of system?

1.2. Give a definition of a team based on the concept of system.

1.3. What is the difference between a source system and a target system?

1.4. What are the three key subsystems in a feedback control system?

1.5. What is an analytic simulation?

1.6. What is time-stamp simulation?

1.7. What would be the two popular areas where virtual environment simulation is used?

1.8. What is constructive simulation?

1.9. What is the main output from a continuous simulation?

1.10. In simulation, a rule under our control is called a policy. What is a law?

1.11. What is sensitivity analysis in simulation experimentation?

1.12. What is simulation optimization?

1.13. What is the role of the acceptor in an experimental frame?

Note

1 This example was taken from www.riskamp.com.

Chapter 2

Basics of Discrete-Event System Modeling and Simulation

All models are wrong, some are useful.

—George E.P. Box

2.1 Introduction

A discrete-event system (DES) is a discrete-state and event-driven system in which the state changes depend entirely on the occurrence of discrete events over time. Examples of discrete-event systems include manufacturing systems, transportation systems such as urban traffic networks, service systems such as hospitals, and communication systems such as wireless networks, etc. This chapter aims to cover all the key subjects of and important issues in autonomous simulation of such discrete-event systems.