CSci 405: Computer Simulation
Spring Semester 2000
Lecture Notes

Introduction to Modeling and Simulation

These notes are based, in part, on material from:

Chapter 1 of the book Practical Process Simulation: Using Object-Oriented Techniques and C++ by Jose' M. Garrido (Artech House, 1999)
Chapter 1 of the book Discrete Event System Simulation, Second Edition by Jerry Banks, John S. Carson II, and Barry L. Nelson (Prentice Hall, 1996).
The Preface of book How to Model It: Problem Solving for the Computer Age Anthony M. Starfield, Karl A. Smith, and Andrew L. Bleloch (McGraw Hill, 1990).

Systems and Models

System:: a set of entities that interact in a cohesive manner to accomplish a specific goal
Model:: a representation of a real system that is equivalent to the real system in all relevant aspects
-- an abstract representation of a system

We build models all the time.

Often our models are implicit, constructed without us thinking about the process.

Sometimes our models are explicit, consciously constructed and expressed so that we can communicate them to others. This is the type of model we deal with in this class.

The purpose of a model must be identified to decide what are the "relevant aspects" of the real system.

The process of deciding what is "relevant" to model and what is not relevant is called abstraction.

Abstraction:

concentrating on essentials and ignoring the details.

 ______________                      ______________
|              |    Abstraction     |              | 
|    System    |------------------->|    Model     | 
|______________|                    |______________|

Modeling:

the intellectual task of developing a model of a system

System Behavior

Environment:

the domain not included in a system.

The boundary between a system and its environment must be clearly and precisely defined.

The system behavior is a response to one or more of the following events:

the passage of time
the occurrence of events in the environment
the inflow of data from the environment.

A model must exhibit behavior at its boundary that is equivalent to the behavior of the real system at its boundary.

Types of Models

Physical models:

a scale model of relevant physical properties of the real system

Advantage:: tangible, visual
Disadvantages:

quite specific to individual system types
difficult and expensive to change once built
normally representative of static structure, not dynamic behaviors

Graphic models:

graphical diagrams to describe the high-level structure and behaviors of a system

Mathematical models:

a set of mathematical or logical expressions to express the relationships among the entities in the system.

These tend to be the most flexible and powerful of the types.

We deal with explicit mathematical models that can be implemented as software on a computer.

System Components -- Terminology

entity:

a major component of interest in the system (typically an active component)

In a bus system, riders and buses are entities.

resources:

a minor component of the system (typically a passive component)

In a bus system, the seats on the buses are resources.

attribute:

a property of or value associated with an entity

In a bus system, the origination and destination points of each rider are attributes.

activity:

a unit of work that an entity carries out for a finite period of time

In a bus system, the movement of a rider to or from a bus might be an activity

operation:

a sequence of activities

In a bus system, the loading and unloading of riders at a particular bus stop might be an operation

state of a system:

the collection of attribute values sufficient to describe the system at some instant in time, with respect to behaviors of interest

In a bus system, the position, capacity, occupancy, route, and schedule of each bus and each bus stop/station and the origination and destination of each rider might describe the state of a bus system.

state variables:

in a mathematical model, the set of attribute variables that capture the state

Components of a Simple Barbershop System

The entities are the customers and the barbers.
The resources are the barber chairs and the spaces available for waiting.
The attributes of the customer entities include arrival time for that customer, the type of haircut desired, the amount of hair.
The operations include "wait until a barber is available", "cut customer's hair", and "clean chair and wait for next customer".
The system state can be described by:
- number of barbers available
- number of barber chairs available
- size of the waiting area (i.e., the arrival queue)
- time the current customers began their haircuts.
- total number of customers since the shop opened today
- total waiting time for barbers since the shop opened today
Note that state change only occurs at specific instants of time.

Continuous and Discrete Models

continuous models:

change the state continuously with time.

The state variables are continuous functions of time.

For example, a mathematical model of a physical object falling toward earth would give the position of the object as a function of time.

    height = -g * time**2 + initial_velocity * time + initial_height

where g is the acceleration of gravity constant.

discrete event models:

change the state at discrete points in time.

The example, the model of the barbershop is a discrete-event model. It changes state when a customer arrives or departs.

event:

an instantaneous occurrence that affects the state of the system.

In the barbershop model, the events of interest include:

The arrival of a customer
The starting of a haircut for a customer
A customer leaving the barberhop after receiving a haircut
A customer leaving the barbershop if it is full or service is too slow
A barber begins to wait/clean when there are no customer awaiting service.

This course will focus on discrete event models. Such models can be "solved" using discrete event simulation techniques.

Deterministic and Stochastic Models

stochastic model of a system:

at least one state variable has some uncertainty in its change of values.

The values are not completely predictable, but take values according to some probability distribution.

The model of the barbershop is, in general, stochastic. The arrival of customers is governed by some probability distribution, such as the exponential distribution.

deterministic model of a system:

every state variable's value is governed by a mathematical function, and is thus entirely predictable

The model of a free-falling object is deterministic. The vertical position is completed described as a function of time.

Formal Models and Their Solutions

formal mathematical model:: a mathematical model in which all variable relationships, entity interactions. and dynamic behavior are specified within the mathematical formalisms used.

Usually formulated as a set of equations -- e.g., set of linear equations, differential equations continuous in time, difference equations for discrete systems

Types of solutions:

analytic solution:

derivation of an expression that can be calculated to give the exact values for the state variables and outputs of interest.

Most models of dynamic systems are too complex to solve with current mathematical techniques.

numeric solution:

approximation of the numerical values of the state and output variables for some specific range of the time variable.

Numerical techniques are appropriate where there are no known analytical solutions or where it is impractical to solve the system of equations.

Simulation Models

simulation model:

a mathematical model implemented on a computer in order to run experiments.

The simulation model is usually implemented as a program in some programming language.

simulation:

the task of running experiments with a mathematical model using numeric techniques to imitate the behavior of a system over a period of time.

An execution of a simulation program with a given set of parameters is a simulation run.

Once built, experiments can be carried out with the simulation model instead of the real system.

Using Simulation to Solve Problems

We can use simulation modeling:

as an analysis technique to predict the behavior an existing system in some specific situation.
We can gain insight about how an existing complex system actually operates (perhaps in contrast to how we might "think" it operates):
- how the variables interact
- which variables are important for system performance
- where the performance bottlenecks are
as a design technique to study the expected behaviors of a proposed system that has not yet been constructed.
We can address "what if" questions about systems safely and inexpensively. For example, we can:
- study new operating policies without upsetting ongoing operations.
- investigate new designs without committing the resources to build the systems.

Advantages of Simulation

A simulation model can be used repeatedly to analyze proposed designs or changes in operating policies.
Simulation is usually less costly and safer than carrying out experiments and gathering data from real systems.
Simulation models are often easier to apply than analytic techniques.
Simulation models do not have the restrictive assumptions that analytic methods often do. Almost any performance measure can be estimated.
In some cases, simulation is the only method that can be used to reach a solution to the problem..

Disadvantages of Simulation

Model building is not an exact science; it is an art for which it takes considerable and experience time to acquire the necessary skill.
Simulation results may be difficult to interpret.
Simulation modeling and analysis can still be time consuming and expensive.
Sometimes simulation is used where better techniques exist. Where feasible, analytic solutions are preferable because they give more precise and general results.

Note that most of these disadvantages can be overcome with education and experience.

Stages in the Model Development Process

Definition of the problem.
What is the purpose of the model? the questions to be answered? the relevant performance measures?
Specification of the model.
Create a clear, precise, complete, concise, and understandable description of what is to be accomplished.
Give a listing of the relevant components, the relationships and interactions among the components, and the overall dynamic behavior of the model.
Model design.
Give the details of the algorithms and data structures to capture the needed relationships and dynamic behaviors.
Data collection.
Collect the data needed to validate the model and to answer the questions.
Implementation of the model.
Choose an implementation "language" and do the detailed design, coding, and testing.
Verification of the model.
Debug the model. Compare the outputs of runs of the model to what what is expected.
Validation of the model.
Compare the model with reality. That is compare the outputs of the simulation model with outputs of the real system.

UP to CSCI 405 Lecture Notes root document?

CSci 405: Computer Simulation Spring Semester 2000 Lecture Notes