Transcript Simulating single server

Simulating Single server
queuing models
Simulating Single server
queuing models
• Consider the following sequence of
activities that each customer undergoes:
1. Customer arrives
2. Customer waits for service if the server is
busy.
3. Customer receives service.
4. Customer departs the system.
Analytical Solutions
• Analytical solutions for W, L, Wq, Lq exist
However, analytical solution exist at infinity
which cannot be reached.
• Therefore, Simulation is a most.
Flowchart of an arrival event
An Arrival
Idle
Busy
Status of
Server
Customer enters service
Customer joins queue
More
Flowchart of a Departure event
A Departure
NO
Queue
Empty ?
Remove customer from
Queue and begin service
Yes
Set system status to
idle
More
An example of a hand
simulation
• Consider the following IAT’s and ST’s:
• A1=0.4, A2=1.2, A3=0.5, A4=1.7, A5=0.2,
A6=1.6, A7=0.2, A8=1.4, A9=1.9, …
• S1=2.0, S2=0.7, S3=0.2, S4=1.1, S5=3.7,
S6=0.6
• Want: Average delay in queue
• Utilization
Initialization
Time = 0
System state
A 0.4
Clock
D 999
.
Eventlist
0
Server
status
# in
que
system
Times
of
Arrival
Time
0
0
Of
Last Number Total
event delayed delay
Area
Under
Q(t)
Statistical Counters
Area
Under
B(t)
Arrival
Time = 0.4
System state
A 1.6
Clock
0.4
system
D 2.4
Eventlist
Server
status
# in
que
Times
of
Arrival
Time
Of
Last Number Total
event delayed delay
Area
Under
Q(t)
Statistical Counters
Area
Under
B(t)
A1=0.4, A2=1.2, A3=0.5, A4=1.7, A5=0.2, A6=1.6, A7=0.2, A8=1.4
S1=2.0, S2=0.7, S3=0.2, S4=1.1, S5=3.7, S6=0.6
Arrival
Time = 1.6
System state
A 2.1
1.6
Clock
0.4
D 2.4
Eventlist
1.6
system
Server
status
# in
que
Times
of
Arrival
Time
Of
Last Number Total
event delayed delay
Area
Under
Q(t)
Statistical Counters
Area
Under
B(t)
A1=0.4, A2=1.2, A3=0.5, A4=1.7, A5=0.2, A6=1.6, A7=0.2, A8=1.4
S1=2.0, S2=0.7, S3=0.2, S4=1.1, S5=3.7, S6=0.6
Arrival
Time = 2.1
System state
A 3.8
1.6
2.1
0.4
Clock
D 2.4
Eventlist
1.6
2.1
System
Server
status
# in
que
Times
of
Arrival
Time
Of
Last Number Total
event delayed delay
Area
Under
Q(t)
Statistical Counters
Area
Under
B(t)
A1=0.4, A2=1.2, A3=0.5, A4=1.7, A5=0.2, A6=1.6, A7=0.2, A8=1.4
S1=2.0, S2=0.7, S3=0.2, S4=1.1, S5=3.7, S6=0.6
Departure
Time = 2.4
System state
A 3.8
2.1
Clock
1.6
D 3.1
Eventlist
2.1
System
Server
status
# in
que
Times
of
Arrival
Time
Of
Last Number Total
event delayed delay
Area
Under
Q(t)
Statistical Counters
Area
Under
B(t)
A1=0.4, A2=1.2, A3=0.5, A4=1.7, A5=0.2, A6=1.6, A7=0.2, A8=1.4
S1=2.0, S2=0.7, S3=0.2, S4=1.1, S5=3.7, S6=0.6
Departure
Time = 3.1
System state
A 3.8
Clock
2.1
D 3.3
Eventlist
Server
status
System
# in
que
Times
of
Arrival
Time
Of
Last Number Total
event delayed delay
Area
Under
Q(t)
Statistical Counters
Area
Under
B(t)
A1=0.4, A2=1.2, A3=0.5, A4=1.7, A5=0.2, A6=1.6, A7=0.2, A8=1.4
S1=2.0, S2=0.7, S3=0.2, S4=1.1, S5=3.7, S6=0.6
Departure
Time = 3.1
System state
A 3.8
Clock
D 999
.
Eventlist
Server
status
System
# in
que
Times
of
Arrival
Time
Of
Last Number Total
event delayed delay
Area
Under
Q(t)
Statistical Counters
Area
Under
B(t)
A1=0.4, A2=1.2, A3=0.5, A4=1.7, A5=0.2, A6=1.6, A7=0.2, A8=1.4
S1=2.0, S2=0.7, S3=0.2, S4=1.1, S5=3.7, S6=0.6
Departure
Time = 3.1
System state
A 4.0
Clock
3.8
D 4.9
Eventlist
Server
status
System
# in
que
Times
of
Arrival
Time
Of
Last Number Total
event delayed delay
Area
Under
Q(t)
Statistical Counters
Area
Under
B(t)
A1=0.4, A2=1.2, A3=0.5, A4=1.7, A5=0.2, A6=1.6, A7=0.2, A8=1.4
S1=2.0, S2=0.7, S3=0.2, S4=1.1, S5=3.7, S6=0.6
Departure
Time = 3.1
System state
A 5.6
4.0
Clock
3.8
4.0
System
D 4.9
Eventlist
Server
status
# in
que
Times
of
Arrival
Time
Of
Last Number Total
event delayed delay
Area
Under
Q(t)
Statistical Counters
Area
Under
B(t)
A1=0.4, A2=1.2, A3=0.5, A4=1.7, A5=0.2, A6=1.6, A7=0.2, A8=1.4
S1=2.0, S2=0.7, S3=0.2, S4=1.1, S5=3.7, S6=0.6
Departure
Time = 3.1
System state
A 5.6
Clock
4.0
Eventlist
Server
status
System
D 8.6
# in
que
Times
of
Arrival
Time
Of
Last Number Total
event delayed delay
Area Area
Under Under
Q(t) B(t)
Statistical Counters
A1=0.4, A2=1.2, A3=0.5, A4=1.7, A5=0.2, A6=1.6, A7=0.2, A8=1.4
S1=2.0, S2=0.7, S3=0.2, S4=1.1, S5=3.7, S6=0.6
Monte Carlo Simulation
• Solving deterministic problems using stochastic
models.
– Example: estimate
b
I   g ( x)dx
a
• It is efficient in solving multi dimensional
integrals.
Monte Carlo Simulation
• To illustrate, consider a known region R with
area A and R1 subset of R whose area A1 in
unknown.
• To estimate the area of R1 we can through
random points in the region R. The ratio of
points in the region R1 over the points in R
approximately equals the ratio of A1/A.
R
R1
Monte Carlo
Simulation
• To estimate the integral I. one can estimate
the area under the curve of g.
– Suppose that M = max {g(x) } on [a,b]
1. Select random numbers
X1, X2, …,Xn in [a,b]
M
R
And Y1, Y2, … ,Yn in [0,M]
R1
a
2. Count how many points
(Xi,Yi) in R1, say C1
b
3. The estimate of I is then
C1M(b-a)/n
Advantages of Simulation
• Most complex, real-world systems with stochastic
elements that cannot be described by
mathematical models. Simulation is often the only
investigation possible
• Simulation allow us to estimate the performance
of an existing system under proposed operating
conditions.
• Alternative proposed system designs can be
compared with the existing system
• We can maintain much better control over the
experiments than with the system itself
• Study the system with a long time frame
Disadvantages of Simulation
• Simulation produces only estimates of
performance under a particular set of
parameters
• Expensive and time consuming to develop
• The Large volume of numbers and the
impact of the realistic animation often
create high level of confidence than is
justified.
Pitfalls of Simulation
• Failure to have a well defined set of objectives at
the beginning of the study
• Inappropriate level of model details
• Failure to communicate with manager during the
course of simulation
• Treating a simulation study as if it is a
complicated exercise in computer programming
• Failure to have well trained people familiar with
operations research and statistical analysis
• Using commercial software that may contain
errors
Pitfalls of Simulation cont.
• Reliance on simulator that make simulation
accessible to anyone
• Misuse of animation
• Failure to account correctly for sources of
randomness in the actual system
• Using arbitrary probability distributions as input of
the simulation
• Do output analysis un correctly
• Making a single replication and treating the output
as true answers
• Comparing alternative designs based on one
replication of each design
• Using wrong measure of performance