BSc CSIT (TU) Science Simulation and Modelling (BSc CSIT, CSC317) Question Paper 2079 Nepal

Discrete-Event Simulation (DES)

Discrete-event simulation models a system whose state changes only at discrete points in time, called events. Between two successive events the state of the system remains unchanged, so the simulation clock can simply jump from one event time to the next rather than advancing in fixed steps. Each event (e.g. a customer arrival or service completion in a queue) is processed in increasing order of its scheduled time and may cause the system state to change and may schedule future events.

Key components of a DES model:

• System state – set of variables describing the system (e.g. number in queue, server busy/idle).
• Simulation clock – current value of simulated time.
• Event list (FEL) – list of future events ordered by time of occurrence.
• Statistical counters – accumulate output measures (e.g. total delay, server utilization).
• Random-number / random-variate generators – produce inter-arrival and service times.

Event-Scheduling / Time-Advance Algorithm

This is the next-event time-advance mechanism:

1. Initialize – set clock $t = 0$, set initial state, clear counters, and place the first (initial) events on the Future Event List (FEL).
2. Find the imminent event – remove the event with the smallest event time $t_{i}$ from the FEL.
3. Advance the clock – set $t = t_{i}$ (the clock jumps to the time of the next event).
4. Execute the event routine – update the system state, update statistical counters, and schedule any new future events (placing them on the FEL).
5. Check termination – if the stopping condition is met (end time reached or FEL empty), generate the output report; otherwise go back to step 2.

Flowchart (described in words / pseudocode)

        +---------------------------+
        |   Initialization          |
        |   t = 0, state, FEL,      |
        |   counters                |
        +-------------+-------------+
                      |
                      v
        +---------------------------+
        | Remove imminent event     |
        | (min event time) from FEL |
        +-------------+-------------+
                      |
                      v
        +---------------------------+
        | Advance clock: t = t_i    |
        +-------------+-------------+
                      |
                      v
        +---------------------------+
        | Execute event routine:    |
        |  - update state           |
        |  - update counters        |
        |  - schedule future events |
        +-------------+-------------+
                      |
                      v
                 < Stop? >---No----+
                      | Yes        |
                      v            | (loop back to remove
        +---------------------------+   next imminent event)
        | Generate report / output  |
        +---------------------------+

Because the clock advances event by event, DES is far more efficient than fixed-increment time advance for systems where events are sparse in time.

Steps in a Sound Simulation Study

A well-conducted simulation study follows a structured sequence of stages (after Banks, Carson & Nelson):

1. Problem formulation – clearly state the problem and the questions the study must answer.
2. Setting of objectives and overall plan – define objectives, performance measures, alternatives, time, and resources.
3. Model conceptualization – abstract the real system into a logical/mathematical model with the right level of detail.
4. Data collection – gather input data for parameters and for fitting probability distributions.
5. Model translation (coding) – implement the model in a simulation language (GPSS, SIMSCRIPT) or a general language.
6. Verification – is the program correct? Check that the model is implemented as intended (debugging).
7. Validation – does the model behave like the real system? Compare model output with real-system data.
8. Experimental design – decide the alternatives to simulate, run length, number of replications, and warm-up period.
9. Production runs and analysis – execute the runs and estimate performance measures.
10. More runs? – based on analysis, decide whether additional runs/alternatives are needed (feedback loop).
11. Documentation and reporting – document model, assumptions, and results.
12. Implementation – put the recommended solution into practice.

Flowchart (described in words)

Problem formulation
        |
Objectives & overall plan
        |
  +-----+------+
  v            v
Model        Data
conceptual.  collection
  +-----+------+
        |
Model translation (coding)
        |
   < Verified? >--No--> (debug, back to coding)
        | Yes
   < Validated? >--No--> (back to model conceptualization / data)
        | Yes
Experimental design
        |
Production runs & analysis
        |
   < More runs? >--Yes--> Experimental design
        | No
Documentation & reporting
        |
Implementation

The verification, validation and "more runs?" decision points create feedback loops back to earlier stages, which is what makes the study iterative and "sound."

Verification and Validation

• Verification answers "Did we build the model right?" It checks that the computer program correctly implements the conceptual model — i.e. debugging, ensuring the logic, equations and code are free of errors.
• Validation answers "Did we build the right model?" It checks that the model is an accurate representation of the real system for the intended purpose, usually by comparing model output with the behaviour of the actual system.

Three-Step Approach for Valid & Credible Models (Naylor and Finger)

Step 1 – Build a model with high face validity. Construct the model so that, on its face, it appears reasonable to people knowledgeable about the system. This is achieved by:

• Involving the end-user/system experts at every stage.
• Using all existing knowledge and intuition about the system.
• Performing structured walkthroughs of the model assumptions with experts.

Step 2 – Validate the model assumptions. Assumptions fall into two classes:

• Structural assumptions – how the system operates (e.g. queue discipline FIFO, number of servers). Validated by observing the real system and interviewing personnel.
• Data assumptions – the input probability distributions and their parameters. Validated by collecting reliable data, fitting distributions, and applying goodness-of-fit tests (e.g. chi-square, Kolmogorov–Smirnov).

Step 3 – Validate input–output transformations. Treat the model as a black box and check whether, for the same inputs, the model produces outputs close to those of the real system. Techniques include comparing simulated outputs with historical system data and using statistical tests (e.g. confidence intervals, the two-sample t-test, or the Turing test where experts try to distinguish model output from real output).

Together these steps build a model that is both valid (accurate) and credible (believed and used by decision makers).

Mid-Square Method

A method to generate pseudo-random numbers proposed by von Neumann. Starting from a seed $X_0$ (an $n$-digit number):

1. Square the current number $X_i$.
2. Take the middle $n$ digits of the (zero-padded) square; this is the next number $X_{i+1}$.
3. The random number in $[0,1)$ is $R_i = X_{i+1}/10^{n}$.

Example ($n=4$, seed $X_0 = 7182$): $7182^2 = 51\,581\,124 \Rightarrow$ middle four digits $= 5811 \Rightarrow R_0 = 0.5811$, then square 5811, etc.

Drawback: it tends to degenerate to zero or fall into short cycles, so it is rarely used in practice.

Additive Congruential Method

A random-number generator that produces the next number by adding previous terms (a generalisation of the Fibonacci/lagged generator):

It requires $k$ seed values $X_1, X_2, \dots, X_k$. The simplest case ($k=1$) is

It is fast (only addition is needed) and can give very long periods, but the choice of $m$ and the lags must be made carefully to ensure good statistical (uniformity and independence) properties.

Basic System Concepts in Simulation

Using a bank as a running example:

• Entity – an object of interest in the system. Static entities (e.g. the bank counter/server) stay in the system; dynamic entities (e.g. customers) move through it.
• Attribute – a property or characteristic of an entity. Example: a customer's account balance, priority, or arrival time.
• Activity – a duration of time of specified length (a time period whose duration is known when it begins). Example: the service time a teller takes to serve a customer.
• Event – an instantaneous occurrence that may change the state of the system. Example: the arrival of a customer or the completion of service. (Events are endogenous if generated within the system, exogenous if from the environment.)
• State of the system – the collection of variables necessary to describe the system at any time, relative to the study objectives. Example: number of busy tellers and number of customers waiting in the queue.

Importance of Output Analysis

Simulation output is random because the inputs (inter-arrival and service times) are random variates. A single run is just one sample path, so its results are merely point estimates that vary from run to run. Output analysis is the statistical examination of simulation data to:

• Estimate true performance measures (mean delay, utilization, throughput).
• Build confidence intervals that quantify the precision of those estimates.
• Determine the required number of replications / run length and the warm-up period.
• Compare alternative system designs with statistical validity.

Without output analysis, conclusions could be drawn from random noise rather than real system behaviour.

Terminating vs. Steady-State Simulation

Poisson Distribution

A discrete distribution giving the probability of a number of events occurring in a fixed interval when events happen independently at a constant average rate $\lambda$:

Its mean and variance both equal $\lambda$. In queuing it models the number of arrivals in a given time period.

Exponential Distribution

A continuous distribution describing the time between successive events of a Poisson process, with rate $\lambda$:

Its mean is $1/\lambda$. Its key property is memorylessness: $P(T > s+t \mid T > s) = P(T > t)$.

Role in Queuing Simulation

• If arrivals are Poisson with rate $\lambda$, then the inter-arrival times are exponential with mean $1/\lambda$ — the two distributions are two views of the same process.
• Exponential service times combined with Poisson arrivals give the classic M/M/1 queue, which has a tractable analytic solution and is the standard model used to drive and validate queuing simulations.
• The memoryless property makes the system a Markov process, simplifying both analysis and the generation of event times (inter-arrival/service times are sampled as exponential variates).

Features of a General-Purpose Simulation Language (GPSS)

GPSS (General Purpose Simulation System) is a process/transaction-oriented, block-structured discrete-event simulation language. Its main features:

• Transaction (process) orientation – dynamic entities called transactions flow through a network of blocks that represent the operations of the system; the modeller describes the system rather than the simulation control logic.
• Built-in blocks – ready-made building blocks such as GENERATE (create transactions), QUEUE/DEPART (collect queue statistics), SEIZE/RELEASE (use a facility/server), ADVANCE (impose a service delay), and TERMINATE (remove transactions).
• Automatic clock and event management – the language automatically maintains the simulation clock, the future-event list and time advance; the user does not write the time-advance algorithm.
• Built-in random-number generators and distributions for inter-arrival and service times.
• Automatic statistics collection – facility utilization, queue lengths, waiting times and transit times are gathered and reported automatically.
• Entities such as facilities, storages, queues, logic switches, and savevalues are provided.
• Rapid model development – high-level constructs greatly reduce coding effort compared with a general programming language, at the cost of some flexibility.

Chi-Square Test for Uniformity

The chi-square ($\chi^2$) test is a frequency (goodness-of-fit) test that checks whether generated random numbers in $[0,1)$ are uniformly distributed.

Hypotheses: $H_0$: the numbers are uniform on $[0,1)$; $H_1$: they are not.

Procedure:

1. Divide $[0,1)$ into $n$ equal sub-intervals (classes).
2. Count the observed frequency $O_i$ of numbers falling in each class.
3. Compute the expected frequency $E_i = N/n$ for $N$ numbers and $n$ classes (equal because of uniformity).
4. Compute the statistic:

5. Compare with the table value $\chi^2_{\alpha,\,n-1}$ at significance level $\alpha$ and $n-1$ degrees of freedom.
6. Decision: if $\chi^2_0 \le \chi^2_{\alpha,n-1}$, do not reject $H_0$ (numbers are uniform); otherwise reject.

Example: Suppose $N = 100$ random numbers are placed into $n = 10$ equal intervals, so $E_i = 100/10 = 10$. Observed counts are:

With $n-1 = 9$ d.f. and $\alpha = 0.05$, the table value $\chi^2_{0.05,9} = 16.919$. Since $3.0 \le 16.919$, we do not reject $H_0$ — the numbers are uniformly distributed.

Classification of Simulation Models

Models are commonly classified along three dimensions:

1. Static vs. Dynamic

• Static model – represents a system at a single point in time (time plays no role). Example: a Monte Carlo model to estimate $\pi$ or evaluate an integral.
• Dynamic model – represents a system as it evolves over time. Example: a queuing/bank model tracking customers through the day.

2. Deterministic vs. Stochastic

• Deterministic model – contains no random variables; a given set of inputs always produces the same output. Example: a fixed-rate chemical reaction or a known-schedule process.
• Stochastic model – contains one or more random (probabilistic) variables, so outputs are themselves random and must be treated as estimates. Example: arrivals at a bank with random inter-arrival and service times.

3. Continuous vs. Discrete

• Continuous model – state variables change continuously with respect to time, usually described by differential equations. Example: flow of water in a dam, fluid level in a tank.
• Discrete model – state variables change only at discrete (countable) points in time. Example: number of customers in a queue, which changes only at arrival/departure events.

Most simulation studies in this course deal with dynamic, stochastic, discrete systems (i.e. discrete-event simulation).

Tests for Randomness

Generated numbers must satisfy two properties: uniformity (every value in $[0,1)$ equally likely) and independence (no correlation between successive numbers). Statistical tests check these:

• Frequency tests – test uniformity (e.g. chi-square, Kolmogorov–Smirnov).
• Runs test, autocorrelation test, gap test, poker test – test independence.

Frequency Test — Kolmogorov–Smirnov (K-S) Test

Tests whether the empirical (sample) cumulative distribution of the numbers matches the theoretical uniform CDF $F(x) = x$ on $[0,1)$.

Procedure:

1. Sort the $N$ numbers in ascending order: $R_{(1)} \le R_{(2)} \le \dots \le R_{(N)}$.
2. Compute the largest deviations above and below:

3. Compute $D = \max(D^{+}, D^{-})$.
4. Compare with the critical value $D_{\alpha}$ from the K-S table. If $D \le D_{\alpha}$, the hypothesis of uniformity is not rejected.

The K-S test is exact and works well even for small samples, unlike the chi-square test.

Runs Test

Tests independence by examining the sequence of numbers for runs — maximal subsequences of consecutive numbers that are increasing (a run up) or decreasing (a run down).

Procedure (runs up and down):

1. Write a + if a number is larger than the previous one and − if smaller.
2. Count the total number of runs $a$ (a run = a maximal block of same sign).
3. For $N$ numbers, under independence the expected number of runs and its variance are:

4. Compute the standardized statistic $Z_0 = \dfrac{a - \mu_a}{\sigma_a}$.
5. If $|Z_0| \le z_{\alpha/2}$ (e.g. $1.96$ at $\alpha = 0.05$), the numbers are independent; too few or too many runs indicates dependence.

Basic Properties of Random Numbers

A sequence of random numbers $R_1, R_2, \dots$ (each in the interval $[0,1)$) used in simulation must have two fundamental statistical properties:

1. Uniformity

The numbers are uniformly distributed over $[0,1)$: every value (or sub-interval of equal width) is equally likely. Formally the PDF is

with mean $E[R] = 1/2$ and variance $\operatorname{Var}(R) = 1/12$. If we divide $[0,1)$ into $n$ equal classes, each should contain about $N/n$ of the $N$ numbers.

2. Independence

Each random number is statistically independent of the others: the value of $R_i$ gives no information about the value of $R_j$ ($i \ne j$). There should be no correlation between successive numbers — no patterns, trends or cycles.

A generator that satisfies both properties is acceptable; uniformity is checked with frequency tests (chi-square, Kolmogorov–Smirnov) and independence with the runs, autocorrelation, gap and poker tests.