CSC 426: Computer Simulation Comprehensive Notes

Introduction to Computer Simulation and Basic Definitions

• Definition of Simulation: Simulation is the process of designing and developing a model of a real-world system and conducting experiments on that model to understand its behavior, predict future outcomes, or evaluate alternative strategies for decision-making.
• Purpose of Simulation: It allows for the imitation of real-life processes in a controlled environment. It is specifically utilized when:
  • Real experimentation is prohibitively costly.
  • The system is too complex for analytical solutions.
  • The system does not yet exist physically.
• Time-Based Nature: Simulation involves time-based analysis; the model evolves and generates results as time progresses.
• System: A collection of interrelated components working together toward a specific objective. Examples include banking systems, traffic systems, computer networks, and manufacturing systems.
  • Open System: Interacts with its environment.
  • Closed System: Minimal interaction with its environment.
• Model: A simplified representation of a real system used to study behavior. It reduces complexity while preserving essential features.
• State of a System: The current condition of the system at any given time (e.g., the number of customers waiting in a queue).
• Event: An occurrence that changes the state of the system (e.g., a customer arrival or service completion).
• Parameters: Fixed values in a simulation, such as a service rate.
• Variables: Values that change during the simulation, such as queue length.
• System Types:
  • Deterministic: No randomness; outcomes are entirely predictable.
  • Stochastic: Includes randomness; outcomes are probabilistic.

Uses, Advantages, and Limitations of Simulation

• Primary Uses:
  • Performance Evaluation: Analyzing how well a system performs under different conditions (e.g., network response time, queue waiting time).
  • Decision Making and Forecasting: Testing strategies before implementation, such as business expansion or inventory management.
  • Risk Analysis: Assessing uncertainties in financial risk modeling or disaster management planning.
  • Training and Education: Providing safe environments via flight simulators, medical training simulators, or military simulations.
  • System Design and Optimization: Improving systems like manufacturing processes or traffic flow before deployment.
  • Research and Development: Experimenting with new ideas without physical implementation.
  • Cost Reduction: Using virtual models to replace expensive real-world experimentation.
• Advantages:
  • Allows testing without real-world risk.
  • Saves significant time and cost.
  • Capable of handling complex, non-linear systems.
  • Flexible and adaptable to various scenarios.
  • Enables "what-if" analysis (e.g., adding more servers or increasing demand).
• Limitations:
  • Requires highly accurate data to be valid.
  • Model development can be time-consuming.
  • Results are heavily dependent on underlying assumptions.
  • Requires specialized technical expertise.
  • Software and tools can be expensive.
  • Cannot guarantee real-world outcomes; results are estimates.
• Real-Life Examples: ATM queue systems, airline reservation systems, hospital patient flow, traffic light control systems, and e-commerce platforms.

The Simulation Process

• Step 1: Problem Definition: Identifying the problem, defining objectives, and determining the scope, boundaries, and limitations (e.g., "How to reduce bank waiting time?").
• Step 2: System Analysis: Studying the real-world system in detail to identify components, operations, inputs, outputs, and performance measures.
• Step 3: Model Formulation: Translating the real system into a mathematical or logical form and defining relationships between variables.
• Step 4: Data Collection: Gathering historical or real-time data, identifying input parameters (arrival rates), and cleaning the data.
• Step 5: Model Implementation (Coding): Converting the model into a computer program using software like Python, MATLAB, Arena, or others.
• Step 6: Verification and Validation:
  • Verification: Checking if the model is implemented correctly (debugging logic).
  • Validation: Checking if the model accurately represents the real system (comparing with real data).
• Step 7: Experimentation: Running simulations under different conditions and changing input variables to observe effects.
• Step 8: Result Analysis: Interpreting graphs, tables, and performance metrics to identify trends and determine if objectives were met.
• Step 9: Documentation and Reporting: Creating detailed reports including methodology, results, assumptions, and recommendations for stakeholders.

Detailed Classification of Models and Simulations

• Physical Models: Tangible replicas (e.g., miniature bridges, globes, wind tunnel airplane models). They are easy to visualize but can be expensive and inaccurate in scale dynamics.
• Mathematical Models: Representations using formulas and equations (e.g., $F = ma$, population growth $P(t) = P_0 e^{rt}$). They are precise but may oversimplify reality.
• Computer Models: Software simulations (e.g., weather forecasting, flight simulators). They handle high complexity but require significant computing power.
• Simulation Model Types:
  • Deterministic Simulation: Same inputs always produce same outputs; no randomness involved (e.g., compound interest calculation).
  • Stochastic Simulation: Includes randomness/probability; different results per run (e.g., stock market prediction).
  • Discrete-Event Simulation (DES): Changes occur only at specific points in time called events (e.g., bank queues). Time jumps from one event to the next.
  • Continuous Simulation: Changes occur smoothly and constantly over time, often modeled with differential equations (e.g., water filling a tank, car motion).

Basic Statistical Distribution Theory

• Uniform Distribution: All outcomes have equal probability.
  • Use Case: Random sampling where no value is more likely than another (e.g., rolling a fair die).
• Normal Distribution: A symmetric bell-shaped curve where values cluster around the mean ($\\mu$).
  • Key Feature: Mean = Median = Mode. Defined by mean ($\\mu$) and standard deviation ($\\sigma$).
  • Use Case: Human height, IQ scores, measurement errors.
• Exponential Distribution: Models the time between independent events occurring at a constant average rate.
  • Formula: $f(x) = \lambda e^{-\lambda x}$ for $x \ge 0$.
  • Property: Memoryless (past history does not affect future probability).
  • Use Case: Time between customer arrivals or machine failures.
• Poisson Distribution: Models the number of events occurring in a fixed interval of time or space.
  • Formula: $P(X = k) = \frac{\lambda^k e^{-\lambda}}{k!}$.
  • Use Case: Counting emails received per hour or cars passing a point per minute.
• Relationship: Poisson counts the number of events; Exponential measures the time between those same events.

Queueing Systems Theory

• Basic Components:
  • Arrival Process: Characterized by arrival rate ($\lambda$). Patterns can be deterministic or stochastic (Poisson).
  • Service Mechanism: Characterized by the number of servers and service rate ($\mu$).
  • Queue Discipline: The rule for service order (FCFS/FIFO, LCFS, Priority, Random Selection).
  • System Capacity: Fixed (Finite) or unlimited (Infinite) waiting space.
• Kendall Notation: Expressed as $A/B/s/K/N/D$.
  • $A$: Arrival time distribution.
  • $B$: Service time distribution.
  • $s$: Number of servers.
  • $K$: System capacity.
  • $N$: Population size.
  • $D$: Queue discipline.
  • Common Symbols: $M$ = Markovian (Exponential/Poisson), $D$ = Deterministic, $G$ = General.
  • Example: $M/M/1$ represents Poisson arrivals, Exponential service, and a single server.
• Little’s Law: Defines the relationship between the average number of customers ($L$), arrival rate ($\lambda$), and average time in the system ($W$):
  • $L = \lambda W$
• Server Utilization ($\rho$): Represents the utilization factor:
  • $\rho = \frac{\lambda}{\mu}$
  • If $\rho < 1$, the system is stable. If $\rho \ge 1$, the system is unstable/overloaded.
• Queueing Networks: Interconnected queues where customers move between service stations (e.g., hospitals, airports).

Stochastic Processes

• Definition: A collection of random variables $X(t)$ indexed by time $T$, representing a system evolving randomly.
• State Space: The set of all possible values (e.g., count of customers, temperature values).
• Classifications:
  • Discrete-State: States are countable (count of machine failures).
  • Continuous-State: States can be any value in a range (blood pressure).
  • Discrete-Time: Changes at specific intervals (daily stock prices).
  • Continuous-Time: Changes constantly (radioactive decay).
• Markov Processes: A process where the future state depends only on the current state, not the history.
  • Markov Property: $P(X_{n+1} | X_n, X_{n-1}, \dots, X_0) = P(X_{n+1} | X_n)$.
• Birth-Death Processes: State changes occur one step at a time via "Birth" (increase/arrival, $\lambda$) or "Death" (decrease/departure, $\mu$).
• Poisson Process Properties:
  • Events are independent.
  • Constant average rate $\lambda$.
  • Events occur one at a time.
  • Probabilistic formula: $P(X = x) = \frac{e^{-\lambda} \lambda^x}{x!}$.

Random Numbers in Simulation

• Basics: Usually generated in the interval $0 \le R \le 1$.
• Types:
  • True Random: Generated from physical processes (radioactive decay, thermal noise). Unpredictable and non-repeatable.
  • Pseudo-Random: Generated by mathematical algorithms. They are deterministic and repeatable (if the seed is known) but appear random.
• Properties of Good Random Numbers: Uniformity, Independence, Long Cycle Length, and Generation Efficiency.
• Linear Congruential Generator (LCG):
  • Formula: $X_{n+1} = (aX_n + c) \mod m$
  • Normalization: $R_n = \frac{X_n}{m}$
• Mid-Square Method: An early technique of squaring a seed and extracting the middle digits to form the next seed.
• Inverse Transformation Method: Used to convert uniform random numbers ($R$) into other distributions.
  • For Exponential: $X = -\frac{1}{\lambda} \ln(1 - R)$.

Worked Examples and Computational Exercises

• Queue Calculation (Little's Law): If a bank has $\lambda = 10$ customers/hour and the time in system $W = 30$ minutes ($0.5$ hours):
  • $L = 10 \times 0.5 = 5$ customers.
• Event-Based Waiting Time: Customer 1 arrives at $T=0$, served for $4$ min. Customer 2 arrives at $T=2$.
  • Customer 1 departs at $T=4$.
  • Customer 2 starts service at $T=4$.
  • Waiting Time for Customer 2 = $4 - 2 = 2$ minutes.
• LCG Random Number Generation: Given $a=5, c=3, m=16, X_0=7$:
  • $X_1 = (5 \times 7 + 3) \mod 16 = 38 \mod 16 = 6$
  • $X_2 = (5 \times 6 + 3) \mod 16 = 33 \mod 16 = 1$
  • $X_3 = (5 \times 1 + 3) \mod 16 = 8$
  • $X_4 = (5 \times 8 + 3) \mod 16 = 43 \mod 16 = 11$
  • $X_5 = (5 \times 11 + 3) \mod 16 = 58 \mod 16 = 10$
• Exponential Probability: $\lambda = 2$ customers/hour. Probability time between arrivals $T > 1$ hour:
  • $P(T > 1) = e^{-2 \times 1} = e^{-2} \approx 0.1353$
• Supermarket Queue Logic: Arrival every $5$ min ($\lambda = 0.2$) and service time $4$ min ($\mu = 0.25$).
  • Since $\lambda < \mu$, no long queue will form.
• Random Number Interval Exercise: Given intervals (0.00-0.20: 1 arrival; 0.21-0.50: 2 arrivals; 0.51-0.80: 3 arrivals; 0.81-1.00: 4 arrivals).
  • If random number $R = 0.67$, the number of arrivals is $3$.