Discrete Event Simulation (DES): Concepts, Phases, and Applications

TAKEAWAYS:

• DES models systems where state changes occur at discrete points in time (e.g., customer arrivals, server completions).
• The three phases of a DES study are problem formulation, model development, and output analysis.
• Poisson arrival patterns and exponential service times are common in DES for modeling randomness (e.g., Pathao ride requests).
• GPSS blocks like MARK and TABULATE track events and collect statistics (e.g., average wait time in a bank queue).
• Hybrid simulation combines DES with continuous models (e.g., simulating traffic flow with vehicle speed changes).
• Initial bias elimination ensures simulation results reflect steady-state behavior (e.g., ignoring early data in a Monte Carlo trial).

Core Concepts of Discrete Event Simulation (DES)

What is DES?

Discrete Event Simulation (DES) is a technique to model systems where the state changes only at specific points in time (events). Unlike continuous simulation (e.g., fluid dynamics), DES focuses on discrete events like:

• A customer arriving at a bank (ARRIVAL event).
• A server finishing a task (DEPARTURE event).
• A machine breaking down (FAILURE event).

Key Idea: The system’s state remains constant between events. For example, in a coffee shop, the number of customers in the queue changes only when a new customer arrives or the barista finishes serving someone.

graph TD
    A["Initial State: Queue = 0"] -->|"Customer arrives"| B["State: Queue = 1"]
    B -->|"Barista starts serving"| C["State: Queue = 0, Server busy"]
    C -->|"Service completes"| A

Phases of a DES Study

Every DES project follows these three phases, visualized below:

1. Problem Formulation

• Objective: Clearly define what the simulation will achieve. Example:
  • Goal: Reduce average wait time in a Daraz delivery queue.
  • Scope: Focus on the last-mile delivery hub (not the entire supply chain).
• Boundaries: Decide what to include/exclude. For example:
  • Include: Number of delivery personnel, package sizes, traffic delays.
  • Exclude: Weather effects (unless data is available).

2. Model Development

Components of a DES Model

Worked Example: Modeling a Bank ATM Queue

Scenario: Customers arrive at an ATM with an average rate of 1 every 2 minutes. The ATM takes 1.5 minutes to process a transaction. Assumptions:

• Arrivals follow a Poisson process (random, independent).
• Service times are exponentially distributed (mean = 1.5 minutes).

Step-by-Step Trace:

1. Event 1: Customer A arrives at time t = 0.
   • State: Queue = [A], ATM = IDLE.
2. Event 2: ATM starts serving A at t = 0.
   • State: Queue = [], ATM = BUSY (until t = 1.5).
3. Event 3: Customer B arrives at t = 1.2 (random Poisson arrival).
   • State: Queue = [B], ATM = BUSY.
4. Event 4: ATM finishes serving A at t = 1.5.
   • State: ATM starts serving B.
5. Event 5: Customer C arrives at t = 2.0.
   • State: Queue = [C], ATM = BUSY.

Visualization of Events:

timeline
    title ATM Queue Simulation Trace
    0: Customer A arrives
    0: ATM starts serving A
    1.2: Customer B arrives (Queue: [B])
    1.5: ATM finishes A, starts B
    2.0: Customer C arrives (Queue: [C])
    3.0: ATM finishes B, starts C

Key DES Concepts and Tools

Poisson Arrivals and Exponential Service Times

• Poisson Process: Models random arrivals where the probability of an arrival in a small time interval is proportional to the interval length.
  • Parameter λ (lambda): Average arrivals per unit time (e.g., λ = 1 customer/3 minutes for the coffee shop).
  • Probability Mass Function (PMF): $$P(N(t)=k)=\frac{e^{-\lambda t}(\lambda t{)}^k}{k!}$$
• Exponential Distribution: Models service times where the probability of completion decreases over time.
  • PMF: $$f(t)=\lambda e^{-\lambda t}$$
  • Mean service time: $\frac{1}{\lambda }$.

Real-World Example:

• Pathao Ride Requests: Ride requests arrive as a Poisson process (λ = 20 requests/hour during peak times). Service time (driver assignment) is exponentially distributed (mean = 3 minutes).

GPSS: A Classic DES Language

GPSS (General Purpose Simulation System) uses blocks to define events. Two critical blocks:

1. MARK Block:

   • Marks the start of a transaction (e.g., a customer entering the system).
   • Syntax: MARK <label>.
   • Example: MARK ARRIVAL when a customer arrives at the coffee shop.

2. TABULATE Block:

   • Collects statistics (e.g., wait times, queue lengths).
   • Syntax: TABULATE <variable>, <interval>.
   • Example: TABULATE WAIT_TIME, 1 records wait times every minute.

GPSS Worked Example: Coffee Shop Simulation

START     GENERATE 3, 0.5      // Arrivals every 3 minutes, 50% variation
         QUEUE     CUSTOMERS   // Join the queue
         SEIZE     BARISTA     // Occupy the barista
         ADVANCE   2.5, 0.5    // Service time: 2.5 mins, 50% variation
         RELEASE   BARISTA
         MARK      1           // End of transaction
         TABULATE WAIT_TIME    // Record wait time
         TERMINATE 1           // End simulation after 1 "customer"

Output: After running, TABULATE provides the average wait time in the queue.

Hybrid Simulation

Combines discrete events (e.g., customer arrivals) with continuous changes (e.g., temperature in a server room). Example: Simulating a data center:

• Discrete Events: Servers failing, technicians arriving.
• Continuous Process: Temperature rising due to overheating servers.

When to Use Hybrid Simulation:

Real-World Tie-In:

• NTC’s Network Traffic Simulation: Uses hybrid models to simulate data packet arrivals (discrete) and signal strength decay (continuous) across Nepal’s telecom towers.

Initial Bias and Steady-State Analysis

Problem: Initial Bias

Early simulation results may not reflect the system’s steady-state behavior because the system starts in an arbitrary state (e.g., empty queue). Example: In a Monte Carlo simulation of a stock market, the first 100 days may show unrealistic volatility.

Solution: Elimination of Initial Bias

1. Warm-Up Period: Discard initial results (e.g., first 10% of simulation time).
2. Batch Means: Split output into batches and analyze only the last few.
3. Regenerative Methods: Reset the simulation at regeneration points (e.g., when the queue empties).

Worked Example: Coffee Shop Warm-Up

• Simulate for 100 minutes (total time).
• Discard first 20 minutes (warm-up).
• Analyze wait times from t = 20 to t = 100.

Exam Tip: How to Score Full Marks

1. For DES Definition:

   • Always mention discrete events, state changes, and time advancement.
   • Example answer:

     "Discrete Event Simulation models systems where state changes occur instantaneously at specific events (e.g., arrivals, departures). Time advances from one event to the next, ignoring continuous changes between events."

2. For Phases of Simulation:

   • Draw the flowchart (Figure 2) and label all three phases with bullet points.

3. For GPSS:

   • Explain MARK and TABULATE with a short code snippet (like above) and a real-world analogy (e.g., eSewa transactions).

4. For Poisson/Exponential:

   • Write the PMF equations and relate them to a real scenario (e.g., Pathao ride requests).

5. For Hybrid Simulation:

   • Compare DES vs. hybrid in a table (like above) and give a Nepali example (NTC, NEPSE trading).

6. For Initial Bias:

   • Describe warm-up period with a time trace (like the ATM example) and explain why it’s needed.

In the Real World

1. eSewa Transactions:

   • Idea Used: Queueing Theory + DES.
   • How: eSewa’s backend simulates payment requests as discrete events (arrivals) and processes them through servers (resources). The system uses Poisson arrivals to model user logins during peak hours (e.g., 6–9 PM) and exponential service times for OTP verification.

2. Pathao Driver Assignment:

   • Idea Used: Poisson Arrivals + Priority Queues.
   • How: Ride requests arrive as a Poisson process. Pathao’s algorithm assigns drivers based on proximity (a discrete event) while continuously tracking driver availability (continuous state). The system eliminates initial bias by ignoring the first 5% of requests in a new city to stabilize the model.

3. NTC’s 4G Network Planning:

   • Idea Used: Hybrid Simulation.
   • How: NTC uses DES to model call arrivals at cell towers (discrete events) and continuous simulation to track signal interference between towers. This helps optimize tower placement in Kathmandu’s dense urban areas.

4. Daraz’s Warehouse Robotics:

   • Idea Used: Discrete Event + Monte Carlo.
   • How: Daraz simulates order picking in warehouses using DES (robots moving, orders being packed). Monte Carlo methods estimate the probability of delays due to robot malfunctions or traffic jams in the warehouse aisles.

Common Pitfalls and How to Avoid Them

Summary Checklist for Exam Preparation

Before the exam, ensure you can:

1. Draw the three phases of DES as a flowchart.
2. Write the PMF for Poisson and exponential distributions.
3. Explain GPSS blocks (MARK, TABULATE) with a short code example.
4. Differentiate DES vs. hybrid simulation with a Nepali example.
5. Describe how to eliminate initial bias in a simulation trace.
6. Relate DES to real-world systems (eSewa, Pathao, NTC) with specific mechanics.