SIMULATION & MODELING (IT-702 (C)) - Unit 1 Short Notes

UNIT 1: FUNDAMENTALS OF SIMULATION AND MODELING

1. Introduction to Simulation

Simulation is the process of developing a model (a logical/mathematical representation) of a real-world system and conducting experiments with this model to understand the behavior of the system or evaluate strategies for its operation.

[!TIP] Exam Focus: Be prepared to draw and explain the simulation process flow diagram.

Steps in Simulation Process:

1. Problem Identification: Define the issue, objectives, and project scope.

2. System Definition & Model Formulation: Identify system components, variables, and logical relationships. Formulate a conceptual model.

3. Data Collection & Input Modeling: Gather data on system parameters (arrival rates, service times, etc.). Fit probability distributions to data.

4. Model Translation: Convert the conceptual model into a computer-executable form using a simulation language/tool (e.g., Arena, SimPy).

5. Verification & Validation: Ensure the model is built correctly (verification) and accurately represents the real system (validation).

6. Experimental Design & Run: Define scenarios, number of replications, and run length. Execute the simulation.

7. Output Analysis & Interpretation: Analyze results (using statistics), draw conclusions, and make recommendations.

8. Documentation & Implementation: Document the model and report findings. Implement decisions if applicable.

Flow Diagram:

[Problem Identification] → [System Definition/Model Formulation] → [Data Collection/Input Modeling]

        ↓

[Model Translation] → [Verification & Validation] → [Experimental Design & Run]

        ↓

[Output Analysis & Interpretation] → [Documentation & Implementation]

Advantages:

• Non-destructive analysis of complex systems.

• Allows "what-if" scenario testing without real-world risk/cost.

• Provides insights into system behavior over time (dynamic).

• Useful for training and education.

• Can compress/expand time for study.

Limitations:

• Model building is an art; requires significant expertise.

• Can be expensive and time-consuming (especially for large models).

• Results are estimates, not exact predictions (stochastic nature).

• Validation can be challenging; is the model "good enough"?

• May lead to over-reliance on results without managerial intuition.

2. Classification of Systems

Continuous Systems:

• Definition: Systems where state variables change continuously over time.

• Characteristics: State described by continuous functions. Differential equations are primary modeling tools. Time is a continuous variable.

• Example: Autopilot Simulation for an aircraft. State variables (altitude, velocity, heading) change smoothly. The autopilot continuously adjusts control surfaces (elevator, aileron, rudder) based on sensor feedback to maintain a desired flight path. Modeled using Ordinary Differential Equations (ODEs) representing physics of flight.

Discrete Systems:

• Definition: Systems where state variables change instantaneously at specific, separate points in time.

• Characteristics: State changes are events (e.g., a customer arrives, a machine fails, a job completes). Time is a discrete variable between events. Often involve queues, resources, and logic.

• Example: A bank teller system. State (number of customers in queue) changes only when a customer arrives or departs.

Comparison: Continuous vs. Discrete System Simulation

3. Probability and Statistics for Simulation

Random Variables (Stochastic Variables):

A variable whose value is determined by the outcome of a random experiment.

• Discrete RV: Takes countable values (e.g., number of customers arriving).

  • Probability Mass Function (PMF): $$\displaystyle P(X = x_i) = p_i $$

  • Cumulative Distribution Function (CDF): $$\displaystyle F(x) = P(X \leq x) $$

• Continuous RV: Takes any value in an interval.

  • Probability Density Function (PDF): $f(x)$, where $$\displaystyle P(a \leq X \leq b) = \int_a^b f(x)dx $$

  • Cumulative Distribution Function (CDF): $$\displaystyle F(x) = P(X \leq x) = \int_{-\infty}^x f(t)dt $$

Key Probability Distributions:

1. Binomial Distribution:

   • Expression:

$$P(X = k) = \binom{n}{k} p^k (1-p)^{n-k}, \quad k=0,1,...,n$$

*   **Conditions:** Fixed number of independent trials `n`, constant probability of success `p` per trial, two outcomes (success/failure).

*   **Mean:** $$\displaystyle \mu = np $$, **Variance:** $$\displaystyle \sigma^2 = np(1-p) $$

2. Poisson Distribution:

   • Expression:

$$P(X = k) = \frac{e^{-\lambda} \lambda^k}{k!}, \quad k=0,1,2,...$$

*   **Conditions:** Models number of events in a fixed interval. Events occur independently, at a constant average rate `λ`, and singly (no simultaneous events).

*   **Mean & Variance:** $$\displaystyle \mu = \lambda $$, $$\displaystyle \sigma^2 = \lambda $$

3. Normal (Gaussian) Distribution:

   • Expression (PDF):

$$f(x) = \frac{1}{\sigma\sqrt{2\pi}} e^{-\frac{1}{2}\left(\frac{x-\mu}{\sigma}\right)^2}$$

*   **Parameters:** Mean `μ`, Standard Deviation `σ`. Symmetric bell curve.

*   **Importance:** Central Limit Theorem; many natural phenomena and sample means approximate normality.

Approximation of Binomial by Poisson:

• Condition: When number of trials n is large ($n \geq 20$) and probability of success p is small ($p \leq 0.05$), such that $$\displaystyle \lambda = np $$ is moderate (typically $$\displaystyle \lambda < 5 $$ or $10$).

• Rationale: Under these conditions, the Binomial($n$, $p$) can be approximated by Poisson($$\displaystyle \lambda = np $$).

Density & Distribution Functions (Example):

• Exponential Distribution (Continuous): PDF: $$\displaystyle f(t) = \lambda e^{-\lambda t}, t \geq 0 $$. CDF: $$\displaystyle F(t) = 1 - e^{-\lambda t} $$. Models interarrival times in a Poisson process or service times.

• Empirical CDF: For data, $$\displaystyle F_n(x) = \frac{\text{number of observations} \leq x}{n} $$.

4. Queuing Theory and Simulation

General Queuing System (Kendall's Notation): A/B/c/K/N/π

• A: Arrival process distribution (e.g., M=Markovian/Poisson, D=Deterministic, G=General)

• B: Service time distribution (M, D, G)

• c: Number of parallel servers

• K: System capacity (max number in system, including service)

• N: Population size (source of customers)

• π: Queue discipline (FCFS, LCFS, SIRO, Priority)

Illustrative Diagram:

[Source] → [Arrival Stream] → [Queue] → [c Servers] → [Departure]

         (Infinite Capacity?)   (FIFO?)   (Parallel?)

Characteristics of Queuing Systems:

1. Arrival Pattern: Described by interarrival time distribution. Poisson process ($M$) is most common (memoryless property).

2. Service Mechanism: Number of servers (c), service time distribution (Exponential M common), whether service is in batches.

3. Queue Discipline: Rule for selecting next customer for service. FCFS/FIFO is most common. Others: LCFS, SIRO, Priority (preemptive/non-preemptive).

4. Capacity Limitations: Finite system capacity (K) can cause balking (customer doesn't join) or reneging (customer leaves after joining).

Applications:

• Manufacturing: Job shops, assembly lines.

• Transportation: Traffic flow, airport runways.

• Services: Call centers, hospitals, banks, computer networks.

• Telecommunication: Packet switching networks.

Simulation of Queuing Systems: Procedure & Example:

1. Initialize: Time t=0, empty queue, servers idle. Set counters (num served, total wait, max queue length).

2. Schedule First Arrival: Generate first interarrival time from input distribution. Set next arrival time.

3. Advance Time: Find next event (next arrival or next departure). Advance simulation clock to that time.

4. Process Event:

   • Arrival: If server free, start service (schedule departure); else, join queue. Schedule next arrival.

   • Departure: Free server. If queue not empty, remove next customer, start service (schedule new departure). Collect statistics (wait time, service time).

5. Repeat from step 3 until termination condition (e.g., t >= T or N customers served).

6. Compute Averages: Average wait, server utilization, average queue length.

[!TIP] Common Pitfall: Forgetting to schedule the next event after processing the current one, or incorrectly handling server state transitions.

5. Model Verification and Validation

6. Simulation Languages and Tools

Classification of Simulation Languages:

1. By Application Domain:

   • Continuous: DYNAMO, ACSL (focus on ODEs).

   • Discrete: GPSS, SIMSCRIPT, Arena, SimPy (focus on events/queues).

   • Combined: GASP IV, SIMAN (can handle both).

2. By Time Handling:

   • Event-Scheduling: Next-event time advance (GPSS, SimPy). Most common for discrete.

   • Activity-Scanning: Scan for activities to execute (SIMSCRIPT).

   • Process-Interaction: Define processes (flow of entities) (Arena, SimPy's Process).

3. By Programming Paradigm:

   • Simulation Libraries/Packages: Extensions to general languages (SimPy for Python, Simmer for R).

   • Special-Purpose Simulation Languages: Standalone with built-in constructs (Arena, AnyLogic).

Analog vs. Digital Simulation:

7. Advanced Simulation Techniques

AI Techniques in Simulation:

• Neural Networks: Used for input modeling (fitting complex distributions from data) or as surrogate models (emulators) to replace slow simulation models for rapid optimization.

• Genetic Algorithms (GA): Used for optimization within simulation. GA searches for optimal input parameters (e.g., resource levels, scheduling rules) by evolving a population of solutions evaluated via simulation runs.

• Fuzzy Logic: Handles imprecise inputs and rules in simulation models, useful for human decision-making or control systems where logic is not binary.

• Expert Systems: Incorporate heuristic rules from human experts into simulation logic for complex decision points.

• Reinforcement Learning (RL): Agent learns optimal policy (actions) through trial-and-error interaction with the simulation environment.

Pure Pursuit Problem in Modeling:

• Concept: A classic path-tracking problem in robotics/autonomous vehicles. A pursuer (e.g., robot, missile) aims to follow a desired path (set of waypoints) by always steering towards a look-ahead point on the path at a fixed distance ahead.

• Modeling/Simulation Steps:

  1. Represent vehicle kinematics (bicycle model common).

  2. Define path (set of (x,y) coordinates).

  3. Algorithm: At each time step:

     • Find closest point on path to vehicle.

     • Identify look-ahead point at distance L_d along path from closest point.

     • Compute desired steering angle to head towards look-ahead point.

     • Update vehicle state (position, heading) using control input.

  4. Simulate to evaluate tracking error, stability, and performance for different L_d values or vehicle speeds.

• Application: Autonomous ground vehicles, UAV path following.

8. Mathematical Foundations

Role of Differential Equations in Simulation:

• Core Purpose: To model continuous systems where the rate of change of state variables is defined by their current state and inputs.

• Ordinary Differential Equations (ODEs): Used when system state depends only on time (e.g., $$\displaystyle \frac{dx}{dt} = f(x, t) $$). Example: Spring-mass-damper: $$\displaystyle m\frac{d^2x}{dt^2} + c\frac{dx}{dt} + kx = F(t) $$.

• Solution Methods in Simulation:

  • Analytical: Solve ODEs exactly (rare for complex systems).

  • Numerical Integration: Primary method in continuous simulation. Algorithms: Euler's method, Runge-Kutta methods (RK4). These compute state at discrete time steps $$\displaystyle t_{i+1} = t_i + \Delta t $$.

• Example: Simulating population growth (logistic equation): $$\displaystyle \frac{dP}{dt} = rP(1 - P/K) $$. Use Euler's method: $$\displaystyle P_{new} = P_{old} + \Delta t \cdot rP_{old}(1 - P_{old}/K) $$.

Arrival Patterns in Queuing Theory (Poisson Process):

• Definition: A counting process $N(t)$ representing number of arrivals in time interval $(0,t]$.

• Key Properties:

  1. Independent Increments: Numbers of arrivals in disjoint intervals are independent.

  2. Stationary Increments: Distribution of arrivals in interval of length t depends only on t, not start time.

  3. No Simultaneous Arrivals: Probability of >1 arrival in infinitesimal interval $\Delta t$ is $o(\Delta t)$.

• Implications:

  • Interarrival Times are Exponentially distributed with rate $\lambda$ (mean $1/\lambda$). PDF: $$\displaystyle f(t) = \lambda e^{-\lambda t} $$.

  • Memoryless Property: $$\displaystyle P(T > s+t | T > s) = P(T > t) $$. Future arrival doesn't depend on past.

• Why Important? The M/M/1 queue (Poisson arrivals, Exponential service, 1 server) is the fundamental building block for analyzing more complex queues. Its analysis provides closed-form formulas for performance metrics (L, Lq, W, Wq).