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

The MARK and TABULATE Blocks in GPSS

MARK Block

The MARK block places (marks) the current value of the simulation clock into a transaction's parameter or into its Mark Time field (the M1 parameter). It is used to record the time at which a transaction passes a particular point so that the transit/residence time can later be measured.

• Syntax: MARK [A] where the optional operand A names the parameter in which the time stamp is stored. If A is omitted, the transaction's mark time is reset.
• Combined with the transit time system attribute M1 (current clock minus mark time), it lets us measure how long a transaction has spent in part of the model.

TABULATE Block

The TABULATE block enters a value into a previously defined TABLE (a frequency/histogram table declared by the TABLE statement). It is used to collect statistics such as the distribution of waiting or transit times.

• Syntax: TABULATE A[,B] where A is the table name and B is an optional weighting count.
• When a transaction enters a TABULATE block, the argument of the referenced TABLE (often the transit time M1) is recorded, building a histogram with mean, standard deviation and frequency classes that GPSS prints automatically.

Together, MARK stamps a start time and TABULATE (using M1 against a TABLE) records the elapsed time, giving the distribution of transit times.

Coffee Shop Simulation Model

System description:

• Single barista (one server) -> model as a FACILITY.
• Customers arrive on average every 3 minutes -> exponential inter-arrival time, mean 3.
• Service takes on average 2.5 minutes -> exponential service time, mean 2.5.
• Simulate for 8 hours = 480 minutes.

Traffic intensity $\rho = \lambda/\mu = (1/3)/(1/2.5) = 2.5/3 \approx 0.83$, so the system is stable.

Block Diagram

      +-----------------------+
      |   GENERATE 3,FN$XPDIS |   customers arrive (mean 3 min)
      +-----------------------+
                 |
      +-----------------------+
      |        QUEUE WAIT     |   join waiting line, start timing
      +-----------------------+
                 |
      +-----------------------+
      |      SEIZE  BARISTA   |   capture the single barista
      +-----------------------+
                 |
      +-----------------------+
      |       DEPART WAIT     |   leave the queue (served)
      +-----------------------+
                 |
      +-----------------------+
      |  ADVANCE 2.5,FN$XPDIS |   being served (mean 2.5 min)
      +-----------------------+
                 |
      +-----------------------+
      |     RELEASE BARISTA   |   free the barista
      +-----------------------+
                 |
      +-----------------------+
      |       TERMINATE 0     |   customer leaves
      +-----------------------+

   Timer segment:
      GENERATE 480  ->  TERMINATE 1   (ends run after 480 min)

GPSS Program

* Coffee shop: single barista, 8-hour (480 min) simulation
* Exponential distribution function (XPDIS) defined via GPSS function
XPDIS  FUNCTION  RN1,C24      ; exponential distribution function
0,0/.1,.104/.2,.222/.3,.355/.4,.509/.5,.69/.6,.915
.7,1.2/.75,1.38/.8,1.6/.84,1.83/.88,2.12/.9,2.3
.92,2.52/.94,2.81/.95,2.99/.96,3.2/.97,3.5/.98,3.9
.99,4.6/.995,5.3/.998,6.2/.999,7.0/.9997,8.0
*
WTIME  TABLE     M1,0,2,20    ; histogram of transit (waiting) times
*
         GENERATE  3,FN$XPDIS   ; arrivals, mean 3 min
         MARK      1            ; stamp arrival time in P1
         QUEUE     WAIT         ; enter waiting line
         SEIZE     BARISTA      ; capture barista
         DEPART    WAIT         ; served, leave queue
         ADVANCE   2.5,FN$XPDIS ; service, mean 2.5 min
         RELEASE   BARISTA      ; release barista
         TABULATE  WTIME        ; record transit time (M1)
         TERMINATE 0
*
         GENERATE  480          ; timer transaction after 480 min
         TERMINATE 1
*
         START     1            ; run until 1 timer terminates

Expected output (interpretation): GPSS automatically reports the barista's utilization (about 0.83), the average and maximum queue length at QUEUE WAIT, the average waiting time, and the transit-time histogram from the WTIME table. Because $\rho\approx0.83$ is close to 1, the model will show appreciable queueing.

What is Simulation?

Simulation is the technique of imitating the operation of a real-world system or process over time by means of a model. A model is built to represent the system, and the model is then driven (often using random inputs) to generate an artificial history of the system from which estimates of performance measures are drawn.

• It is used when a system is too complex for an analytical (closed-form) solution.
• It allows "what-if" experimentation without disturbing or building the real system.
• Simulation models are typically dynamic, stochastic and run on a computer.

Dynamic Physical Models and the Mechanical–Electrical Analogy

A dynamic physical model is a physical (tangible) model in which the behaviour of one physical system is studied using another physical system that is governed by the same mathematical equations. Two systems are called analogous when their describing differential equations have the same form; the variables of one map onto the variables of the other. This lets engineers study a difficult mechanical system by building/measuring an easier-to-handle electrical circuit.

Mechanical System (mass–spring–damper)

Consider a mass $M$ attached to a spring (stiffness $K$) and a damper (damping coefficient $D$), pushed by an external force $F(t)$. By Newton's second law:

where $x$ is displacement.

        F(t)
         |
   +-----v-----+
   |   MASS M  |---/\/\/\--- spring K
   +-----------+---[ D ]---- damper
         x (displacement)

Corresponding Electrical System (series RLC circuit)

A series circuit with inductance $L$, resistance $R$ and capacitance $C$ driven by voltage $E(t)$ obeys (with charge $q$):

   E(t) --[ L ]--[ R ]--[ C ]--+
     |__________________________|

The Analogy

The two equations are identical in form, so the systems are analogous with the following correspondence:

Significance: Because the equations match, the response of the mechanical system can be studied by building and measuring the electrical circuit (which is cheaper, faster and easier to instrument). This is the basis of analog computers and dynamic physical modelling — measuring voltages/currents to predict displacements/forces.

Properties of Random Numbers

A sequence of random numbers $R_1, R_2, \dots$ (each in $[0,1]$) must satisfy two key properties:

1. Uniformity: The numbers are uniformly distributed over $[0,1]$. If the interval is split into $n$ equal sub-intervals, each is expected to contain $N/n$ of the $N$ numbers. The density is $f(x)=1$ for $0\le x\le 1$, with mean $1/2$ and variance $1/12$.
2. Independence: Each number is statistically independent of every other; the current value gives no information about any other value (no correlation/autocorrelation).

Autocorrelation Test for Independence

The autocorrelation test checks independence by measuring the correlation between numbers that are a fixed distance (lag $m$) apart, starting at index $i$.

Test setup: $i = 2$, $m = 3$, $N = 20$, $\alpha = 0.05$, $Z_{\alpha/2}=1.96$.

Step 1 — Find M (number of pairs). $M$ is the largest integer such that $i + (M+1)m \le N$:

Step 2 — Identify the subsequence (indices $i, i+m, i+2m, \dots, i+(M+1)m$ = 2, 5, 8, 11, 14, 17, 20):

Step 3 — Compute the autocorrelation estimator $\hat{\rho}_{im}$:

Products of consecutive terms in the subsequence:

Step 4 — Standard deviation of the estimator:

Step 5 — Test statistic:

Step 6 — Decision. Since $|Z_0| = 0.579 \le Z_{\alpha/2} = 1.96$, we fail to reject the null hypothesis $H_0: \rho_{im}=0$.

Conclusion: There is no evidence of significant autocorrelation at lag 3 starting from index 2; the numbers can be considered independent at the 5% significance level.

Static Mathematical Model

A mathematical model represents a system using symbols, variables, equations and logical/mathematical relationships rather than a physical replica. A static mathematical model is one that represents the system at a single point in time (or one in which time plays no role) — it gives the relationship between system variables in an equilibrium or steady condition, ignoring how the system evolves over time.

Key characteristics:

• Time is not a variable in the model.
• Describes the system in equilibrium / at one instant.
• Often solved directly (algebraically) for the unknowns.
• Contrasts with a dynamic model, where the state changes with time (described by differential/difference equations).

Suitable Example: Supply and Demand (Market Equilibrium)

Consider a market where, for price $P$:

• Demand: $Q_d = a - bP$
• Supply: $Q_s = c + dP$

At equilibrium, demand equals supply ($Q_d = Q_s$):

This gives the equilibrium price $P^*$ at one point in time — there is no notion of how the price reaches equilibrium over time, so it is a static mathematical model.

Other examples:

• Linear programming for product mix (maximize profit subject to fixed resource constraints).
• Monte Carlo estimation of a definite integral (e.g. estimating $\pi$), where sampling represents the system at a fixed state with no time dimension.
• Ohm's law $V = IR$ for a resistor at steady state.

Markov Chain — Definition

A Markov chain is a stochastic (random) process $\{X_n\}$ that moves among a finite or countable set of states such that the probability of moving to the next state depends only on the current state and not on the sequence of states that preceded it. This is the Markov (memoryless) property:

• The values $p_{ij}$ are the one-step transition probabilities.
• They form a transition probability matrix $P$ where every row sums to 1.
• The $n$-step transition probabilities are given by $P^n$, and the long-run steady-state distribution $\pi$ satisfies $\pi = \pi P$ with $\sum_i \pi_i = 1$.

Suitable Example: Weather Model

Let the weather each day be either Sunny (S) or Rainy (R). Suppose:

• If today is Sunny: 80% chance Sunny tomorrow, 20% chance Rainy.
• If today is Rainy: 40% chance Sunny tomorrow, 60% chance Rainy.

State diagram:

        0.8                0.6
       /---\              /---\
       \   v     0.2      v   /
        ( S ) ---------> ( R )
            <---------
               0.4

Steady state: Solving $\pi = \pi P$ with $\pi_S + \pi_R = 1$:

With $\pi_S + \pi_R = 1$: $\pi_R = 1/3,\ \pi_S = 2/3$. In the long run about 2/3 of days are Sunny and 1/3 Rainy, independent of the starting day.

Markov chains are widely used in simulation for modelling machine up/down status, inventory levels, queue states and brand-switching behaviour.

Non-Stationary Poisson Process (NSPP)

A Poisson process is a counting process in which events occur randomly and independently over time at a constant average rate $\lambda$, with the number of events in any interval following a Poisson distribution. In a stationary (homogeneous) Poisson process this rate $\lambda$ is constant over time.

A Non-Stationary Poisson Process (NSPP) — also called a non-homogeneous Poisson process — is a Poisson process in which the arrival rate varies with time, i.e. the rate is a function $\lambda(t)$ instead of a constant.

Key points:

• The rate function $\lambda(t)$ captures time-of-day / seasonal variation in arrivals.
• The expected number of arrivals in the interval $[a, b]$ is the integral of the rate:

• The cumulative function $\Lambda(t) = \int_0^t \lambda(s)\,ds$ is the expected number of arrivals by time $t$.
• Arrivals in non-overlapping intervals are still independent, but no longer stationary (counts depend on when the interval is, not just its length).

Realistic use / example: Customer arrivals at a restaurant, calls to a help desk, or traffic on a road are heavier at peak hours and lighter at off-peak times. For instance, $\lambda(t)$ might be 2 customers/min at lunchtime but 0.5/min in mid-afternoon. Modelling this as an NSPP is far more realistic than assuming a single constant rate.

Generating NSPP arrivals (thinning): Pick a constant $\lambda^* \ge \max \lambda(t)$, generate stationary Poisson arrivals at rate $\lambda^*$, and accept each candidate arrival at time $t$ with probability $\lambda(t)/\lambda^*$ (reject otherwise). The accepted times form the NSPP.

Random Variate Generation Techniques

Random variates are values drawn from a specified probability distribution, generated from uniform $U(0,1)$ random numbers. Two fundamental techniques are the inverse transform technique and the acceptance-rejection technique.

1. Inverse Transform Technique

This method uses the fact that if $X$ has CDF $F(x)$, then $F(X)$ is uniformly distributed on $[0,1]$. So we set the CDF equal to a uniform number $R$ and invert.

Steps:

1. Derive the CDF $F(x)$ of the desired distribution.
2. Set $F(X) = R$, where $R \sim U(0,1)$.
3. Solve for $X$: $X = F^{-1}(R)$.

Example (exponential, rate $\lambda$): $F(x) = 1 - e^{-\lambda x}$.

Pros: simple, efficient (one uniform per variate), good when $F^{-1}$ is known in closed form. Cons: unusable when the CDF cannot be inverted analytically (e.g. the normal distribution).

2. Acceptance–Rejection Technique

Used when the inverse of the CDF is hard to obtain. It generates candidate values from an easy distribution and accepts only those that fall under the desired density $f(x)$.

Steps (for a density $f(x)$ on $[a,b]$ bounded by $c \ge \max f(x)$):

1. Generate $R_1 \sim U(0,1)$ and form a candidate $X = a + (b-a)R_1$.
2. Generate $R_2 \sim U(0,1)$.
3. If $R_2 \le \dfrac{f(X)}{c}$, accept $X$; otherwise reject and return to step 1.

Example: Generate a variate with $f(x)=2x$ on $[0,1]$ (here $c=2$): pick $X=R_1$, accept if $R_2 \le 2X/2 = X$.

Pros: works for almost any density, including ones with no closed-form inverse. Cons: can be inefficient — many candidates may be rejected, requiring more uniform numbers; efficiency depends on how tightly the bound $c$ fits $f(x)$.

Comparison

Iterative Process of Calibrating a Model

Calibration is the iterative process of comparing a model with the real system it represents and adjusting (tuning) the model until its behaviour matches the real system closely enough for the intended purpose. It is a central part of model validation.

The Iterative Loop

  +------------------------------------------------+
  |          Real-System Data / Measurements       |
  +------------------------------------------------+
                 |                       ^
                 v                       |
     +----------------------+            | adjust
     |   Run the Model      |            | parameters/
     |  (current parameters)|            | assumptions
     +----------------------+            |
                 |                       |
                 v                       |
     +----------------------+   No   +-----------+
     | Compare model output |------> | Discrepancy|
     |  vs real-system data |        |  too large?|
     +----------------------+        +-----------+
                 | Yes (acceptable)
                 v
           Model Calibrated

Steps

1. Build the initial model with first estimates of parameters and assumptions.
2. Run the model and obtain its output measures.
3. Compare the model output against measured data from the real system (using graphs, statistical tests, confidence intervals).
4. Identify discrepancies. If the difference is unacceptably large, locate which assumptions, parameters or input distributions are responsible.
5. Adjust the model — refine parameter values, correct structural assumptions, or improve input data.
6. Repeat steps 2–5 until the model's output agrees with the real system within an acceptable tolerance.

Important Notes

• Calibration is done iteratively — usually no single pass produces a valid model.
• Beware of over-fitting / over-tuning to one data set: a model tuned only to one historical data set may fail on new data. Good practice is to calibrate on one data set and validate on an independent data set.
• Calibration involves both objective (statistical comparison) and subjective (expert judgement) elements.

Kendall's Notation

Queuing systems are described by the standard Kendall's notation, written as:

Where each position has a specific meaning:

Common distribution symbols for A and B:

• M = Markovian / exponential (Poisson), memoryless
• D = Deterministic (constant)
• G = General (arbitrary) distribution
• $E_k$ = Erlang-k distribution

Appropriate Examples

• M/M/1 — Poisson arrivals, exponential service, single server, infinite capacity and population. The classic single-server queue, e.g. a single ATM machine.
• M/M/c — Poisson arrivals, exponential service, c servers, e.g. a bank with several tellers sharing one queue.
• M/D/1 — Poisson arrivals, constant service time, one server, e.g. an automated car wash that takes a fixed time per car.
• M/M/1/N — single-server queue with limited capacity $N$, e.g. a small clinic waiting room that can hold only $N$ patients.
• M/G/1 — Poisson arrivals, general service-time distribution, one server.

Worked reading of M/M/1: "M" -> arrivals are Poisson (exponential inter-arrival times); "M" -> service times are exponential; "1" -> one server; capacity and population are both infinite (omitted) and discipline is FIFO by default.

Hybrid Simulation

Hybrid simulation is a simulation approach that combines two or more simulation paradigms (or continuous and discrete techniques) within a single model, so that the strengths of each are used to represent different parts of the same system. It is needed when a system has both continuously changing state variables and discrete events, or when no single modelling style captures the whole system well.

Forms of Hybrid Simulation

1. Combined continuous–discrete (continuous + discrete-event): Some state variables change continuously (described by differential equations), while others change only at discrete event points. The continuous and discrete parts interact — e.g. a continuous variable crossing a threshold triggers a discrete event, and a discrete event changes a rate in the continuous part.
2. Mixing of methods such as Discrete-Event Simulation (DES), System Dynamics (SD) and Agent-Based Modelling (ABM) in one model.
3. Analog–digital (hybrid) computing, historically, where an analog computer handled continuous equations and a digital computer handled logic/discrete control.

Examples

• Chemical / refinery plant: the fluid level and temperature in a tank change continuously (continuous model), while valves opening/closing and batch loading are discrete events. A discrete event (open valve) alters the continuous flow equations, and the continuous level reaching a set point triggers the next discrete event.
• Hospital / healthcare system: patient flow and resource use modelled with discrete-event simulation, while disease progression in the population is modelled with system dynamics — combined into one hybrid model.
• Supply chain: continuous system-dynamics stocks and flows for inventory levels combined with discrete-event modelling of individual orders and shipments.
• Traffic / water systems: continuous flow of water or vehicles plus discrete control actions (traffic lights, gate operations).

Advantage: captures complex real systems more faithfully than a single technique. Drawback: more complex to build, synchronize (the continuous and discrete clocks must be coordinated) and validate.

Feedback System

A feedback system is a system in which a portion of the output is fed back and used as an input to influence and control the system's future behaviour. The fed-back signal is compared with a reference/desired value, and the resulting difference (error) is used to adjust the system so it moves toward the desired state. Feedback makes a system self-regulating.

General Structure

   Reference     +    error      +-----------+   output
   input ------>(  )----------->  |  System / |--------+--->
               - ^               |  Process  |        |
                 |               +-----------+        |
                 |                                    |
                 +------------ Feedback path <--------+

Types of Feedback

1. Negative feedback: the feedback opposes the change, driving the output back toward the reference. It produces stability and self-regulation. (Most control systems.)
2. Positive feedback: the feedback reinforces the change, amplifying the output. It can cause growth or instability.

Suitable Examples

• Thermostat / air-conditioning (negative feedback): the desired temperature is the reference; the room temperature (output) is sensed and fed back. If the room is too warm, the error switches the cooler on; when the temperature reaches the set point, it switches off — keeping temperature stable.
• Cruise control in a car (negative feedback): the actual speed is measured and compared to the set speed; the throttle is adjusted to remove the error, maintaining constant speed despite hills.
• Human body temperature regulation (homeostasis, negative feedback): sweating/shivering brings body temperature back to ~37 deg C.
• Microphone–speaker howl / population explosion (positive feedback): output is amplified back into the input, causing runaway behaviour.
• Economic / inventory systems: sales data (output) feed back to control production and ordering decisions (input).

Relevance to simulation: feedback loops are central to system dynamics models, where stocks, flows and feedback determine dynamic behaviour over time.

a. Mid-Square Method

The Mid-Square method is one of the earliest pseudo-random number generators, proposed by John von Neumann. It generates a sequence of numbers by repeatedly squaring the previous number and extracting the middle digits.

Procedure:

1. Choose an $n$-digit seed $X_0$ (commonly 4 digits).
2. Square it to get a $2n$-digit number (pad with leading zeros if needed).
3. Take the middle $n$ digits as the next number $X_1$.
4. Optionally divide by $10^n$ to get a random number $R_i \in [0,1]$.
5. Repeat using $X_1$ as the new seed.

Example (4-digit seed):

Drawbacks: the sequence may degenerate (collapse to zero or fall into a short repeating cycle), and the period is short. It is mostly of historical interest; modern work uses linear congruential generators.

b. Digital-Analog Simulation

Digital-analog simulation (digital simulation of analog systems) refers to using a digital computer to simulate the behaviour of continuous (analog) systems that are naturally described by differential equations — the kind of problems traditionally solved on analog computers.

Key idea: Analog computers solve continuous problems directly using physical components (integrators, summers, amplifiers) but suffer from limited accuracy and reprogramming difficulty. Digital-analog simulation reproduces the same continuous behaviour on a digital computer by:

• Representing the system's differential equations in the program.
• Using numerical integration methods (e.g. Euler, Runge–Kutta) to approximate the continuous solution step by step over time.
• Optionally using a block-oriented continuous-simulation language (e.g. CSMP, ACSL, Simulink) where the user wires together integrator/gain/summer blocks just as on an analog computer, and the digital engine integrates them numerically.

Advantages over pure analog: higher accuracy, repeatability, easy reprogramming, and the ability to combine with discrete logic (leading to hybrid simulation).

Example: Simulating the mass–spring–damper equation $M\ddot{x} + D\dot{x} + Kx = F(t)$ on a digital computer by numerically integrating it with the Runge–Kutta method is a digital-analog simulation of a continuous physical system.