BE Computer Engineering (IOE, TU) Simulation and Modeling (IOE, CT 751 / ENCT 353) Question Paper 2079 Nepal

(a) System, Model, and Types of Models

System: A system is a collection of entities (objects) that interact together over time to accomplish one or more goals. Example: a bank with tellers, customers and a queue is a system.

Model: A model is a simplified representation (abstraction) of a system used to study and predict the behaviour of that system without operating on the real system itself.

Physical vs. Mathematical models

Static vs. Dynamic models

(b) When is simulation the right tool?

The statement is largely true but incomplete. Simulation is indeed preferred when a system is too complex for closed-form analytical solutions, but complexity is not the only criterion.

Simulation IS appropriate when:

• The system is too complex (non-linear, many interacting random components) for analytical/mathematical solution.
• We want to study the dynamic behaviour and transient effects over time.
• We wish to experiment with "what-if" scenarios or new policies/designs before building the real system.
• It is too costly, dangerous or impossible to experiment on the real system.
• We want to verify or gain insight into an analytical solution.

Simulation is NOT appropriate when:

• The problem can be solved exactly by closed-form analytical methods (e.g. simple M/M/1 formulas) — analysis is then cheaper and exact.
• The cost of building/running the simulation exceeds the benefit, or there is insufficient time/resources/data.
• Common sense or direct measurement gives the answer more easily.
• The system behaviour can be observed directly and cheaply on the real system.
• Adequate input data are unavailable, so the model cannot be validated.

Conclusion: Simulation is a powerful last-resort tool when analysis fails, but when an exact analytical solution exists it should be preferred for accuracy and economy.

(a) Event-Scheduling Approach

In the event-scheduling / next-event time-advance approach, the simulation clock jumps from the time of one event directly to the time of the next event. At each event, the system state is updated, statistics are collected, and any future events generated are placed in the event list.

• Event: an instantaneous occurrence that may change the state of the system (e.g. an arrival or a departure).
• Event list (FEL): an ordered list of future events with their scheduled times of occurrence; the imminent event (smallest time) is processed next.
• System state: the collection of variables that describe the system at any time (e.g. number in queue, server busy/idle).
• Simulation clock: a variable giving the current value of simulated time; it advances to the time of the next (imminent) event.

(b) Hand Simulation Table

Inter-arrival times (IAT): 3, 1, 4, 2, 5. Service times (ST): 2, 4, 1, 3, 2.

Arrival time $A_i = \sum IAT$. Service start $= \max(A_i, \text{prev. departure})$. Departure $=$ start $+$ ST.

Average waiting time in queue:

$$\bar W_q = \frac{0+1+1+0+0}{5} = \frac{2}{5} = 0.4 \text{ min}$$

Average time in system:

$$\bar W = \frac{2+5+2+3+2}{5} = \frac{14}{5} = 2.8 \text{ min}$$

Server utilization = total busy time / total simulation time. Total service time $= 2+4+1+3+2 = 12$ min. The first customer arrives at $t=3$ and the last departs at $t=17$, so the simulation run length is $17$ min (server idle 3 min at start, plus idle gaps).

$$\rho = \frac{12}{17} \approx 0.706 \;(70.6\%)$$

(If utilization is measured only over the busy period from first arrival $t=3$ to last departure $t=17$, the same value $12/14 \approx 0.857$ may be quoted if idle start time is excluded; either consistent definition is acceptable.)

(a) Linear Congruential Method (LCG)

The LCG generates a sequence of integers $X_0, X_1, X_2,\dots$ using the recurrence:

$$X_{i+1} = (a\,X_i + c)\bmod m, \qquad i = 0,1,2,\dots$$

where $X_0$ is the seed, $a$ is the multiplier, $c$ is the increment and $m$ is the modulus. The pseudo-random numbers on $[0,1)$ are obtained as:

$$R_i = \frac{X_i}{m}$$

If $c \ne 0$ it is a mixed LCG; if $c = 0$ it is a multiplicative LCG.

Hull–Dobell theorem (maximum period $= m$): A mixed LCG ($c \ne 0$) has full period $m$ if and only if:

1. $\gcd(c, m) = 1$ (i.e. $c$ and $m$ are relatively prime);
2. $a - 1$ is divisible by every prime factor of $m$;
3. $a - 1$ is divisible by $4$ if $m$ is divisible by $4$.

(b) Inverse-Transform for the Exponential Distribution

The exponential distribution with mean $1/\lambda$ has cdf:

$$F(x) = 1 - e^{-\lambda x}, \quad x \ge 0$$

Procedure: Set $F(X) = R$ where $R \sim U(0,1)$ and solve for $X$:

$$R = 1 - e^{-\lambda X} \Rightarrow e^{-\lambda X} = 1 - R \Rightarrow X = -\frac{1}{\lambda}\ln(1 - R)$$

Since $1-R$ is also $U(0,1)$, this is often written $X = -\frac{1}{\lambda}\ln R$.

Numerical generation with $R = 0.25$, $\lambda = 0.5$:

$$X = -\frac{1}{0.5}\ln(1 - 0.25) = -2\ln(0.75) = -2(-0.28768) = 0.5754$$

The generated exponential variate is $X \approx 0.575$.

(a) Verification vs. Validation

Verification asks "Did we build the model right?" — it ensures that the computer program (the operational model) correctly implements the conceptual/assumptions model, i.e. it is free of logical and coding errors.

Validation asks "Did we build the right model?" — it ensures that the model is an accurate representation of the real system for its intended purpose.

Verification techniques (any three):

1. Structured walk-through / code review of the program with another person, checking flowcharts against code.
2. Trace the simulation — print intermediate values (clock, state, event list) for a few entities and check them by hand.
3. Test under simplified/known conditions for which analytical results exist (e.g. deterministic service times) and compare.
4. Use animation to visually observe that entities behave as intended.

Validation techniques (any three):

1. Compare model output with real-system data (historical/field data) using statistical tests.
2. Face validity — have experts/operators of the real system judge whether outputs and behaviour look reasonable.
3. Sensitivity analysis / Turing test — vary inputs and check the direction/magnitude of output changes match reality; or see if experts can distinguish model output from real output.
4. Validate model assumptions (structural and data assumptions) against the real system.

(b) General-Purpose vs. Special-Purpose Simulation Languages

Kolmogorov–Smirnov Test for Uniformity

Step 1 — Sort the numbers ascending:

$$0.05,\; 0.14,\; 0.44,\; 0.81,\; 0.93 \quad (n=5)$$

Step 2 — Compute $D^{+}$ and $D^{-}$ using $D^{+}=\max\big(\tfrac{i}{n}-R_{(i)}\big)$ and $D^{-}=\max\big(R_{(i)}-\tfrac{i-1}{n}\big)$.

Step 3 — Test statistic:

$$D^{+} = 0.26,\qquad D^{-} = 0.21$$ $$D = \max(D^{+}, D^{-}) = 0.26$$

Step 4 — Decision: Compare with the critical value $D_{0.05} = 0.565$.

$$D = 0.26 < 0.565 = D_{0.05}$$

Conclusion: Since the computed $D$ is less than the critical value, we fail to reject the null hypothesis. The numbers can be regarded as drawn from a uniform $U(0,1)$ distribution at the 5% level of significance.

M/M/1 Queue Performance Measures

Given $\lambda = 6$ /hr and $\mu = 8$ /hr.

(a) Server utilization $\rho$:

$$\rho = \frac{\lambda}{\mu} = \frac{6}{8} = 0.75 \;(75\%)$$

Since $\rho < 1$, the queue is stable.

(b) Expected number in the system $L$:

$$L = \frac{\rho}{1-\rho} = \frac{\lambda}{\mu - \lambda} = \frac{6}{8-6} = \frac{6}{2} = 3 \text{ customers}$$

(c) Expected waiting time in the queue $W_q$:

$$W_q = \frac{\lambda}{\mu(\mu-\lambda)} = \frac{6}{8(8-6)} = \frac{6}{16} = 0.375 \text{ hr} = 22.5 \text{ minutes}$$

Summary: $\rho = 0.75$, $L = 3$ customers, $W_q = 0.375$ hr ($22.5$ min).

Acceptance–Rejection Technique

The acceptance–rejection method generates variates from a target density $f(x)$ when direct inversion is difficult. The idea is to generate candidate points uniformly under a bounding envelope and accept only those that fall under $f(x)$; rejected points are discarded.

Case: $f(x)$ bounded on a finite interval $[a,b]$. Let $c = \max_{a\le x\le b} f(x)$ be an upper bound on the density. We enclose $f$ in the rectangle $[a,b]\times[0,c]$.

Algorithm:

1. Generate two independent uniform random numbers R1, R2 ~ U(0,1).
2. Set candidate X = a + (b - a) * R1.        // uniform on [a,b]
3. Set Y = c * R2.                             // uniform on [0,c]
4. If Y <= f(X):
       Accept and RETURN X.                    // point lies under f
   Else:
       Reject and go back to Step 1.            // try again

Why it works: Conditioned on acceptance ($Y \le f(X)$), the accepted $X$ has density proportional to $f(x)$, hence exactly the target distribution. The efficiency (probability of acceptance per trial) is

$$P(\text{accept}) = \frac{\int_a^b f(x)\,dx}{c\,(b-a)} = \frac{1}{c\,(b-a)},$$

so a tight bound $c$ (envelope close to $f$) minimizes rejections and maximizes efficiency.

Continuous vs. Discrete and Deterministic vs. Stochastic Simulation

Continuous vs. Discrete simulation

Deterministic vs. Stochastic simulation

Properties of Good Pseudo-Random Numbers and the Runs Test

Desirable properties of a good random-number sequence:

1. Uniformity — the numbers are uniformly distributed on $[0,1)$.
2. Independence — the numbers are statistically independent (no correlation/pattern between successive values).
3. Long period (cycle length) before the sequence repeats.
4. Reproducibility — the sequence can be regenerated from the same seed.
5. Computational efficiency — fast to generate and low memory use.

Runs Test (test for independence): A run is a succession of numbers in the same direction. The runs up and down test counts a run as a maximal subsequence of increasing (up) or decreasing (down) values; a sign change marks the end of a run. We count the total number of runs $a$ in the sequence.

For $n$ numbers, under independence the expected number of runs and its variance are

$$\mu_a = \frac{2n-1}{3}, \qquad \sigma_a^2 = \frac{16n-29}{90}.$$

The test statistic

$$Z = \frac{a - \mu_a}{\sigma_a}$$

is approximately standard normal. If $|Z| \le Z_{\alpha/2}$ we do not reject.

Hypothesis tested: It tests $H_0$: the numbers in the sequence are independent (no pattern/correlation), against $H_1$: the numbers are not independent. Too few or too many runs indicates dependence.

Next-Event Time-Advance Discrete-Event Simulation

In the next-event time-advance mechanism the simulation clock is advanced to the time of the most imminent future event (not in fixed increments). At each step the state is updated, statistics gathered, and new future events scheduled, until a stopping condition is met.

Main steps / flowchart (described in words):

      ┌─────────────────────────────┐
      │   START: Initialization      │
      │  - set clock = 0             │
      │  - set initial system state  │
      │  - initialize statistics     │
      │  - schedule initial event(s) │
      └──────────────┬──────────────┘
                     ▼
      ┌─────────────────────────────┐
      │  Determine the imminent      │◄──────────┐
      │  (next) event from the       │           │
      │  Future Event List (FEL)     │           │
      └──────────────┬──────────────┘           │
                     ▼                           │
      ┌─────────────────────────────┐           │
      │  Advance simulation clock to │           │
      │  the time of that event      │           │
      └──────────────┬──────────────┘           │
                     ▼                           │
      ┌─────────────────────────────┐           │
      │  Execute event routine:      │           │
      │  - update system state       │           │
      │  - update statistics         │           │
      │  - generate & schedule future│           │
      │    events into the FEL       │           │
      └──────────────┬──────────────┘           │
                     ▼                           │
            ◇ Stopping condition met? ◇──No──────┘
                     │ Yes
                     ▼
      ┌─────────────────────────────┐
      │  Generate report / compute   │
      │  summary statistics; STOP    │
      └─────────────────────────────┘

Summary: Initialize → find imminent event → advance clock to it → process event (update state, stats, schedule new events) → repeat until termination → produce report.

System Modeling Terms

(a) Entity: An object of interest in the system. It may be dynamic (moving through the system, e.g. a customer, a part) or permanent (e.g. a server, a machine).

(b) Attribute: A property or characteristic of an entity. Example: the arrival time, priority or service requirement of a customer; the speed of a machine.

(c) Activity: A duration of time of specified (often known) length during which something happens. Example: a service activity lasting the service time; an inter-arrival activity.

(d) State of a system: The collection of variables (state variables) necessary to describe the system at any instant of time relative to the objectives of the study. Example: the number of busy servers and the number of customers in the queue.

(e) Endogenous and exogenous events:

• Endogenous event — an activity or event occurring within the system. Example: the completion of service (a departure) inside a bank.
• Exogenous event — an activity or event in the environment that affects the system from outside. Example: the arrival of a customer to the bank.

Short Notes (any TWO)

(a) Monte Carlo Simulation

Monte Carlo simulation is a static simulation technique that uses repeated random sampling to obtain numerical results for problems that may be deterministic or stochastic, where time plays no substantive role. Random numbers are used to sample from probability distributions, and many trials are averaged to estimate a quantity. A classic use is estimating $\pi$ by throwing random points into a unit square and counting how many fall inside the inscribed quarter-circle: $\pi \approx 4\times(\text{fraction inside})$. It is also used for numerical integration, risk analysis and reliability estimation. Accuracy improves with the number of trials (error $\propto 1/\sqrt{N}$).

(b) Features of a Good Simulation Software Package

A good simulation package should provide:

• Modeling flexibility and ease of building/modifying models (graphical/drag-and-drop modeling).
• Built-in random-number and random-variate generators for standard distributions.
• Built-in statistical analysis of output (confidence intervals, multiple replications).
• Animation to visualize and verify model behaviour.
• Good input data analysis (distribution fitting) facilities.
• Run control, debugging/trace tools and clear reporting.
• Good documentation, support, portability and reasonable execution speed.

(c) Calibration of a Model in the Validation Process

Calibration is the iterative process of tuning a model's parameters and assumptions so that its output matches the behaviour of the real system as closely as possible. The modeler compares model output with observed real-system data, identifies discrepancies, adjusts parameters/structure, and repeats. Care must be taken to avoid over-fitting the model to one particular data set; therefore the calibrated model should be re-tested (validated) against a separate, independent data set to confirm it generalizes. Calibration is thus a key sub-step within validation.