Description

4 attachmentsSlide 1 of 4attachment_1attachment_1attachment_2attachment_2attachment_3attachment_3attachment_4attachment_4

Unformatted Attachment Preview

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);

}

}

Purchase answer to see full

attachment

User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.