Steps in a Simulation Study

In this lesson, we will look at the different steps involved in a simulation study.

Problem Formulation
The first step in a simulation study is a high-level problem formulation or problem
statement. For example, a problem might be that profits are too low or that
customers are complaining about the long lines. Note that the problem statement is
often quite general.

Objectives and Planning

In the second step, we focus on objectives and planning. Here we try to consider
the specific questions we want to answer to attack the problem we defined. For
example, we might want to know how many workers to hire or how much buffer
space to insert in the assembly line. By answering these questions, we can
potentially mitigate our problem.

Model Building
In step three, we look at model building. We might be interested in an M/M/k
queueing model, and so we might be curious about interarrival times, service times,
and server counts. Alternatively, we might be modeling natural phenomena that may
require us to revisit physics equations.

Sometimes, we combine several models to form a supermodel. The model building

process isn't strictly about math; instead, it's both an art and a science that combines
rigor, experience, and creativity.

Data Collection
Data collection comes next. Here we think about what kinds of data we need. This
consideration will often include specific data points of interest as well as
understanding the general characteristics of the data. For example, are we looking at
discrete or continuous data?

Additionally, we have to understand how much data we need and whether we can
reconcile that need against our budget. Usually, more data is better, and clean data
is better than that, but data collection and processing is often a big, expensive task.

Coding
At this point, it's time to start coding. There are many simulation languages to
choose from and even more general-purpose programming languages - C++,
Python, etc. - that may be sufficient.
Regardless of language choice, we have to consider the modeling paradigm, which
describes, at a high level, how we reason about the simulation. Two examples of
such paradigms are event-scheduling and process-interaction.

Verification
After we've written at least the first iteration of code, we turn to verification. In this
step, we make sure that our program works as expected. In the case of obvious
programming errors, we return to the coding step.

Validation
More importantly, we also need to focus on validation. Did we choose the right
model? For example, if we modeled a particular system as a simple MM1 queueing
system, yet we have five servers instead of one, the answer is "no". Usually, we can
show that we have chosen the wrong model using certain statistical techniques. If
our model is incorrect, we have to go back to the modeling and data collection steps.

Experimental Design
Once the code has been verified, and the model has been validated, it's time to look
at experimental design. In this phase, we think about what experiments we need to
run to answer our questions efficiently.

When working on experimental design, we need to think about both statistical

considerations - how many experimental runs should I complete to answer my
question with high confidence? - as well as time and budget constraints.

Experimental Runs
Once the designs are complete, it's time to run experiments. We press the "go"
button and start executing the experiments that we just designed. Often, these
experiments take a lot of time to complete.

Output Analysis
After conducting the experiments, we turn to output analysis. We have to perform
correct, relevant statistical analysis of the data we gathered from our experiments.
This process is often performed iteratively, in conjunction with the experimental
design and execution steps. As a general rule, we almost always need more
experimental runs.

Implementing Results
Finally, we need to write up our reports and implement results. If all goes well,
management will be happy, and we'll be happy, too.
 Some Useful Definitions
In this lesson, we will learn some easy definitions that are relevant to all general
simulation models. We will use these definitions throughout the rest of the course,
and they will be especially important when we look at programming simulations.

System/Entities
A system is a collection of entities - people, machines, things - that interact
together to accomplish a goal.

Model
A model is an abstract representation of a system. Usually, the model contains
certain mathematical or logical relationships that describe the system in terms of:

 the entities involved in the system

 the various states and state transitions of the system
 the events that can occur in the system

As a basic example, we might model a single-server queueing system using an MM1

queueing model.

System State
The system state is a collection of variables that contains enough information to
describe the system at any point in time. We can think of the state as a complete
snapshot of the system, containing all the information we need.

Let's look at a single-server queue. At a minimum, we need to keep track of two

variables. First, we need to know the number of people in the queue at
time �t, ��(�)LQ(t). We also have to keep track of whether the server is busy
or idle at time �t, �(�)B(t). If �(�)=0B(t)=0 then the server is idle, and
if �(�)=1B(t)=1 then the server is busy. For a simplistic simulation, knowing
these two variables may be sufficient.

Attributes
Entities - customers, resources, servers - can be permanent or temporary. For
example, machines in an assembly line are often permanent, whereas individual
customers come and go.

Entities can have different properties or attributes. For example, different customers
have differing amounts of money to spend, and some customers may have higher
priority than others. In queueing systems, individual servers might have various
capacities for accomplishing work.
List/Queue
A list (or queue) is an ordered list of associated entities. For example, the line that
forms in front of a server is a queue and is often ordered by arrival time.

Event
An event is a point in time at which something interesting happens - that is, the
system state changes - that typically can't be predicted with certainty beforehand.

For example, in queueing systems, the time at which a customer arrives is an event.
We don't know with certainty when a customer will arrive, but we do know that an
arrival changes the state of the system. Similarly, the time at which a customer
departs is an event.

Some people regard an event not only as the time that something happens but also
the type of thing that happens. Even though an event technically refers to a time, we
can also use it to refer to a "what"; for example, an arrival event.

Activity
An activity, also known as an unconditional wait, is a duration of time
of specified length. For example, we might say that the times between customer
arrivals are exponential or that service times are constant. These events are
specified because we have explicitly defined the parameters for generating them.

Conditional Wait
A conditional wait is a duration of time of unspecified length. For example, in a
queueing system, we don't know customer wait times directly; in fact, that's often
why we are running a simulation. All we can specify when we are programming our
simulation are the arrival times and service times. From those specifications, either
we or the simulation language has to reverse engineer the waiting times.

Folks will occasionally run simulations and observe the waiting times and forget
about the arrival times and service times. As it turns out, it's a lot harder to reverse
engineer these variables from the waiting times. As a result, the best strategy is to
collect the arrival times and service times.

Time-Advance Mechanisms
Time advance mechanism discusses how the simulation clock moves forward as
time progresses.

Definitions
The simulation clock is a variable whose value represents simulated time (not real
time). Time-advance mechanisms describe how the simulation clock moves from
time to time. The clock always moves forward, never backward, and can advance
using two mechanisms: fixed-increment time advance and next-event time advance.

Clock Movement
In the fixed-increment time advance approach, we update the system state at
fixed times, nℎ, where n=0,1,2, …. where h is a small number chosen
appropriately. For example, if ℎ is minute, then we update the state every minute.

This approach makes sense for continuous-time models such as models of aircraft
movement through space or weather patterns. Additionally, we use this approach in
models where data is only available at fixed time units, such as at the end of every
month.

Suppose we are looking at a queuing model where customers enter the queue and
get served and leave the queue. If we are advancing the clock for every second,
nothing is happening most of the time, and we are just wasting computation cycles.

In the next-event time advance approach, we determine all future events at the
beginning of the simulation at time t=0 and we place them in a Future Events
List (FEL), ordered by time. Moving forward, the clock doesn't advance by a fixed
increment; instead, it jumps to the most imminent event at the head of the FEL.

For example, at time t=0, we might determine that one arrival occurs at
time t=23 and the next arrival occurs at t=29. After determining these events, our
FEL is a two-element list where the first arrival is the first element and the second
arrival is the second.

In this case, the clock advances from time t=0 to time t=23 and then
from t=23 to t=29. At each event, both the system state and potentially the FEL are
updated.

This approach has the benefit of jumping directly to times where interesting things
are happening.

FELs
By definition, the system state can only change at event times: nothing happens
between events. In queueing systems, in particular, we only care about arrivals and
departures, and we don't consider customers standing in line bored to be "anything
happening".

As a result, the simulation progresses sequentially by executing the most imminent

event on the FEL. After dealing with the most imminent event, it advances to the
next-most imminent event, and it progresses until the end of FEL.

Imminent Events
As the clock advances to the most imminent event at the head of the FEL, simulation
program has to do two things: update the system state and, potentially, update the
FEL.

The specific state update depends on the type of event we are processing. For
example, if we are looking at an arrival event, and the server is not busy, we have to
turn on the server. Alternatively, if the server is busy, the new arrival has to wait, so
we enqueue it. A departure event might involve turning a busy server off.

In any case, we might have to update the FEL. For example, when we process an
arrival, the first thing we often do is generate the next arrival, which we place at the
end of the FEL. Additionally, if a customer receives service upon arrival, we might
have to schedule an event marking the completion of this service.

Updating the FEL

Any time the simulation processes an event, it might have to update FEL. There are
several different operations that the simulation might perform on FEL:

 appending/inserting new events

 deleting events
 rearranging events
 doing nothing

Suppose a customer arrives in the system: an arrival event occurs. As we said, the
first step we usually take in processing an arrival is to spawn the next arrival time
and place it in the appropriate position in the FEL.

If the new arrival time is sufficiently far in the future, we can append it to the end of
the FEL. However, suppose we generated an arrival ten minutes into the future, but
a slow server doesn't finish serving the current customer until thirty minutes into the
future. In this case, the arrival event precedes the service completion event, and we
have to insert the arrival in the interior of the FEL instead of appending it.

Now, suppose we have an arrival of a particularly rowdy customer in the queue. In

response to this customer, other customers in line might switch lines or leave the
system altogether. For folks who switch lines, their associated events may need to
be rearranged within the FEL. If a customer leaves the system completely, any future
events linked to them should be deleted from the FEL.

.Example:next-event time advance mechanism.

We will consider a single server system containing a FIFO queue that will process
exactly ten customers. The arrival and service times for these customers are:

Customer 1 2 3 4 5 6 7 8 9 10
Arrival time 1 3 4 10 17 18 19 20 27 29

Service time 5 4 1 3 2 1 4 7 3 1

Simulation:

Clock t LQ(t) B(t) Queue(Cust, FEL(Event

ArrTime) Time, Event
Type)

0 0 0 0 (1,1A)

1 0 1 (2,3) (3,2A), (6,1D)

3 1 1 (2,3) (4,3A), (6,1D)

4 2 1 (2,3), (3,4) (10,4A)

6 1 1 (3,4) (6,1D),
(10,2D),
(10,4A)

10 1 1 0 (10,2D),
(10,4A),(11,3D)
 Two Modeling Approaches
There are two high-level simulation modeling approaches, the event-scheduling
approach and the process-interaction approach.

Event Scheduling
In event scheduling, our focus is on the events and how they affect the system
state. As the simulation evolves, we have to keep track of every event in increasing
order of time of occurrence.

Generic Event Scheduling Flow Chart

Most importantly, a main program invokes three routines: the initialization routine,
the timing routine, and the event routine.

First initialization routine is invoked. It should set the clock to zero and initialize the
system state, statistical counters, and the FEL. Usually, the FEL initially contains the
first arrival event and the event marking the end of the simulation.

Then, we invoke the timing routine. This routine determines when the next event is,
what type of event it is - arrival, departure, end of simulation - and then advances the
clock to the next event.

Third, we invoke the event routine itself. First, we update the system state along with
our statistical counters, and then we update the FEL appropriately given the event.
For example, if the routine is processing an arrival, we might generate another arrival
and append or insert it into the FEL. If we are processing the event marking the end
of the simulation, we generate any output and end the program; otherwise, we return
to the timing routine.
Arrival Event
First we examine the server and see if they are busy.

If the server is not busy, we set the waiting time for the arrived customer to zero, and
we update the appropriate statistics - for example, the average customer waiting
time. We increment the number of customers who have gone through the line, and
we make the server busy. Finally, we return to the main program.

If the server is busy, we add the customer to the queue and increment the number of
customers enqueued. If the queue is full, we might have to adjust some parts of the
system to accommodate this capacity. Perhaps we kick the customer out. If the
queue isn't full, we store the customer arrival time - we will need this later to compute
their waiting time. Finally, we return to the main program.
Departure Event
Check the status of the queue. If there are no more customers, we make the server
idle. Additionally, we eliminate the departure event being the next event because
departures are impossible if there are no customers. Finally, we return to the main
program.

If the queue isn't empty, we grab the first guy from the front of the queue and
subtract one from the number enqueued. We compute the delay of the customer
entering service and gather the appropriate statistics. We schedule his departure,
and we shift each remaining customer forward one space in the queue. Finally, we
return to the main program.
Process Interaction
In the process-interaction approach, we concentrate on a generic customer or
entity and the sequences of events and activities it undergoes as it progresses
through the system. The simulation language keeps track of how one generic entity
interacts with all the other generic entities. At any time during the simulation, there
may be many customers competing with each other for resources.

User has the task of modeling the generic customer, but don't have to deal with the
event bookkeeping, which the simulation package handles deep inside its core. The
simulation language is doing event scheduling in its implementation but exposes an
API that allows us to model using process interaction.

In queueing simulations, a customer is generated, eventually gets served, and then

[Link] Arena, we generate customers every once in a while. We process/serve
the customers after they wait in line for zero or more time units. Finally, we dispose
of the customers after we finish processing them.

Simulation Languages
There are more than 100 commercial simulation languages out in the ether. The
lower-level languages - FORTRAN, SIMSCRIPT, and GPSS/H - require more
programmer work. In contrast, the higher-level languages like Extend, Arena, Simio,
Automod, and any logic require a lot less programming effort to get up and running.

There are 5-10 major simulation players in university settings. In industry, the price
for simulation packages can range from under $1,000 to more than $100,000.
Thankfully, freeware is also available: simulation packages exist in Java and Python
(SimPyl). Though they might contain a learning curve, these packages can be
powerful and enjoyable to work with.

Selecting a Simulation Language

Factors should take into account when selecting a language:

Examine the various costs: For example, the cost of purchasing the licenses, the
cost of specialized programmers, as well as certain run-time costs.

Ease of learning: Different packages may have different learning curves, and each
may vary with respect to documentation, syntax, and flexibility.

Furthermore, compare packages based on their worldviews. If we are looking at

continuous systems, we need a language with continuous modeling capabilities.
Often, we need a language that supports a combination of different approaches.

Finally, Features in need. Different packages have different random variable

generators, statistics collection capabilities, debugging aids, graphics packages, and
user communities.