Transcript Overview - Department of Computer Science

Fall 2011
Part 2: Simulation Examples
CSC 446/546
Agenda
1. General guideline of simulations
2. Discrete event simulation
3. Steps to follow
4. Simulation of Queueing systems
•
•
4.1 Single Channel Queue
4.2 Queueing with Multiple Channels
Fall 2011
5. Simulation of a bombing mission
CSC 446/546
Fall 2011
1. General guideline of simulations
(1)
CSC 446/546
Fall 2011
1. General guideline of simulations
(2)
CSC 446/546
1. General guideline of simulations
(3)
•Problem formulation: Every study should begin with a statement of the
problem.
•Setting of objectives and overall project plan: The objectives indicate the
questions to be answered by simulation. A determination should be made
concerning whether simulation is the appropriate methodology for the
problem as formulated and objectives as stated.
•Model conceptualization: The construction of a model of a system is
probably as much art as science. The art of modeling is enhanced by an
ability to abstract the essential features of a problem, to select and modify
basic assumptions that characterize the system, and then to enrich and
elaborate the model until a useful approximation results
Fall 2011
•Data collection: There is a constant interplay between the construction of
the model and the collection of the needed input data
CSC 446/546
1. General guideline of simulations
(4)
•Model translation: Most real-world systems result in models that require a great
deal of information storage and computation, so the model must be entered into a
computer-recognizable format. General purpose or special purpose simulation
languages or packages to be used is determined here.
• Verified?: Verification pertains to the computer program prepared for the
simulation model. Is the computer program performing properly?
•Validated?: Validation usually is achieved through the calibration of the model, an
iterative process of comparing the model against actual system behavior and using
the discrepancies between the two, and the insights gained, to improve the model.
Fall 2011
• Experimental design: The alternatives that are to be simulated must be
determined. Often, the decision concerning which alternatives to simulate will be a
function of runs that have been completed and analyzed. For each system design
that is simulated, decisions need to be made concerning the length of the
initialization period, the length of simulation runs, and the number of replications to
be made of each run.
CSC 446/546
1. General guideline of simulations
(5)
•Production runs and analysis: Production runs, and their subsequent analysis, are
used to estimate measures of performance for the system designs that are being
simulated.
• More Runs?: Given the analysis of runs that have been completed, the analyst
determines whether additional runs are needed and what design those additional
experiments should follow.
• Documentation and reporting: There are two types of documentation: program
and progress.
Fall 2011
•Program documentation is necessary for numerous reasons. If the program is
going to be used again by the same or different analysts, it could be necessary
to understand how the program operates and what parameters used.
•The result of all the analysis should be reported clearly and concisely in a final
report. This will enable the model users (now, the decision makers) to review
the final formulation, the alternative systems that were addressed, the criterion
by which the alternatives were compared, the results of the experiments, and
the recommended solution to the problem
CSC 446/546
2. Discrete event simulation
1. This course is about Discrete Event Simulations.
Therefore, the models considered are discrete,
dynamic, and stochastic
2. Discrete-event systems simulation is the modeling of
systems in which the state variable changes only at a
discrete set of points in time
Fall 2011
3. The simulation models are analyzed by numerical
methods rather than by analytical methods
CSC 446/546
3. Steps to follow (1)
Determine the characteristics of each of the inputs to the
simulation. Quite often, these are modeled as probability
distributions, either continuous or discrete.
Construct a simulation table. Each simulation table is different, for
each is developed for the problem at hand.
Each column in the table is one of the following:
Fall 2011
•
•
•
•
•
•
CSC 446/546
An activity time associated with model input
Any other random variable defined by a model input
A system state
An event, or the clock tie of an event
A model output
A model response
3. Steps to follow (2)
A Generic simulation Table:
• Let there are p inputs, xij, j = 1,2,... ,p, and one response, Yi, for
each of repetitions (or, trials) i = 1,2, . . . , n.
• Initialize the table by filling in the data for repetition 1
• 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.
Step
Activities and system states
Output
xi1 xi2 xi3 … xij… .xip
yi
Fall 2011
1
CSC 446/546
n
9
4. Simulation of Queueing Systems
(1)
A queueing system is described :
Fall 2011
• by its calling population, the nature of arrivals, the service
mechanism, the system capacity and the queue and any
priorities within the queue or service
CSC 446/546
10
4. 1 Single Channel (Server)
Queue (1)
In the single-channel queue, the calling population is infinite; that is, if a
unit leaves the calling population and joins the waiting line or enters
service, there is no change in the arrival rate of other units that could need
service.
Arrivals for service occur one at a time in a random fashion; once they join
the waiting line, they are eventually served.
In addition, service times are of some random length according to a
probability distribution which does not change over time.
The system capacity has no limit, meaning that any number of units can
wait in line
Finally, units are served in the order of their arrival (often called FIFO:
first in, first out) by a single server or channel.
Arrivals and services are defined by the distribution of the time between
arrivals and the distribution of service times, respectively.
Fall 2011
For any simple single or multi-channel queue, the overall effective arrival
rate must be less than the total service rate, or the waiting line will grow
without bound.
When queues grow without bound, they are termed "explosive" or unstable.
CSC 446/546
11
4.1 Single Server Queue (2)
Prior to our introducing several simulations of queueing systems, it is
necessary to understand the concepts of system state, events, and
simulation clock.
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 can affect the state of the system.
• The entry of a unit into the system (the arrival event)
• The completion of service on a unit (the departure event).
The queueing system includes the server, the unit being serviced (if one is
being serviced), and the units in the queue (if any are waiting).
Fall 2011
The simulation clock is used to track simulated time
CSC 446/546
12
4.1 Single Channel Queue (3) –
Departure Event
If a unit has just completed service, the simulation proceeds in the
manner shown in this flow diagram
Fall 2011
Server has only two possible
states: It is either busy or idle.
CSC 446/546
13
4.1 Single Channel Queue (4) –
Arrival Event
Fall 2011
The arrival event occurs when a unit enters the system. The flow
diagram for the arrival event is shown below.
CSC 446/546
14
4.1 Single Channel Queue (5)Unit Status
Arrival Event
Fall 2011
Departure Event
CSC 446/546
15
4.1 Single Channel Queue (6)Simulated Clock
How can the events described above occur in simulated time?
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.
Simulations using event lists are described in Chapter 3.
Here the simulation is simplified by tracking each unit explicitly.
In simulation, events usually occur at random times, the
randomness imitating uncertainty in real life
The randomness needed to imitate real life is made possible
through the use of “Random Numbers”
Fall 2011
Random numbers are distributed uniformly and independently on
the interval (0, 1)
CSC 446/546
16
4.1 Single Channel Queue (7) Random Numbers
Random numbers also can be generated in simulation
packages and in spreadsheets (such as Excel).
For example, Excel has a macro function called RAND()
that returns a "random" number between 0 and 1.
When numbers are generated by using a procedure, they
are often referred to as pseudo-random numbers
• Because the procedure is fully known, it is always
possible to predict the sequence of numbers that will be
generated prior to the simulation
Fall 2011
We will discuss random number generation later
CSC 446/546
17
4.1 Single Channel Queue (8) –
Interarrival Times
In a single-channel queueing simulation, interarrival times and service times are
generated from the distributions of these random variables.
Fall 2011
For simplicity, assume that the times between arrivals were generated by rolling a
die five times and recording the up face. Table below contains a set of five
interarrival times generated in this manner.
CSC 446/546
18
4.1 Single Channel Queue (9)Interarrival Times (continued ..)
These five interarrival times are used to compute the
arrival times of six customers at the queueing system.
The first customer is assumed to arrive at clock time 0.
This starts the clock in operation.
The second customer arrives two time units later, at
clock time 2.
Fall 2011
The third customer arrives four time units later, at clock
time 6; and so on
CSC 446/546
19
4.1 Single Channel Queue (10) –
Service Times
The second time of interest is the service time.
Table below contains service times generated at random from a
distribution of service times.
The only possible service times are one, two, three, and four time units, all
four values are equally likely to occur
Fall 2011
These random numbers are
generated by placing the
numbers one through four on
chips and drawing the chips
from a hat with replacement,
being sure to record the
numbers selected
CSC 446/546
20
4.1 Single Channel Queue (11) –
Simulation Table
Now, the interarrival times and service times must be meshed to simulate
the single-channel queueing system
Fall 2011
Table 2.7 was designed specifically for a single-channel queue that serves
customers on a first-in-first-out (FIFO) basis
CSC 446/546
21
4.1 Single Channel Queue (12)Chronological Ordering of Events
Fall 2011
The following table is ordered by clock time, in which case the events may
or may not be ordered by customer number. The chronological ordering of
events is the basis of the approach to discrete-event simulation
CSC 446/546
22
Fall 2011
4.1 Single Channel Queue (13) Number of Customers in the System
CSC 446/546
23
4.1 Single Channel Queue (14) Grocery Store Example (1)
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.9
The service times vary from 1 to 6 minutes, with the probabilities shown in Table
2.10
Simulate up to 100 customers (too small a data for good analysis)
Fall 2011
Average Service time = s.p(s) = 3.2 minutes
Average Interval Arrival Time = (1+8)/2 = 4.5 minutes
CSC 446/546
24
Fall 2011
4.1 Single Channel Queue (14) Grocery Store Example (2)
CSC 446/546
25
Fall 2011
4.1 Single Channel Queue (14) Grocery Store Example (3)
CSC 446/546
26
4.1 Single Channel Queue (14) Grocery Store Example (4)
Averagewaiting time
P robability (wait) 
totaltimecustomerswait in queue (minutes) 174

 1.74
totalnumbersof customers
100
number of customerswho wait 54

 0.54
totalnumbersof customers
100
P robability of Idle Server 
AverageService T ime
T otalidle timeof server
101

 0.24
totalrun timeof simulat ion 418
T otalService T ime
317

 3.17
T otalNumber of customers 100
AverageT imebetween arrivals
sum of all timesbetween arrivals 415

 4.19
number of arrivals- 1
99
Averagewaiting timeof thosewho wait 
totaltimecustomerswait in queue 174

 3.22
totalnumber of customersthat wait 54
Fall 2011
Averagetimecustomerspends in thesystem
totaltimecustomersspend in thesystem 491

 4.91
totalnumber of customers
100
Or
Averagetimecustomerspends in thesystem average waiting timeaverageservice time 1.74 3.17  4.91minutes
CSC 446/546
27
4.1 Single Channel Queue (14) Grocery Store Example (6)
Fall 2011
Waiting time in queue for the first trial of 100 customers is shown below
CSC 446/546
28
4.1 Single Channel Queue (14) Grocery Store Example (6)
Average waiting time over 50 trials is = 1.5
Fall 2011
Histogram of 50 average waiting times over 50 trials is shown below
CSC 446/546
29
4.2 Queuing with Multiple Servers (1):
Able-Baker Call Center Problem
Two Service Channels (or Servers)
A computer technical support center where personnel take calls and
provide service. The time between calls ranges from 1 to 4 minutes,
with distribution as shown in Table 2.12 of the textbook.
There are two technical support people-Able and Baker. Able is more
experienced and can provide service faster than Baker.
The distributions of their service times are shown in Tables 2.13 and 2.14
Policy: A simplifying rule is that Able gets the call if both technical
support people are idle. Able has seniority.
The solution would be different if the decision were made at random or by
any other rule
Fall 2011
How well this policy is working??
CSC 446/546
30
4.2 Queuing with Multiple Servers (2):
Distributions
Average=2.25
Average=3.29
Fall 2011
Average=4.25
CSC 446/546
31
4.2 Queuing with Multiple Servers (3):
Simulation Steps
Step 1:
Fall 2011
• For Caller k, generate an interarrival time Ak. Add it to the
previous arrival time Tk-1 to get the arrival time of Caller k
as Tk = Tk-1+Ak.
CSC 446/546
32
4.2 Queuing with Multiple Servers (3):
Simulation Steps
Fall 2011
Step 2:
• If Able is idle, Caller k begins service with Able at the current time Tnow.
• Able's service completion time, Tfin.A is given by Tfin.A = Tnow + Tsvc.A
where Tsvc.A is the service time generated from Able's Service Time
Distribution.
• Caller k's time in system, Tsys, is given by Tsys = Tfin.A - Tk.
• Because Able was idle, Caller k's delay, Twait, is given by Twait = 0
• If Able is busy, but Baker is idle, Caller k begins service with Baker at
the current time Tnow.
• Baker's service completion time, Tfin.B is given by Tfin.B = Tnow + Tsvc.B
where Tsvc.B is the service time generated from Baker's Service Time
Distribution.
• Caller k's time in system, Tsys, is given by Tsys = Tfin.B - Tk.
• Because Baker was idle, Caller k's delay, Twait, is given by Twait = 0
CSC 446/546
33
4.2 Queuing with Multiple Servers (3):
Simulation Steps
Step 3:
• If Able and Baker are both busy, then calculate the time at
which the first one becomes available, as follows: Tbeg =
min(Tfin.A, Tfin.B).
• Caller k begins service at Tbeg. When service for Caller k
begins, set Tnow = Tbeg.
• Then compute Tfin.A or Tfin.B as in Step 2.
Fall 2011
• Caller k's time in system, Tsys, is given by Tsys = Tfin.A - Tk
or Tsys = Tfin,B - Tk, as appropriate.
CSC 446/546
34
4.2 Queuing with Multiple Servers (4):
Simulation Table
Total Customer Delay = 211 or about 2.11 minutes per caller
Fall 2011
Total time in system = 564 or 5.64 minutes per caller
CSC 446/546
35
4.2 Queuing with Multiple Servers (5):
Caller Delay
Fall 2011
One trail with 100 callers
CSC 446/546
36
4.2 Queuing with Multiple Servers (5):
Average Caller Delay
Experiment with 400 trials each with 100 callers
19% average delays are longer than 1 minute (78 of 400)
Fall 2011
only 2.75% (11 of 400) are longer than 2 minutes
CSC 446/546
37
4.2 Queuing with Multiple Servers (6):
Further Investigation
What happens if the policy is changed?
Is it cost effective to add another server?
Fall 2011
Can one server handle all calls in this example?
CSC 446/546
38
5. Simulation of a Bombing
Mission (1)
A bomber attempting to destroy an ammunition depot, as shown in
Figure. (This bomber has conventional rather than laser-guided
weapons). The bomber flies in the horizontal direction and
carries 10 bombs. The aiming point is (0,0).
Fall 2011
If a bomb falls anywhere on the target, a hit is scored; otherwise,
the bomb is a miss.
CSC 446/546
39
5. Simulation of a Bombing
Mission (2)
The point of impact is assumed to be normally distributed around the
aiming point with a standard deviation of 400 meters in the direction of
flight and 200 meters in the perpendicular direction
The problem is to simulate the operation and make statements about the
number of bombs on target.
Recall that the standardized normal variate, Z, having mean 0 and
standard deviation 1 is distributed as Z=(X-)/ , where X is a normal
random variable,  is the mean of distribution X and  is the standard
deviation of X
Then X=ZX and Y=ZY where (X,Y) are the simulated co-ordinates of the
bomb after it has fallen (What is the Mean???)
With X=400 and Y=200 we have X=400.Zi and Y=200.Zj
The i and j subscripts have been added to indicate that the values of Z
should be different. (Why???)
Fall 2011
We will see later how to generate Normal Random Variables
CSC 446/546
40
5. Simulation of a Bombing
Mission (3)
Fall 2011
RNNx (RNNY) stands for "random normal number to
compute the X (Y) coordinate" and corresponds to Zi (Zj)
CSC 446/546
41
5. Simulation of a Bombing
Mission (4)
An experiment was run with 400 trials (each trial 10 bombs)
The results range from two hits to ten hits. Average is 6.72 hits
Fall 2011
44% [(175/400) x 100%] of the bombing runs there are six or fewer hits. In about 71
% of the cases, [(283/400) x 100%] there were six, seven, or eight hits
CSC 446/546
42