Event Relationship Graphs Questions

Problem 1: System Time to Failure (TTF)The TTF consists of two components that alternatively work as an active and cold spare:
• The spare component becomes the active component when the (current) active component fails;
• when a component fails it starts repair immediately;
• The failed component becomes the spare component as soon as it finishes repair;
• the system fails if both components have failed;
• the system is operational as long as at least one component is operational;
• Lifetime of a component is a discrete uniform {1, 2, . . . , 5, 6};
• The repair time is 2.5 days.
Question 1:
Describe the states and the events characterizing the dynamic of the failure of the component.
Question 2:
Draw the events graph for the example showing the relationship between the events and the triggering conditions for each arc to be executed.
2
IEE 475 GP© ASU
Question 3:
Write the pseudo-code, as seen in class, for each event in terms of: state update and events scheduled.
3
IEE 475 GP© ASU
Problem 2: The M/G/1 queue
The receptionist in a medium-sized hospital helps direct entering patients and visitors to the relevant floor or
wing of the building:
• It is under discussion to replace the human receptionist with an electronic kiosk;
• Patients arrive according to a Poisson process with rate λ (time between arrivals is exponential);
• Service times are i.i.d. with mean τ and deviation σ time units.
Question 1:
Describe the states and the events characterizing the dynamics of the queue of interest.
Question 2:
Draw the events graph for the example showing the relationship between the events and the triggering conditions for each arc to be executed.
4
IEE 475 GP© ASU
Question 3:
Write the pseudo-code, as seen in class, for each event in terms of: state update and events scheduled.
5
IEE 475 GP© ASU
Problem 3: The Stochastic Activity Network
A construction project consists of a large number of activities. Some can be completed in parallel, while others
are subject to constraints on the sequence.
• A project is completed when all the ` = 1, 2, . . . , L activities are completed;
• Each activity has a duration X` which is randomly distributed;
• Planners are interested in information about the distribution of Y , i.e., the project finishing time, for
instance:
θ = P r (Y > tp )
where tp is the quoted duration of the project.
In order to answer the questions refer to the small activity network in Figure 1.
Figure 1: Stochastic Activity Network
According to Figure 1, the project starts with milestone a (i.e., there is no delay between the start and a nodes)
and the sequence of events is determined by the arcs representing the 5 activities and the related duration
Xi , i = 1, 2, . . . , 5. These durations are random with a specific distribution. Milestone d is the final of the
project and it gets to the “end” milestone with no delay.
Question 1:
Describe the states and the events characterizing the dynamic of the activity network.
6
IEE 475 GP© ASU
Question 2:
Draw the events graph for the example showing the relationship between the events and the triggering conditions for each arc to be executed.
Question 3:
Write the pseudo-code, as seen in class, for each event in terms of: state update and events scheduled.
7
IEE 475 GP© ASU
General Principles of Simulation
G. Pedrielli
SCHOOL OF COMPUTING INFORMATICS & DECISION SYSTEMS
ENGINEERING
Pedrielli
School of CIDSE
1 / 20
Table of contents
1 Learning Objectives
2 A simple System
3 Simulation Questions
4 Simulation Model Components
Pedrielli
School of CIDSE
2 / 20
Learning Objectives
Learning Objectives
Underlying ideas, methods, and issues in simulation
Centered around an example of a simple processing system
Decompose the problem
Terminology
Simulation by hand
Some basic statistical issues
Overview of a simulation study
Pedrielli
School of CIDSE
3 / 20
A simple System
A Simple Processing System
General Objective:
Estimate expected production;
Estimate the waiting time in queue, queue length, proportion of
time machine is busy;
Time Units:
Can use different units in different places . . . must declare;
Be careful to check the units when specifying inputs;
Declare base time units for internal calculations, outputs;
Be reasonable (interpretation, roundoff error).
Pedrielli
School of CIDSE
4 / 20
A simple System
An Example
Initially (time 0) empty and idle
Base time units: minutes
Input data (assume given for now . . .), in minutes:
Stop when 20 minutes of (simulated) time have passed.
Pedrielli
School of CIDSE
5 / 20
Simulation Questions
Output Performance Measures
Before we develop a simulation model we should know which quantities
we are interested in tracking!!!
Total Production of parts over a simulation run Φ;
Average waiting time of parts in queue:
Pn
wq,i
W̄q = i=1
n
Maximum waiting time of parts in queue:
Wqmax =
max wq,i
i=1,2,…,n
Time Average Queue:
Q̄(T ) =
Pedrielli
1
T
Z
T
q (t) dt
0
School of CIDSE
6 / 20
Simulation Questions
Output Performance Measures
Maximum number of parts in queue:
Qmax (T ) = max q (t)
0≤t≤T
Average Cycle Time:
PΦ
i=1 ci
C̄ =
Φ
Maximum Cycle Time of parts in queue:
C max =
Machine Utilization:
(
Z
1
1 T
B̄(T ) =
b (t) dt, b(t) =
T 0
0
Pedrielli
max ci
i=1,2,…,Φ
If the machine is busy at time t
Otherwise
School of CIDSE
7 / 20
Simulation Model Components
What to model
Individual operations (arrivals, service times) will occur exactly as
in reality;
Movements, changes occur at the right “time”, in the right order
Different pieces interact;
Install “observers” to get output performance measures;
Adopt a concrete, “brute-force” analysis approach;
Nothing mysterious or subtle.
In order to achieve your modeling objectives you can use:
Entities;
Attributes;
Global Variables;
Resources;
Queues;
Statistical Accumulators.
Pedrielli
School of CIDSE
8 / 20
Simulation Model Components
Entities
“Players” that move around, change status, affect and are affected
by other entities;
Dynamic objects — get created, move around, leave (maybe);
Usually represent “real” things (“fake” entities for modeling
“tricks”);
Usually have multiple realizations “floating” around;
different types of entities exist concurrently.
Pedrielli
School of CIDSE
9 / 20
Simulation Model Components
Attributes
Characteristic of all entities: describe, differentiate
All entities have same attribute “slots” but different values for
different entities, for example:
Time of arrival
Due date
Priority Color
Attribute value tied to a specific entity;
Like “local” (to entities) variables.
Pedrielli
School of CIDSE
10 / 20
Simulation Model Components
Global Variables
Reflects a characteristic of the whole model, not of specific entities;
Used for many different kinds of things;
Travel time between all station pairs;
Number of parts in system;
Simulation clock (TNOW);
Name, value of which there’s only one copy for the whole model;
Not tied to entities;
Entities can access, change variables.
Pedrielli
School of CIDSE
11 / 20
Simulation Model Components
Resources
What entities compete for;
People
Equipment
Space
Entity seizes a resource, uses it, releases it;
Think of a resource being assigned to an entity, rather than an
entity “belonging to” a resource;
A resource can have several units of capacity;
Seats at a table in a restaurant
Identical ticketing agents at an airline counter
Number of units of resource can be changed during the simulation.
Pedrielli
School of CIDSE
12 / 20
Simulation Model Components
Queues
Place for entities to wait when they can’t move on (maybe since
the resource they want to seize is not available);
Often tied to a corresponding resource;
Can have a finite capacity to model limited space — have to model
what to do if an entity shows up to a queue that’s already full;
Usually interested in the length of a queue, waiting time in it.
Pedrielli
School of CIDSE
13 / 20
Simulation Model Components
Statistical Accumulators
Variables that “watch” what is happening;
Depend on output performance measures desired;
“Passive” in model — don’t participate, just watch;
Many are automatic, but …;
At end of simulation, used to compute final output performance
measures.
Examples:
Number of parts produced so far;
Total of the waiting times spent in queue so far;
No. of parts that have gone through the queue;
Max time in queue we’ve seen so far;
Total of times spent in system;
Max time in system we’ve seen so far;
Area so far under queue-length curve Q(t);
Max of Q(t) so far;
Area so far under server-busy curve B(t).
Pedrielli
School of CIDSE
14 / 20
Simulation Model Components
Events and State variables
Event Calendar: it is a list of event records
Entity No., Event Time, Event Type;
Keep sorted in increasing order on Event Time;
Next event always in top record;
Initially, schedule first Arrival, schedule stopping event.
State variables: describe current status
Server status B(t) = 1 for busy, 0 for idle;
Number of customers in queue Q(t);
Times of arrival of each customer now in queue (a list of random
length).
Pedrielli
School of CIDSE
15 / 20
Simulation Model Components
Simulating with Arena vs. Simulating with a general purpose language
Arena uses The Process View to model a system. The basics are:
Identify characteristic entities in the system;
Multiple copies of entities co-exist, interact, compete;
“Code” is non-procedural;
Tell a “story” about what happens to a “typical” entity;
May have many types of entities, “fake” entities for things like
machine breakdowns;
Usually requires special simulation software;
Underneath, still executed as event-scheduling (see next).
Pedrielli
School of CIDSE
16 / 20
Simulation Model Components
Simulating with Arena vs. Simulating with a general purpose language
A general purpose simulator implements the Event-Scheduling
“World View”;
Identify characteristic events;
Decide on logic for each type of event to:
Change the state for each event type
Observe statistics
Update times of future events (maybe of this type, other types)
Keep a simulation clock, future event calendar;
Jump from one event to the next, process, observe statistics,
update event calendar;
Must specify an appropriate stopping rule.
Pedrielli
School of CIDSE
17 / 20
Simulation Model Components
What do you need to code a discrete event simulator
Use “utility” libraries;
List processing;
Random-number generation;
Random-variate generation;
Statistics collection;
Event-list and clock management;
Summary and output;
Main program ties it together, executes events in order.
Pedrielli
School of CIDSE
18 / 20
Simulation Model Components
Event Simulation for the Simple Production System
Pedrielli
School of CIDSE
19 / 20
Simulation Model Components
Simulation By Hand
Manually track state variables, statistical accumulators;
Use “given” inter-arrival, service times;
Keep track of event calendar;
“Lurch” clock from one event to the next.
Pedrielli
School of CIDSE
20 / 20
Rework
In some cases, it may be necessary to rework a part that has just
been processed.
A random number, RND,
that falls (strictly) between
0 and 1 is drawn.
𝑡𝑟 is the rework setup time
Notice that if we model REWORK in this manner, LEAVE, REWORK,
and ENTER might all schedule a START vertex at the same time.
This model illustrates problems that may occur when two events are
scheduled at the same time.
Giulia Pedrielli
Simulating Stochastic Systems (IEE 545)
2
Rework (cont’d)
(Solver Compliant):
Increase the state
space when R_{i}=1
the server is
reserved by the i-th
trigger
(Q>0 && R_1==0&& R_2 == 0)
S
(S==1 && R_2==0
&& R_3 == 0)
S
Q=Q+1
R_1=1*(S==1)+0*(S==0)
(Okay in manual code the
solver may give you
troubles!)Perform state
update as follows:
• “Local Update”
• Check Conditions
• “Second Update” &
Schedule
Strt
Leav
S=1
S=R_1=R_2=R_3=0
Q=Q-1
(S==1)
R_3=1*(Q>=1)+0*(Q==0)
Rew
(RND0)
S
Ent
Q=Q+1
S=0*(S==1)
Giulia Pedrielli
(RND=1)+1*(Q==0)
3
Limited Waiting Space
The amount of waiting space is called the buffer size and called B
in the example below.
The self-scheduling edge used to create customer arrivals is moved
from the ENTER vertex to the ARRIVE vertex.
We also conditioned the edge from ARRIVE to ENTER to require that
there be an empty space for the arriving customer to wait.
Giulia Pedrielli
Simulating Stochastic Systems (IEE 545)
4
Assembly operation
In an assembly operation, several different types of parts are put
together into a single unit. The collected parts for a finished
assembly are sometimes called a “kit.”
Giulia Pedrielli
Simulating Stochastic Systems (IEE 545)
5
Different Servers Working in Parallel
Some systems have two servers with different characteristics
operating in parallel. In this example, there is a new, faster machine
working with last year’s slower model.
{S[0]=1, S[1]=1}
Giulia Pedrielli
Simulating Stochastic Systems (IEE 545)
6
Simulating based on counters
N is the number of cars washed.
The simulation run stops when N reaches the value a.
(N>=a)
COU
NT
{N=0}
{N=N+1}
Giulia Pedrielli
Simulating Stochastic Systems (IEE 545)
7
A Semi-Random Walk
Build a simulation model of a semi-random walk. The location of the
walker on the line is given by the variable, X. Every step is in an
opposite direction and has an expected step length equal to 4
feet. However, the steps to the left are uniformly distributed
between 3 and 5 while steps to the right are exactly 4 feet long.
Would you expect the location of the walker to change much over
time?
(𝑇𝐼𝑀𝐸 ≥ 𝑒𝑛𝑑_𝑡𝑖𝑚𝑒)
1
RUN
{X=0}
Giulia Pedrielli
RIGHT
{X=X+4}
LEFT
END
1 {X=X-UNIF(3,5)}
Simulating Stochastic Systems (IEE 545)
8
Event Parameters and Edge Attributes
I+1
~ (I < 7) EVENT (I) ~ 2 (I = = 7) Do EVENT: FOR I = 2 to 7 Giulia Pedrielli Simulating Stochastic Systems (IEE 545) 9 Many Servers of Many Types A generalization of the model with two types of servers is a model of many types of servers with many servers of each type. As example, consider a production department with 𝑁 different types of machines of different models and ages. There may be any number of each type of machine. Giulia Pedrielli Simulating Stochastic Systems (IEE 545) 10 TTF System (X>0)
State Variables
Number of functional
components 𝑋 ∈ 0,1,2
Events
RUN
 FAIL: One component fails
 REPAIR: One component
is repaired
 END: System fails
tf
{X=2}
tf
FAIL
tr
{X=X-1}
(X>0)
REPAIR
Giulia Pedrielli
(X==0)
END
Simulating Stochastic Systems (IEE 545)
{X=X+1}
11
Final considerations
 ERGs can be used to derive a formal representation of the system
dynamics. Modeling a system using ERGs helps to understand the
system dynamics and the simulation model we want to develop.
 They are general enough to represent any system dynamics (they
are Turing complete)
 They are more general than others (e.g., Petri nets, GSMPs, etc.)
 ERG models can be
(http://sigmawiki.com/)
Giulia Pedrielli
implemented
in
Simulating Stochastic Systems (IEE 545)
SIGMA
software
12
Simple production system: Event graph and pseudo code.
𝜏𝐴
Q>0
𝜏𝐴
𝜏𝐷
𝜏𝐷
R>0
R>0
A
D
R=[R-1] if R>0
R=[R+1] if Q=0
Q=Q+1
Q=Q-1
Notation:
•
•
•
•
Q>0
𝜏𝐷
A
S
D
Q=Q+1
R=R-1
R=R+1
Q=Q-1
𝜏𝐴 : Inter-arrival time;
𝑅(𝑡) : Number of free servers at time t;
𝑄(𝑡): Level of the queue (including the server) at time t;
𝜏𝐷 : Processing time.
Pseudo-code:
Pseudo-code:
A(Arrival) :: Input (𝜏𝐴 , 𝑅(𝑡), 𝜏𝐷 )
{
If (R>0) // There is a free server
{
R=R-1; // Dicrease the num of free stations
Schedule Event D(𝑡 + 𝜏𝐷 );
}
Q=Q+1; //Increase the queue level
Schedule Event A(𝑡 + 𝜏𝐴 );
}
A(Arrival) :: Input (𝜏𝐴 , 𝑅(𝑡))
{
If (R>0)
{
Schedule Event S(t);
}
Q=Q+1;
Schedule Event A(𝑡 + 𝜏𝐴 );
}
D(Departure) :: Input (𝑅(𝑡), 𝑄(𝑡), 𝜏𝐷 )
{
R(t)=R+1;
Q(t)=Q-1;
If (Q>0)
{
Schedule Event D(𝑡 + 𝜏𝐷 );
R=R+1;
}
}
S(Start) :: Input ( 𝑅(𝑡), 𝜏𝐷 )
{
R=R-1; //Occupy the machine
Schedule Event D(𝑡 + 𝜏𝐷 );
}
D(Departure) :: Input (𝑅(𝑡), 𝑄(𝑡))
{
R(t)=R(t)+1;
Q=Q-1;
If (Q>0)
{
Schedule Event S(t);
}
}