Lesson 2: Event Calendars and Clock Advancement

1 Modelling context

Lesson 1 specified the entities, events, resources, and queues of a discrete-event system. This lesson develops the mechanism that drives the simulation: the event calendar and the clock-advancement rule. Together, they determine the order in which events are processed and the timing of every state change.

The event calendar is a list of pending events, ordered by their scheduled time. The simulation always processes the earliest event next. The clock advances to the time of that event, not in fixed steps. The mechanism is exact — it skips over the idle periods between events without computing them. This is why discrete-event simulation is so efficient for systems with long idle intervals.

No event calendar, no DES

A simulation that advances the clock in fixed steps and processes state changes at those steps is not a discrete-event simulation. It might be a discrete-time simulation, but it is not a DES. The defining feature of DES is the event calendar: the model decides which event happens next, and the clock advances to that event's time.

2 Learning objectives

By the end of this lesson you will be able to

Describe the structure and role of the event calendar.
Trace the execution of a discrete-event simulation step by step.
Implement a simple queueing simulation using an event calendar.
Handle the scheduling of new events during event processing.
Explain why the clock advances to the next event time rather than in fixed steps.
Recognise the failure modes of clock advancement and event scheduling.

3 Prerequisite review

Priority queue: A data structure that returns the smallest (or largest) element quickly. The event calendar is a priority queue keyed by event time.
State variable: A quantity that describes the condition of the system at a point in time. The set of state variables defines the model's state space.
Simulation clock: A variable holding the current simulated time. It advances to the timestamp of the next event.
Scheduled event: An event with a known future time, waiting in the event calendar to be processed.

4 Mathematical formulation

The event calendar

The event calendar (also called the future-events list or event queue) is a collection of pending events, each with a scheduled time. It supports two operations:

Schedule. Add a new event with a given time to the calendar.
Remove-next. Return and remove the event with the smallest timestamp.

The calendar is usually implemented as a priority queue, which supports both operations in O(log n) time, where n is the number of pending events.

The clock-advancement rule

The simulation clock t holds the current simulated time. It advances as follows:

If the event calendar is empty, terminate the simulation.
Otherwise, remove the earliest event from the calendar.
Set t to the timestamp of that event.
Process the event: update the state, and possibly schedule new events.
Return to step 1.

The clock never advances to a time when no event occurs. It jumps from one event time to the next. Idle intervals — periods in which no event occurs — pass instantaneously in simulated time.

Scheduling new events

When an event is processed, it may schedule new events. For example, when an arrival event occurs, the simulation usually:

Creates the arriving entity.
Schedules the next arrival event (using the arrival process).
Attempts to start service, if a resource is available.
If service starts, schedules an end-of-service event for t + service_time.
If no resource is available, adds the entity to the appropriate queue.

Similarly, an end-of-service event:

Frees the resource.
Selects the next entity from the queue (according to the queue discipline).
If a queue is non-empty, starts service for the selected entity, and schedules an end-of-service event.

The pattern is universal: each event may schedule one or more subsequent events, and the simulation proceeds until the calendar is empty or the termination condition is met.

Figure 5.6. The main simulation loop. The event calendar holds pending events; the clock advances to the earliest; the state and statistics are updated; new events may be scheduled; the process repeats.

Why the clock advances to the next event

The clock-advancement rule is what makes discrete-event simulation efficient. If the clock advanced in fixed steps, the simulation would waste time on intervals in which nothing happens. By jumping directly from one event to the next, the simulation visits only the moments at which the state changes.

For systems with long idle intervals — a rural emergency service between calls, a computer server between requests — the efficiency gain is enormous. For systems with continuous activity, the event calendar degrades gracefully: many events are scheduled, and the simulation visits nearly every time unit.

5 Worked example

A single-server queue by hand

Consider an M/M/1 queue: single server, Poisson arrivals at rate λ = 1, exponential service times at rate μ = 1.2. Trace the first few events.

Step 1 — Set up.

Clock: t = 0.
State: queue is empty, server is idle.
Event calendar: contains a single arrival event, scheduled at time determined by the first interarrival time.
Random draws: interarrival a₁ = 0.42, service s₁ = 1.15, interarrival a₂ = 1.34, service s₂ = 0.72, …

Step 2 — Process event 1: Arrival at t = 0.42.

Advance clock to t = 0.42.
Create entity 1.
Schedule next arrival at 0.42 + 1.34 = 1.76.
Server is idle; start service.
Schedule departure at 0.42 + 1.15 = 1.57.
Server becomes busy.

Step 3 — Process event 2: Departure at t = 1.57.

Advance clock to t = 1.57.
Server finishes entity 1.
Queue is empty (no other arrivals yet). Server becomes idle.
No new events to schedule.

Step 4 — Process event 3: Arrival at t = 1.76.

Advance clock to t = 1.76.
Create entity 2.
Schedule next arrival.
Server is idle; start service.
Schedule departure at 1.76 + 0.72 = 2.48.

Step 5 — Continue.

The pattern continues: each event advances the clock, updates the state, and may schedule new events. If an arrival occurs while the server is busy, the entity joins the queue instead of starting service. When a departure occurs, if the queue is non-empty, the next entity begins service immediately, and a new departure is scheduled.

Observing the mechanism.

Note that the clock jumps from t = 0.42 to t = 1.57 to t = 1.76, skipping over the intervals in between. In those intervals, nothing happens. The simulation does not compute anything for those intervals. This is the efficiency gain of discrete-event simulation.

6 Verification check

Checks to perform

Trace the first few events by hand. For a small number of events, simulate the process manually and compare against the spreadsheet or code.
Check conservation of entities. Every entity that arrives must eventually depart (or be accounted for at the termination time). Count entities entering and leaving.
Check the clock is non-decreasing. The clock should never go backward. If it does, the event calendar is not returning the earliest event.
Check that scheduled times are in the future. An event should never be scheduled for a time before the current clock.
Test the limiting case of zero arrivals. With no arrivals, the simulation should terminate immediately after the initial event.
Test the limiting case of infinite service rate. With instantaneous service, no queue should form.
Compare against an analytical solution. For an M/M/1 queue, the theoretical mean wait is known (W_q = ρ / (μ(1−ρ)) for ρ = λ/μ < 1). Compare the simulated mean against this.

7 Interpretation

The event calendar is the mechanism that makes the discrete-event simulation a simulation. The state of the system is not computed at every point in continuous time; it is computed only at the moments when it changes. Between those moments, the state is constant, and the simulation does not need to represent it.

Three interpretive points:

The event calendar determines the temporal resolution. The simulation represents only the moments at which events occur. Between them, the state is assumed constant.
The clock-advancement rule is what makes DES efficient. Idle intervals cost nothing. This is why DES is the method of choice for queueing systems with long idle periods.
Every event type must be anticipated in the implementation. The event calendar can only schedule events the code knows how to process. Missing event types produce state changes that cannot occur.

Reporting the event calendar

A complete specification of a DES documents the event types, the state changes each event causes, and the new events each event can schedule. This is the "event graph" of the model and is part of the model documentation.

8 Uncertainty and limitations

The event calendar mechanism is exact given the specification. Its limitations are in the specification and in the arithmetic.

Limitations of the event-calendar mechanism
Limitation	Effect
Floating-point comparison	Simultaneous events may be ordered differently across runs; use a tie-breaking rule if needed
Accumulating numerical error	Long simulations accumulate round-off in times; extreme cases may require higher precision
Simultaneous events	If two events are scheduled at the same time, the order of processing can affect the state
Large event calendars	For simulations with millions of pending events, memory and time may become significant

Simultaneous events require a tie-breaking rule

If two events are scheduled at exactly the same time, the simulation must have a deterministic rule for processing them. Common rules: process by event type priority, or by the order in which events were scheduled. The rule should be documented, because it can affect the results in systems with frequent simultaneous events.

9 Common implementation errors

Watch for these

Scheduling an event in the past. If an event is scheduled for a time before the current clock, the simulation is broken. Check that all scheduled times are in the future.
Forgetting to advance the clock. The clock must be advanced to the timestamp of the event being processed, not left at its previous value.
Processing events out of order. The simulation must always process the earliest event. If the priority queue returns the wrong event, the simulation is incorrect.
Not scheduling a follow-up event. If an arrival event does not schedule the next arrival, the simulation will stop after one arrival.
Losing track of scheduled events. An event scheduled but not stored in the calendar is never processed.
Reusing event objects. If events are stored by reference and reused, the calendar may contain duplicate or corrupted entries. Copy events when scheduling if the language requires it.
Confusing the end-of-service time with the departure time. The end of service is the moment the resource is freed. The departure event is the moment the entity leaves the system. In some models these coincide; in others they are separate.

10 Independent modelling task

Your turn

Take the specification from Lesson 1's task.
List the event types in your system.
For each event type, describe the state changes it causes and the new events it may schedule.
Trace the first five events of your simulation by hand for a specific seed and specific random draws. Record the clock value, the event, the state change, and the new events scheduled.
Implement the event calendar and clock mechanism in a spreadsheet for a simplified version of your system (e.g. one server, one queue, exponential arrivals and service).
Verify the implementation by comparing against a hand trace for the same seed.
Verify against an analytical solution where one exists.

This exercise forms part of Laboratory 10 and the implementation component of Assignment 5.

11 Reflection prompt

Reflect before continuing

Suppose a discrete-event simulation has long idle intervals between events. How does the event calendar mechanism take advantage of this?

Two or three sentences. Consider the difference between advancing the clock to the next event and advancing it in fixed steps.

12 Lesson summary

Key takeaways

The event calendar holds pending events in time order. It is the central data structure of a discrete-event simulation.
The clock advances to the earliest pending event. It does not advance in fixed steps.
Each event may schedule new events. An arrival schedules the next arrival and possibly a departure; a departure may start service for the next entity.
The mechanism is efficient because it skips idle intervals. Long periods of inactivity cost nothing.
Simultaneous events require a tie-breaking rule. Document the rule, because it can affect results.

Coming next

Lesson 3 addresses output analysis: how to extract meaningful statistics from a simulation that begins in an artificial state, and how to avoid warm-up bias.

§ Self-quiz, practice, and homework

Practice exercises

Trace the first three events of the M/M/1 queue from the worked example with a different seed, using interarrival times a₁ = 0.8, a₂ = 0.5, a₃ = 1.2 and service times s₁ = 1.0, s₂ = 0.6, s₃ = 0.9. Record the clock, the event, the state change, and the events scheduled.
Describe the state changes that occur when a departure event is processed and the queue is non-empty.
Explain in two sentences why the clock should never go backward.
Sketch an event calendar after processing three events in a single-server queue with two arrivals and one departure.

Homework problems

Hand trace. For a single-server queue with Poisson arrivals at rate 1 and exponential service at rate 1.2, trace the first ten events by hand using a chosen seed and specific random draws. Record the clock, the event, the state of the queue and server, and the new events scheduled. Produce a table of the trace.
Implement a simplified event calendar. Implement the event-calendar mechanism in a spreadsheet for a single-server queue. Run the simulation for 100 events and confirm that the clock is non-decreasing. Report the number of arrivals and departures and check conservation.
Simultaneous events. Design a system in which two events could occur at the same time. Describe a tie-breaking rule and explain how different rules could produce different results.

Mini project

Implement a discrete-event simulation of a single-server queue in a spreadsheet, using an event calendar. Verify against the analytical M/M/1 results and against a hand trace. Submit the spreadsheet, the hand trace, and a one-page report describing the implementation and verification. This completes Laboratory 10 and feeds Assignment 5.