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

(a) System and its components (6)

System: A system is a collection of entities (people, machines, objects) that interact together over time to accomplish one or more goals. Example: a bank, a factory, a computer network.

Components:

• Entity: An object of interest in the system. Example: a customer in a bank.
• Attribute: A property/characteristic of an entity. Example: the account balance or priority of a customer.
• Activity: A time period of specified length representing an operation. Example: the act of serving a customer (a teller transaction).
• State: The collection of variables needed to describe the system at any instant, relative to the objectives of the study. Example: number of busy tellers and number of customers waiting.
• Event: An instantaneous occurrence that may change the state of the system. Example: the arrival of a customer or the completion of service (departure).

(b) Physical vs Mathematical model + steps of a simulation study (6)

Physical model: A tangible, scaled-down (iconic) replica of the real system whose physical properties resemble the original. Example: a wind-tunnel model of an aircraft, a model dam.

Mathematical model: Represents the system through logical and quantitative relationships (equations, inequalities, logical conditions) that are manipulated to see how the model reacts. Example: $L = \lambda/(\mu-\lambda)$ for a queue. Simulation models are typically mathematical models solved numerically.

Steps in a simulation study (flowchart, described in words):

1. Problem formulation — state objectives.
2. Setting objectives and overall plan.
3. Model conceptualization — build the conceptual model.
4. Data collection.
5. Model translation — code the model in a language/tool.
6. Verified? (No → return to step 5).
7. Validated? (No → return to step 3/4).
8. Experimental design — runs, length, replications.
9. Production runs and analysis.
10. More runs? (Yes → step 8).
11. Documentation and reporting.
12. Implementation.

The flowchart is a top-down flow from Problem formulation down to Implementation, with decision diamonds at Verification and Validation looping back, and a loop from production runs back to experimental design when more runs are needed.

(a) Simulation table (8)

Arrival time = running sum of inter-arrival times. Service begins at $\max(\text{arrival}, \text{previous service-end})$.

(b) Performance measures (4)

Average waiting time in queue:

$$W_q = \frac{\sum \text{wait}}{N} = \frac{4}{6} = 0.67 \text{ minutes}$$

Average time in system:

$$W = \frac{\sum \text{time in system}}{N} = \frac{21}{6} = 3.5 \text{ minutes}$$

Server utilization (total busy time over total simulation time; server idle gaps exist between customers):

$$\rho = \frac{\text{total service time}}{\text{simulation end time}} = \frac{17}{22} = 0.77 \;(77\%)$$

So customers wait on average 0.67 min in the queue, spend 3.5 min in the system, and the server is busy 77% of the time.

(a) Linear Congruential Method + Hull-Dobell theorem (5)

The Linear Congruential Method (LCM) produces a sequence of integers between $0$ and $m-1$ by the recurrence:

$$X_{n+1} = (a X_n + c)\bmod m,\qquad n\ge 0$$

where $X_0$ = seed, $a$ = multiplier, $c$ = increment, $m$ = modulus. Random numbers on $(0,1)$ are then $U_n = X_n/m$. If $c=0$ it is called the multiplicative congruential method.

Hull-Dobell theorem — a mixed LCG ($c\neq 0$) has full period $m$ if and only if:

1. $c$ and $m$ are relatively prime ($\gcd(c,m)=1$);
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) Multiplicative generator (3)

$X_{n+1} = (17 X_n)\bmod 100$, seed $X_0 = 27$.

First five random numbers: 0.59, 0.03, 0.51, 0.67, 0.39.

(c) Inverse-transform technique for the exponential distribution (4)

Idea: If $X$ has CDF $F(x)$ and $U\sim U(0,1)$, then $X = F^{-1}(U)$ has the desired distribution, because $F$ is monotone and $P(F^{-1}(U)\le x)=P(U\le F(x))=F(x)$.

For the exponential distribution with mean $1/\lambda$:

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

Set $U = F(X)$ and invert:

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

Since $1-U$ is also uniform on $(0,1)$, in practice we use:

$$\boxed{X = -\frac{1}{\lambda}\ln U}$$

Procedure: generate $U\sim U(0,1)$; return $X=-\tfrac{1}{\lambda}\ln U$ as an exponential variate.

(a) Verification vs Validation + verification techniques (7)

Verification asks "Are we building the model right?" — it checks that the computer program/implementation correctly represents the conceptual (assumed) model, i.e. it is debugging the code.

Validation asks "Are we building the right model?" — it checks that the model is an accurate representation of the real system for the intended purpose, comparing model behavior with reality.

Techniques for verifying a simulation model (any three):

1. Structured walk-through / code review of the program by the modeler and others.
2. Trace and debugging — print the state, clock, and event list as events occur and check them by hand for a few steps.
3. Run with simplified/known input for which analytic answers exist (e.g. set arrival = service so the queue should behave predictably) and compare.
4. Animation — observe the dynamic behavior graphically to spot logical errors.
5. Check output reasonableness for a variety of input parameter settings.

(b) General-purpose vs special-purpose simulation languages (5)

General-purpose languages (C, C++, Java, Python):

• Advantages: widely known, flexible, fast execution, low cost, no licensing, portable, integrates easily with other software.
• Disadvantages: must program the simulation infrastructure (clock, event list, random generators, statistics) yourself; longer development time; more error-prone.

Special-purpose simulation languages (GPSS, SIMSCRIPT, SIMAN, SLAM):

• Advantages: built-in simulation facilities — automatic time advance, event/queue handling, random-variate generators, automatic statistics collection; faster modeling; reduced coding/errors; good built-in reporting and often animation.
• Disadvantages: must learn a new language; less flexible for unusual logic; may run slower; licensing cost; less portable.

Conclusion: general-purpose languages give maximum flexibility at the cost of effort, while simulation languages speed up development at the cost of flexibility and money.

Kolmogorov-Smirnov (K-S) test for uniformity

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

Step 1 — sort the numbers in ascending order:

$$0.05,\;0.14,\;0.44,\;0.81,\;0.93$$

Step 2 — compute $D^+ = \max_i\left(\tfrac{i}{n} - R_{(i)}\right)$ and $D^- = \max_i\left(R_{(i)} - \tfrac{i-1}{n}\right)$, with $n=5$.

$$D^+ = 0.26,\qquad D^- = 0.21$$

Step 3 — test statistic:

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

Step 4 — compare with critical value: $D_{\alpha} = D_{0.05} = 0.565$ for $n=5$.

Since $D = 0.26 < 0.565 = D_{0.05}$, we do not reject $H_0$.

Conclusion: There is no evidence against uniformity at the $0.05$ level — the numbers can be regarded as uniformly distributed on $(0,1)$.

M/M/1 queue: $\lambda = 8/\text{hr}$, $\mu = 10/\text{hr}$

(a) Server utilization (traffic intensity):

$$\rho = \frac{\lambda}{\mu} = \frac{8}{10} = 0.8 \;(80\%)$$

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

$$L = \frac{\lambda}{\mu - \lambda} = \frac{8}{10-8} = \frac{8}{2} = 4 \text{ customers}$$

(c) Average number in the queue $L_q$:

$$L_q = \frac{\lambda^2}{\mu(\mu-\lambda)} = \frac{64}{10\times 2} = 3.2 \text{ customers}\quad(=\rho L = 0.8\times4)$$

(d) Average time a customer spends in the system $W$:

$$W = \frac{1}{\mu - \lambda} = \frac{1}{2}\,\text{hr} = 0.5\,\text{hr} = 30 \text{ minutes}$$

Summary: $\rho = 0.8$, $L = 4$, $L_q = 3.2$, $W = 0.5$ hr (30 min).

(a) Acceptance-Rejection technique (4)

Used when the inverse CDF is hard to obtain. To generate $X$ with density $f(x)$, choose a simpler density $g(x)$ from which we can sample, and a constant $c$ such that $f(x) \le c\,g(x)$ for all $x$.

Algorithm:

1. Generate $Y$ from $g(x)$.
2. Generate $U\sim U(0,1)$ independently.
3. If $U \le \dfrac{f(Y)}{c\,g(Y)}$, accept and set $X = Y$.
4. Otherwise reject and return to step 1.

The accepted values follow $f(x)$. The efficiency is $1/c$ (the probability of acceptance), so a smaller $c$ (tighter envelope) means fewer rejections. Example: generating a $U(0,1)$ variate from a Poisson/triangular density using a uniform envelope.

(b) Convolution method for an Erlang variate (4)

The convolution method uses the fact that some random variables are the sum of simpler, independent variates. The Erlang-$k$ distribution with rate $\lambda$ (mean $k/\lambda$) is the sum of $k$ independent exponential variates each with mean $1/\lambda$:

$$X = \sum_{i=1}^{k} X_i,\qquad X_i \sim \text{Exp}(\lambda).$$

Procedure:

1. Generate $k$ independent uniforms $U_1,\dots,U_k \sim U(0,1)$.
2. Convert each to an exponential by inverse transform: $X_i = -\tfrac{1}{\lambda}\ln U_i$.
3. Sum them:

$$X = \sum_{i=1}^{k} X_i = -\frac{1}{\lambda}\sum_{i=1}^{k}\ln U_i = -\frac{1}{\lambda}\ln\!\Big(\prod_{i=1}^{k} U_i\Big).$$

The result $X$ is an Erlang-$k$ variate. (Only $k-1$ multiplications/one log are needed using the product form.)

Tests for independence of random numbers

Both tests check independence (no correlation/pattern), as opposed to uniformity.

Autocorrelation test

It checks whether numbers separated by a lag $m$ are correlated. For numbers $R_i$, the test computes the autocorrelation $\rho_{im}$ between every $m$-th number starting from $R_i$:

$$\hat\rho_{im} = \frac{1}{M+1}\sum_{k=0}^{M}R_{i+km}R_{i+(k+1)m} - 0.25,$$

where $M$ is the largest integer with $i+(M+1)m \le N$. The standardized statistic

$$Z_0 = \frac{\hat\rho_{im}}{\sigma_{\hat\rho_{im}}}$$

is compared with the standard normal critical value $z_{\alpha/2}$. If $|Z_0| \le z_{\alpha/2}$ we accept $H_0$ (the numbers are independent / not autocorrelated at lag $m$). Property checked: independence — absence of correlation between numbers a fixed distance apart.

Runs test (test for independence)

A run is a succession of numbers in the same direction. We look at runs up and down: mark $+$ when the next number is larger and $-$ when smaller; a run is a maximal block of identical signs. Count the total number of runs $a$. For $n$ numbers the expected number and variance of runs are:

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

The statistic $Z_0 = (a-\mu_a)/\sigma_a$ is compared with $z_{\alpha/2}$. Too few or too many runs both indicate dependence. Property checked: independence — whether the sequence has patterns/trends (clustering or rapid oscillation).

Summary: the autocorrelation test detects correlation between numbers at a given lag; the runs test detects trends/patterns in the order of the numbers. Both assess independence, not uniformity.

Event-scheduling / time-advance algorithm in DES

In discrete-event simulation the system state changes only at discrete points in time called events. The simulation jumps from one event time to the next using the next-event time-advance approach (the clock skips over idle periods).

Key data structures:

• System clock (CLOCK): holds the current simulation time.
• Future Event List (FEL): an ordered list of pending events, each tagged with the (event type, event time). It is kept sorted by event time so the imminent (earliest) event is always at the head.
• State variables and statistical counters.

Algorithm:

1. Initialize: CLOCK = 0; set state variables and counters;
   schedule initial event(s) and place them in the FEL.
2. While (FEL not empty AND stopping condition not met):
   a. Remove the imminent event (smallest time) from the FEL.
   b. Advance the CLOCK to that event's time.
   c. Execute the event routine:
        - update system state,
        - update statistical counters,
        - generate and schedule future events (insert into FEL),
        - generate random variates as needed.
3. End while -> compute and report summary statistics.

Role of FEL and clock (diagram, in words): Imagine a horizontal time axis. The FEL is a queue of event notices ordered left-to-right by time, e.g. [t=3 Arrival] -> [t=4 Departure] -> [t=7 Arrival]. The simulation engine repeatedly: (1) pops the leftmost (imminent) notice, (2) sets the CLOCK to its time, (3) runs the corresponding event routine which may push new notices back into the FEL in sorted order. Thus the CLOCK never moves backward and only stops at instants where the state actually changes, making the simulation efficient.

(a) Classifications of simulation (4)

Continuous vs Discrete:

• Discrete simulation: the state variables change only at discrete (countable) points in time. Example: number of customers in a bank queue (changes at arrivals/departures).
• Continuous simulation: the state variables change continuously over time, usually described by differential equations. Example: the water level in a reservoir, or velocity of a moving vehicle.

Deterministic vs Stochastic:

• Deterministic simulation: contains no random variables; the same input always gives the same output. Example: a fixed-schedule chemical reaction model.
• Stochastic simulation: contains one or more random variables; outputs are random and must be treated as statistical estimates. Example: a queue with random arrival and service times.

(b) Monte Carlo simulation (4)

Monte Carlo simulation is a technique that uses repeated random sampling from probability distributions to obtain numerical estimates of quantities that may be deterministic but hard to compute analytically. It is generally static (no time-advance mechanism). Steps: model the problem with random inputs, sample many values, evaluate the outcome each time, and aggregate (average) the results, whose accuracy improves with the number of trials ($\propto 1/\sqrt{N}$).

Example application — estimating $\pi$ / numerical integration: Throw $N$ random points uniformly in the unit square; the fraction landing inside the quarter circle approximates $\pi/4$, so $\pi \approx 4 \times (\text{points inside}/N)$. Other practical uses: evaluating definite integrals, risk and financial-portfolio analysis, reliability estimation, and inventory/project-cost analysis.

Short notes (any two)

(a) Steps in building a simulation model

1. Problem formulation — define the problem and objectives.
2. Model conceptualization — identify entities, attributes, activities, events and assumptions.
3. Data collection — gather input data and fit distributions.
4. Model translation (coding) — implement in a language or simulation package.
5. Verification — check that the program matches the conceptual model.
6. Validation — check that the model represents the real system.
7. Experimental design — decide run length, number of replications, warm-up.
8. Production runs and analysis of output.
9. Documentation, reporting and implementation.

(b) Calibration and validation of models

• Calibration is the iterative process of tuning/adjusting model parameters and assumptions so that model output matches observed real-system data as closely as possible. It is an internal refinement loop.
• Validation is the process of confirming that the (calibrated) model is an accurate representation of the real system for its intended purpose, typically by comparing model output with independent real-world data, using face validity, historical-data validation and sensitivity analysis.
• Relationship: calibration adjusts the model; validation judges whether the adjusted model is good enough. Over-calibrating to one data set can hurt validity, so validation should use data not used in calibration.

(c) Advantages and disadvantages of simulation

Advantages:

• Can study systems too complex for analytical solution.
• "What-if" experiments without disturbing the real system.
• Compresses or expands time; cheaper and safer than real experiments.
• Gives insight into how the system works and which variables matter.

Disadvantages:

• Model building requires special skill and is time-consuming.
• Results can be hard to interpret (random output needs statistical analysis).
• Can be expensive and may consume much computer time.
• May be misused — a model that looks realistic may still be invalid.