CSC401 Simulation Techniques
Exam 1 is scheduled to be given on Wednesday, October 13, 2010
This exam will cover Chapters 1 – 6 of the text book.
It will be designed as a 1.25 hour in-class exam with a take-home component.. You will be allowed to take up to the full 100 minutes of the period.
I will post the take-home portion Wednesday, October 6, on blackboard. This part will be to complete a simulation.
You will be allowed to bring two pages of notes to the in-class portion of the exam.
Everything you should know for the exam:
Please check the assessment paper – all topics will eventually be covered and questions will appear on the midterm or final.
Chapter 1 Introduction to Simulation
All of first chapter should be studied for the exam.
The material has good topics for exam questions: the what and how of simulation from an overall standpoint.
A simulation is the imitation of the operation of a real-world process or system
over time.
Simulation involves the generation of an artificial history of a system and the
observation of that artificial history to draw inferences concerning the operating characteristics of the real system.
Develop a system model
Set of assumptions concerning the operation of the system.
Mathematical, logical, symbolic relationships between the entities
(objects of interest) of the system.
Validated system can be used to investigate what-if questions about the
real-world system such as
Analysis tool to predict the effect of system changes on performance
Design tool to predict the performance of new systems
Sometimes a model can be done analytically via mathematical techniques.
Many systems are too complex for mathematical solutions and require
computer-based simulation.
1.1When simulation is the appropriate tool.
Study and experimentation of internal interactions of a complex system
Informational, organizational, environmental changes can simulated and
there effect on the model’s behavior observed.
Knowledge gained during design of simulation model is valuable.
Verify analytic solutions.
Simulation models for training.
Animation facilitates visualization.
1.2 When simulation is not appropriate
1. and 2. Problem can be solved easily analytically or by common sense.
3. Don’t use if easier to perform direct experiments
4. Don’t use if costs exceed savings.
5. and 6. Don’t use simulation if resources or time are not available.
7. If no data is available, not even estimates, simulation is not advised.
8. Don’t use if not enough time or personnel to validate model.
9. Simulation tough if managers have unreasonable expectations
10. If system behavior too complex or undefined, simulation not appropriate.
(Human behavior)
1.3 Advantages and disadvantages or simulation
Simulation mimics what happens in real life.
Simulation model does not need to make dubious assumptions.
Output from model directly correspond to outputs from real system.
1.4 Areas of application
Simulation for risk analysis is growing: options pricing and insurance.
Simulation of large-scale systems, such as the internet backbone and wireless networks, are growing as hardware and software increase their capability to handle large numbers of entities in a reasonable time.
Simulation models of automated material handling systems
1.5 Systems and system environment
A system is defined as a group of objects that are joined together in some regular interaction or interdependence toward accomplishment of some purpose.
A system is often affected by changes occurring outside the system.
Such changes are said to occur in the system environment.
In modeling systems, it is necessary to decide on the boundary between the system and its environment.
This decision may depend on the purpose of the study.
Setting of interest rate may be a constraint or may be an activity of the system.
1.6 Components of a system
Entity – object of interest in the system
Attribute – property of an entity
Activity – represents a time period of specified length
Collection of entities that compose a system for one study may be only a subset of the overall system
State of a system – that collection of variables necessary to describe the system at any time, relative to the objectives of the study
Event – an instantaneous occurrence that might change the state of the system.
Endogenous – activities and events occurring within a system
Exogenous – activities and events in the environment that affect the system.
1.7 Discrete and continuous systems
Although few systems are wholly discrete or continuous, usually one type of change usually predominates for most systems
A discrete system is one in which the sate variables change only at discrete set of points in time.
A continuous system is one in which the state variables change continuously over time.
1.8 Model of a system
A model is defined as a representation of a system for the purpose of studying the system.
Usually only need those aspects of the system that affect the problem under investigation.
Chapter 3
1.9 Types of models
Models can be classified as being mathematical or physical
Mathematical models use symbolic notation and mathematical equations to represent a system
A simulation model is a particular type of mathematical model
A static simulation model, some time called a Monte Carlo simulation, represents a particular point in time.
Dynamic simulation models represent systems as they change over time.
Simulation models that contain no random variables are classified as deterministic.
Have a known set of inputs which will result in a unique set of outputs
A stochastic simulation model has one or more random variables as inputs.
Random inputs lead to random outputs.
Since outputs are random, they can be considered only as estimates of the true characteristics of a model
In a stochastic simulation, the output measures must be treated as statistical estimates of the true characteristics of the system.
Discrete models can be used to model a continuous system.
Models in text are discrete, dynamic, and stochastic
1.10 Discrete-event systems simulation
Discrete –event systems simulation is the modeling of systems in which the state variables changes only at a discrete set of points in time
The simulation models are analyzed by numerical methods rather than by analytical methods
Analytical methods employ the deductive reasoning of mathematics to “solve” the model.
Numerical methods employ computational procedures to “solve” mathematical models.
Simulation models which employ numerical models are run rather than solved.
Artificial history of the system generated from model assumptions and observations are collected to be analyzed and to estimate the true system performance measures.
Large amount of data usually requires the aid of a computer
1.11 Steps in a simulation study
Problem formulation
Setting of objectives and overall project plan
Model conceptualization
Art and science
Data collection
Interplay between construction of the model and collection of needed data
Model translation
Program the model
Verified?
Verify the computer program prepared for the simulation model to insure it performs properly
Validated?
Validation usually is achieved through calibration of the model
Experimental design
The alternatives that are to be simulated must be determined.
Production runs and analysis
Production runs, and their subsequent analysis, are used to estimate measures of performance for system designs that are being simulated.
More runs?
Given the analysis of runs that have been completed, additional runs may be needed and may require a different experimental design.
Documentation and reporting
Program documentation
Progress documentation important to keep project on course
Implementation
Depends on how well previous steps have been performed
Model and underlying assumptions properly communicated important
Phase 1: problem formulation, and setting of objectives and overall design
Phase 2: model conceptualization, data collection, model translation, verification, and validation
Phase 3: running the model, experimental design, production runs and analysis, additional runs
Phase 4: documentation and reporting, and implementation
Problems:
Page 22 +
1, 2, 3, 4, 11
Chapter 2 Simulation Examples
This chapter should also be looked at as prime exam material.
We looked carefully at both the grocery store and the call center. You should be able to handle either in a spreadsheet.
What is meant by “manually” in the following?
This chapter presents several examples of simulation that can be performed by devising a simulation table either manually or with a spreadsheet.
The simulation table provides a systematic method for tracking system state over time.
Methodology of discrete-system simulation
1. Determine the characteristics of each of the inputs to the simulation.
These are often modeled as probability distributions, either continuous or discrete.
2. Construct a simulation table.
Each simulation table is different, for each is developed for the problem at hand.
For each repetition or trial there are a set of inputs and one response.
3. For each repetition i, generate a value for each of the p inputs, and evaluate the function, calculating a value of the response yi.
The input values may be computed by sampling values from the distributions chosen in step 1.
A response typically depends on the inputs and one or more previous responses.
The inventory example has a closed-form (mathematical) solution to compare to the simulation solution. This is an important concept.
Note that I skipped over the inventory section (Section 2.2).
2.1 Simulation of queuing systems
A queueing system is described by
its calling population,
the nature of the arrivals,
the service mechanism,
the system capacity, and
the queueing discipline.
A simple single-channel queueing system is shown in figure 2.1.
Queueing systems require the concepts of system state, events, and simulation clock (Chapter 3).
The state of the system is the number of units in the system and the status of the server, busy or idle.
An event is a set of circumstances that causes an instantaneous change in the state of the system.
In a single-channel queueing system there are only two possible events that affect the state of the system: arrival event and the departure event.
The queueing system includes the server, the unit being serviced ( if there is one), and the units in the queue (if any).
The simulation clock is used to track simulated time.
If a unit has just competed service, the simulation proceeds in the manner shown in the flow diagram of figure 2.2
The arrival even occurs when a unit enters the system. figure 2.3
If the server is busy, the unit enters the queue.
If the server is not busy, the unit begins service.
After the completion of the service, the server will either become idle or will remain busy with the next unit.
Simulations of queueing systems generally require the maintenance of an event list for determining what happens next.
The event list tracks the future times at which the different types of events occur.
This chapter simplifies the simulation by tracking each unit explicitly.
Simulation clock times for arrivals and departures are computed in a simulation table customized for each problem.
In simulation, events usually occur at random times, the randomness imitating uncertainty in real life.
Why are random numbers needed? What is the difference between random digits and random numbers? Pseudo-random numbers?
In a single-channel queueing simulation, interarrival times and service times are generated from the distributions of these random variables.
For simplicity, assume that the times between arrivals were generated by rolling a die five times and recording the up face.
The second time of interest is the service time. Service times generated at random from a distribution of service times.
Now, the interarrival times and service times must be meshed to simulate the single-channel queueing system.
Example 2.1 Single-Channel Queue One of our favorites
A small grocery store has only one checkout counter.
Customers arrive at this checkout counter at random times that are from 1 to 8 minutes apart.
Each possible value of interarrival time has the same probability of occurrence, as shown in Table 2.6.
The service times vary from 1 to 6 minutes, with the probabilities shown in Table 2.7.
The problem is to analyze the system by simulating the arrival and service of 100 customers.
Compare the findings that follow from the simulation to what you might find using Little’s law.
1. The average waiting time for a customer
= total time customers wait / total number of customers
= 174 minutes / 100 customers
= 1.74 minutes / customer
2. The probability that a customer has to wait in the queue
= number of customers who wait / total number of customers
= 46 / 100
= .46
3. The proportion of the time the server is idle
= total time the server is idle / total time of the simulation
= 101 / 418
= .24
so the probability that the server is busy is 1 - .24 = .76
This means the server is utilized 76% of the time.
4. The average service time is
= total service time in minutes / total number of customers
= 317 minutes / 100
= 3.17
This result can be compared with the expected service time by finding the mean of the service–time distribution
This is the sum of the service time s times the probability of the service time. s and p(s) are from table 2.7.
This yields 3.2. If the simulation is run longer the average and expected value will get closer together.
5. The average time between arrivals
= sum of all times between arrivals in minutes / number of arrivals – 1
= 415 minutes / 99
= 4.19 minutes
nothing before 1 or after 100
6. The average waiting time of those who wait
= total time customers wait in queue / total number of customers that wait
= 174 minutes / 54
= 3.22 minutes
7. The average time a customer spends in the system
= total time customers spend in the system / total number of customers
= 491 minutes / 100
= 4.91 minutes
also
= average time customer spends waiting in the queue +
average time customer spends in service
= 1.74 minutes + 3.17 minutes
= 4.91 minutes
In Section 2.3 we worried about the reliability problem.
Came back to reliability in Chapter 5.
We did do a problem from section 2.3 about the project simulation on page 54+
We also spent some time in this secion thinking about random digits, random numbers and their applicability
Problems Page 83: # 21 - 27, 44 - 47
One of the spreadsheet problems will be part of the take-home.
Chapter 3 General Principles
Most of Chapter 3 should be studied in detail for the exam
Everything in the Introduction and Section 3.1 is important
Section 3.1
An activity typically represents a service time, an interarrival time, or any other processing time whose duration has been characterized and defined by the modeler.
An activity’s duration may be specified in a number of ways:
1. Deterministic—for example, always exactly 5 minutes;
2. Statistical—for example, as a random draw from among 2, 5, 7 with equal probabilities;
3. A function depending on system variables and/or entity attributes
The duration of an activity is computable from its specification at the instant it begins.
Its duration is not affected by the occurrence of other events (unless, as is allowed by some simulation packages, the model contains logic to cancel an event).