simulation 100

Simulation

Building a model of a system and experimenting with it, to understand how the system behaves or to evaluate strategies for running it.

State of a system

The set of variables needed to describe the system at one moment, such as machines available and jobs waiting.

Event

A change of the system state at a point in time, such as an arrival or the end of a service.

Discrete event stochastic simulation

The state changes only at events (discrete event), and the timing of events is uncertain and drawn from probability distributions (stochastic).

When should you not simulate?

When the answer is simple to calculate analytically. Analytical models are faster and easier to optimise.

Monte Carlo simulation

Simulation that uses random numbers but has no time dimension, so the model is static.

Why not just experiment in reality?

It is expensive, not repeatable, slow, sometimes dangerous or not allowed, and impossible if the system does not exist yet.

Typical inputs and outputs of a simulation model

Inputs: arrivals, layout, processing and set-up times, routing, control rules. Outputs: throughput and waiting times, service levels, utilisation, inventory.

Continuous simulation

State variables change continuously over time, usually described by differential equations, such as a water level.

System dynamics

Models aggregate factors and their causal loops instead of individual entities. Mostly used for strategic policy analysis.

Agent-based simulation

Bottom-up modelling driven by the smallest entities. Often a special case of discrete event simulation.

Three elements of event control

The simulation clock (current time), the event list (future events) and the event controller that manages the list.

How does a simulation move through time?

The event list is sorted on time and the clock jumps straight to the next event; nothing happens in between.

Pseudo random number generator

A formula that produces numbers which cannot be statistically told apart from independent uniform numbers between 0 and 1.

Four requirements for a random number generator

Numbers look uniform and uncorrelated; fast and light on memory; reproducible; able to give multiple independent streams.

Seed

The starting value of a random number generator. The same seed reproduces exactly the same sequence.

Why is one simulation run not enough?

Random input gives random output, so one run is only a point estimate. You need replications and a confidence interval.

Four characteristics of object orientation

Abstraction, encapsulation, modularity and hierarchy.

Encapsulation

Separating an object's interface from its implementation, so the inside is hidden and can be replaced without changing the rest.

Inheritance

A subclass or derived object takes over the attributes and methods of its class, so changing the class updates everything derived from it.

The simulation loop (four routines)

Initialisation sets the clock, state and event list. The timing routine picks the next event and advances the clock. The event routine updates state and schedules new events. The report generator computes results.

Midsquare method and why it fails

An early generator that squares a number and takes the middle digits. It collapses to zero or falls into short cycles.

Linear congruential generator

A generator where each number is computed from the previous one by multiplying, adding a constant and taking the remainder after division by a large modulus.

Abstraction

Representing only the essential characteristics that distinguish an object from others.

Modularity

Splitting a system into cohesive, loosely coupled modules that can be built and tested separately.

Hierarchy: 'part of' vs 'is a'

'Part of' is an object hierarchy (a machine is part of a plant). 'Is a' is a class hierarchy with inheritance.

Pros and cons of object-oriented simulation

Pros: natural representation, reuse, manageable complexity, easier maintenance. Cons: steeper learning curve, benefits only after many projects.

When queueing theory, when simulation?

Queueing theory for simple systems and quick first estimates; simulation when the system or network is too complex.

Kendall notation

A code describing a queue: arrival process, service process, number of servers, then queue discipline, capacity and population.

Why not maximise utilisation?

Waiting times and queue lengths grow non-linearly with utilisation and explode as it approaches 100%.

Effect of variability on waiting

More variability in arrivals or service times means longer waiting, even at the same utilisation.

Jackson's theorem

An open network of queues can be analysed as if every station were an independent queue.

Steady state: simulation vs queueing theory

Simulation: KPIs are stable after the warm-up. Queueing theory: the state probabilities no longer change, and the time to get there is ignored.

Burke's theorem

If arrivals to a station are Poisson, the departures from it are Poisson with the same rate.

Open vs closed queueing network

Open: entities enter and leave the system. Closed: a fixed number of entities circulates.

Which queueing results are exact and which are approximations?

Exact: single and multi-server queues with Poisson arrivals, including general service times for one server. Approximations: Kingman and Allen-Cunneen for general arrivals.

Examples of arrivals that are not Poisson

Scheduled appointments and arrivals from an upstream machine. Both are more regular than Poisson.

What can simulation do that queueing theory cannot?

Model detailed logic such as routing and batching, track performance over time, and show the uncertainty in results instead of only averages.

Three ways to model random input (in order of preference)

A theoretical distribution, then an empirical distribution, then using the historical data directly.

Why prefer a theoretical distribution?

It smooths irregularities, can generate values outside the observed range, and is easy to change for sensitivity analysis.

Three steps to fit a theoretical distribution

Hypothesise a family of distributions, estimate its parameters, then check the fit against the data.

Q-Q plot

A plot of the sorted data against the quantiles of the fitted distribution. A good fit lies on a straight diagonal line.

Chi-square goodness-of-fit test

Splits the data range into intervals and compares observed counts with the counts expected under the fitted distribution.

Does not rejecting the null hypothesis prove the distribution fits?

No. It only means the difference is not statistically significant.

When to use an empirical distribution or direct data

Empirical: no theoretical distribution fits, or extreme values must be avoided. Direct data: validation and complex correlated data.

Drawback of a theoretical distribution

Long tails can produce unrealistic extreme values. The fix is to truncate the distribution.

Clues from summary statistics

Standard deviation about equal to the mean suggests exponential. Zero skewness suggests a symmetric distribution; positive skewness suggests Gamma, Lognormal or Weibull.

P-P plot vs Q-Q plot

Both compare data with a fitted distribution. The P-P plot is sensitive to the middle of the distribution, the Q-Q plot to the tails.

Guidelines for chi-square intervals

Use intervals of equal probability, with at least five expected observations in each and at least three intervals.

Kolmogorov-Smirnov test

A goodness-of-fit test based on the largest vertical distance between the empirical and the fitted distribution function.

Type I vs Type II error

Type I: rejecting a true null hypothesis. Type II: failing to reject a false one.

Autocorrelation

Correlation between successive observations in one sequence. It breaks the independence that most statistical methods assume.

Choosing a distribution without data

Ask an expert for a minimum, a maximum and a most likely value, and use a triangular distribution.

Why can't you apply standard statistics to observations within one run?

They are correlated, for example the waiting times of successive customers.

Transient vs steady state behaviour

Transient: performance still depends on the initial conditions. Steady state: it no longer does.

Terminating vs non-terminating simulation

Terminating: a natural event ends the run, such as closing time. Non-terminating: no natural end, so you study steady state.

Warm-up period

The start of a run, where results still depend on the initial conditions. It is deleted before measuring steady state performance.

Welch's method

A graphical way to find the warm-up: average over replications, smooth with a moving average, and see where the curve becomes stable.

MSER rule

Finds the warm-up by choosing the cut-off that makes the remaining data least variable while keeping as much data as possible.

Replication/deletion vs batch means

Replication/deletion: many runs, each with its own warm-up. Batch means: one long run with one warm-up, split into batches.

How do you decide the number of replications?

Keep adding replications until the confidence interval is narrow enough relative to the mean.

When is a difference between two systems significant?

When zero lies outside the confidence interval for the difference in their means.

Paired-t vs Welch approach

Paired-t: equal numbers of runs that may be correlated, the usual case in simulation. Welch: independent samples of possibly unequal size.

Non-terminating simulation without a steady state

Treat it as a terminating simulation.

Steady state cycles

Performance repeats in a pattern, such as waiting time by day of the week, so it is measured per cycle.

Sequential procedure for replications

Start with a few replications and add one at a time until the confidence interval is narrow enough. Estimate the number first, so you know how long it will take.

Initial conditions in a terminating simulation

Starting empty can bias results. Start with a realistic state, for example by drawing the starting queue from measured data.

Risk of the batch means method

If batches are too small they are correlated, which makes confidence intervals too narrow.

Time plots

Plots of a variable over time, such as queue length, that show dynamic behaviour. Do not build confidence intervals on these correlated observations.

Three steps of a simulation study

Problem definition, model construction, and experimental design with analysis of results.

Why not make the model as detailed as possible?

It costs more, needs more data, has more errors and runs slower, without necessarily being more accurate.

Verification

Checking that the computer model correctly implements the conceptual model.

Validation

Checking that the model represents reality accurately enough for the purpose of the study.

Credibility

The decision maker accepts the model and its results as correct.

White box vs black box validation

White box: validate the components, such as input distributions. Black box: compare the model's overall output with the real system.

Factors, levels and responses

Factors are the inputs you vary, levels are the values they take, and responses are the output performance measures.

Interaction effect

The effect of one factor depends on the level of another. Changing one factor at a time misses this.

Two-level factorial design

Give every factor a low and a high level and simulate all combinations, to estimate main effects and interactions.

Main effect

The average change in the response when a factor moves from its low to its high level.

Fractional factorial design and confounding

Run only part of the combinations to save effort. The price is that some effects become confounded: they cannot be separated.

Simulation-based optimisation

Using earlier results to decide which configuration to simulate next, searching for the best settings in few runs.

Law's ten steps of a simulation study

Formulate the problem; collect data and define the model; validate the conceptual model; program and verify; pilot runs; validate the programmed model; design experiments; production runs; analyse output; document and present.

Five sub-steps of problem definition

Identify the problem and goals; choose experimental factors and reports; set scope and level of detail; collect and analyse data; write a project specification.

Contents of a project specification

Problem and goals, expected results, model description with scope, assumptions, factors and reports, data requirements, time planning and cost estimate.

Scope vs level of detail

Scope is what part of the system is modelled. Level of detail is how finely it is modelled.

Ways to simplify a model

Start basic and refine, split into modules, aggregate processes or items, and leave out resources, low-level components and rare events.

Verification techniques

Test modules separately, structured walk-through, plausibility runs, tracing, comparing with analytical results, watching the animation, using the debugger.

Turing test in validation

Experts are shown model data and real data and try to tell which is which.

One-factor-at-a-time experiments

Vary one factor while keeping the others fixed. Needs few experiments but misses interaction effects.

How to judge whether an effect is significant

Replicate the whole design several times and build a confidence interval for the effect.

Limitations of a two-level factorial design

It assumes linear effects, the results depend on the chosen low and high levels, and levels set too far apart can hide interactions.

Why is simulation-based optimisation hard?

There are very many possible configurations, each evaluation is a costly simulation run, and results are noisy because of randomness.

Inverse transform method

Generate a uniform random number and pass it through the inverse of the cumulative distribution function to get a value from that distribution.

Variance reduction

Deliberately introducing useful correlation in the output to get narrower confidence intervals from the same number of runs.

Common random numbers

Use the same random numbers for every configuration, so differences in output come from the configurations and not from chance.

Synchronisation

Making sure the same random number is used for the same purpose in every experiment, for example a separate stream per random process.

Antithetic variates

For a single system: pair each run with one driven by the opposite random numbers, so high and low outcomes cancel out.

Inverse transform for a discrete distribution

Generate a uniform random number and return the smallest outcome whose cumulative probability is at least that number.

Convolution method

Generate a variable that is a sum of others by generating the parts and adding them, such as an Erlang from exponentials.

Tricks to keep synchronisation

Give each random process its own stream, discard unused random numbers, generate values in advance, and check every replication.