Single-Server Queue: Event-by-Event Simulation

This section follows a computer simulation of a single-server FIFO queue one event at a time. Starting from an empty system at t = 0, we apply the arrival and departure event routines, take a snapshot of the computer representation after each of the 13 events, and stop at t = 8.6 when the sixth customer finishes waiting. The report generator then turns the statistical counters into the three measures of performance.

Objectives

• Recall the queueing ideas the simulation needs: arrivals, service, FIFO, delay in queue, Q(t) and B(t).
• Describe how a discrete-event simulation program is organized around the next-event time advance.
• Name every state variable, the event list and the four statistical counters.
• Apply the exact update rules of the arrival and departure event routines.
• Trace all 13 events of the exercise to t = 8.6 and produce each snapshot.
• Compute d(n), q(n) and u(n) and explain what each one says about the system.

1. Queueing ideas we need

Key elements

• Customer: anything that arrives at a facility and requires service (people, machines, trucks, email).
• Server: any resource that provides the service. At any moment it is either busy or idle.
• Calling population: the potential customers. Here it is treated as infinite, so the arrival rate does not depend on how many customers are already in the system.
• System capacity: unlimited in this exercise.

A customer who is waiting is in the queue. A customer who is being served is in the system but not in the queue.

Arrivals and service

A_i is the inter-arrival time between customer i-1 and customer i, so the arrival time of a customer is the running sum of the inter-arrival times. S_i is the service time of customer i. Both are independent, identically distributed (IID) random variables, most often exponential, which gives Poisson arrivals. In this exercise they are given:

Queue discipline

The queue discipline decides which waiting customer is served next when the server becomes free: FIFO (first in, first out), LIFO (last in, first out), SIRO (service in random order), SPT (shortest processing time first) or PR (by priority). This lesson uses FIFO, so customers start service in arrival order: customer k uses service time S_k, and the first location of the times-of-arrival array always belongs to the next customer to be served.

Delay in queue

The delay D_i of customer i is the time he waits in the queue: the time his service starts minus his arrival time. If the server is idle when he arrives, service starts at once and D_i = 0; that zero delay still counts as an observed delay. In general, departure time = arrival time + delay + service time.

Q(t) and B(t)

• Q(t) is the number of customers in the queue at time t (the customer in service is not counted).
• B(t) is the busy function: 1 if the server is busy at time t, 0 if it is idle.

Both functions change only at events, so between two events they are flat. The area under each one is a sum of rectangles, value times interval length.

The three measures of performance

d(n) = (D_1 + D_2 + ... + D_n) / n            average delay in queue
q(n) = (area under Q(t) from 0 to T(n)) / T(n)   time-average number in queue
u(n) = (area under B(t) from 0 to T(n)) / T(n)   server utilization

Customers want d(n) and q(n) small; the organization wants u(n) high. A good design balances the two.

The stopping rule

The run stops when n delays in queue have been observed, here n = 6. The check is made after every event. In the exercise this happens at t = 8.6, when customer 5 departs and customer 6 starts service, so T(6) = 8.6. Note that the run does not stop when customer 6 arrives (at 5.6): it stops when he finishes waiting.

2. How the program is organized

Next-event time advance

1. Set the simulation clock to 0.
2. Read the times of future events from the event list.
3. Advance the clock to the most imminent event, the smallest time in the list.
4. Execute that event: update the system state and the statistical counters, and possibly the event list.
5. Repeat until the stopping rule is satisfied.

The clock jumps from one event to the next, and periods of inactivity are skipped. The alternative, fixed-increment time advance, moves the clock in equal steps and treats every event in a step as happening at its end, which is less accurate.

Components of a discrete-event simulation model

Flow of the main program

Start
  -> Initialization routine: clock = 0, initialize state, counters, event list
  -> repeat:
       Timing routine: next event type i, advance the clock
       Event routine i: update state, update counters, schedule future events
                        (library routine supplies random variates)
       Simulation over?  no -> repeat   yes -> Report generator
  -> Report generator: compute estimates, write report
Stop

In this exercise the A and S values are given, so the library routine simply hands over the next value from the list.

3. The computer representation

State, clock, event list and counters

The times-of-arrival array exists because, when a waiting customer finally starts service, the program needs his arrival time to compute his delay.

Rule 1: update the areas first, with the previous state

lag        = clock - time_of_last_event
area_Q     = area_Q + (number in queue BEFORE the event) x lag
area_B     = area_B + (server status BEFORE the event)   x lag
time_of_last_event = clock

Between the last event and now, the queue length and server status held their old values, so that rectangle is what the counter adds.

Rule 2: the arrival event routine

1. Update both areas with the previous state.
2. Schedule the next arrival: A = clock + A_next.
3. If the server is busy: add 1 to the number in queue and store the clock in the next free location of the times-of-arrival array.
4. If the server is idle: the delay is 0; add 1 to number delayed (total delay is unchanged); set server status to 1; schedule this customer's departure D = clock + S.
5. Set time of last event = clock.

Rule 3: the departure event routine

• Queue empty: update both areas, set server status to 0 and D = ∞, set time of last event = clock.
• Queue not empty: update both areas; compute the delay of the customer entering service as clock minus the first time in the array; add it to total delay and add 1 to number delayed; schedule D = clock + S for the new customer; subtract 1 from the number in queue and move every time in the array up one place; set time of last event = clock.

The delay must be computed before the array is shifted: the entering customer's arrival time sits in the first location only until the shift.

4. Event-by-event walkthrough

The run below has 13 events. For each one: the timing routine's choice, the updates in order, and the snapshot after the event. The first four events are the ones shown on the exercise slides; the rest complete the exercise.

t = 0: initialization

Clock = 0, server idle, queue empty, all counters 0. The first event is always an arrival, so A = A1 = 0.4 and D = ∞.

Event 1, t = 0.4: arrival of customer 1

• Timing routine: event list holds A = 0.4 and D = ∞, the smaller is A = 0.4.
• Areas first, with the previous state: Q: 0 + 0 x (0.4 - 0) = 0 and B: 0 + 0 x (0.4 - 0) = 0.
• Schedule the next arrival: A = 0.4 + 1.2 = 1.6 (uses A2).
• Server idle: customer 1 starts service at once, delay 0, number delayed = 1.
• Server status = 1, schedule the departure: D = 0.4 + 2.0 = 2.4 (uses S1).

Event 2, t = 1.6: arrival of customer 2

• Timing routine: event list holds A = 1.6 and D = 2.4, the smaller is A = 1.6.
• Areas first, with the previous state: Q: 0 + 0 x (1.6 - 0.4) = 0 and B: 0 + 1 x (1.6 - 0.4) = 1.2.
• Schedule the next arrival: A = 1.6 + 0.5 = 2.1 (uses A3).
• Server busy: customer 2 joins the queue, Q = 1, time 1.6 stored in location 1.

Event 3, t = 2.1: arrival of customer 3

• Timing routine: event list holds A = 2.1 and D = 2.4, the smaller is A = 2.1.
• Areas first, with the previous state: Q: 0 + 1 x (2.1 - 1.6) = 0.5 and B: 1.2 + 1 x (2.1 - 1.6) = 1.7.
• Schedule the next arrival: A = 2.1 + 1.7 = 3.8 (uses A4).
• Server busy: customer 3 joins the queue, Q = 2, time 2.1 stored in location 2.

Event 4, t = 2.4: departure of customer 1

• Timing routine: event list holds A = 3.8 and D = 2.4, the smaller is D = 2.4.
• Areas first, with the previous state: Q: 0.5 + 2 x (2.4 - 2.1) = 1.1 and B: 1.7 + 1 x (2.4 - 2.1) = 2.0.
• Customer 2 leaves the queue: delay 2.4 - 1.6 = 0.8, read before the shift.
• Total delay 0 + 0.8 = 0.8, number delayed = 2.
• Schedule the departure: D = 2.4 + 0.7 = 3.1 (uses S2).
• Q = 1, array moves up one place: 2.1.

Event 5, t = 3.1: departure of customer 2

• Timing routine: event list holds A = 3.8 and D = 3.1, the smaller is D = 3.1.
• Areas first, with the previous state: Q: 1.1 + 1 x (3.1 - 2.4) = 1.8 and B: 2.0 + 1 x (3.1 - 2.4) = 2.7.
• Customer 3 leaves the queue: delay 3.1 - 2.1 = 1.0, read before the shift.
• Total delay 0.8 + 1.0 = 1.8, number delayed = 3.
• Schedule the departure: D = 3.1 + 0.2 = 3.3 (uses S3).
• Q = 0, array moves up one place: empty.

Event 6, t = 3.3: departure of customer 3

• Timing routine: event list holds A = 3.8 and D = 3.3, the smaller is D = 3.3.
• Areas first, with the previous state: Q: 1.8 + 0 x (3.3 - 3.1) = 1.8 and B: 2.7 + 1 x (3.3 - 3.1) = 2.9.
• Queue empty: server status = 0 and D = ∞.

Event 7, t = 3.8: arrival of customer 4

• Timing routine: event list holds A = 3.8 and D = ∞, the smaller is A = 3.8.
• Areas first, with the previous state: Q: 1.8 + 0 x (3.8 - 3.3) = 1.8 and B: 2.9 + 0 x (3.8 - 3.3) = 2.9.
• Schedule the next arrival: A = 3.8 + 0.2 = 4.0 (uses A5).
• Server idle: customer 4 starts service at once, delay 0, number delayed = 4.
• Server status = 1, schedule the departure: D = 3.8 + 1.1 = 4.9 (uses S4).

Event 8, t = 4.0: arrival of customer 5

• Timing routine: event list holds A = 4.0 and D = 4.9, the smaller is A = 4.0.
• Areas first, with the previous state: Q: 1.8 + 0 x (4.0 - 3.8) = 1.8 and B: 2.9 + 1 x (4.0 - 3.8) = 3.1.
• Schedule the next arrival: A = 4.0 + 1.6 = 5.6 (uses A6).
• Server busy: customer 5 joins the queue, Q = 1, time 4.0 stored in location 1.

Event 9, t = 4.9: departure of customer 4

• Timing routine: event list holds A = 5.6 and D = 4.9, the smaller is D = 4.9.
• Areas first, with the previous state: Q: 1.8 + 1 x (4.9 - 4.0) = 2.7 and B: 3.1 + 1 x (4.9 - 4.0) = 4.0.
• Customer 5 leaves the queue: delay 4.9 - 4.0 = 0.9, read before the shift.
• Total delay 1.8 + 0.9 = 2.7, number delayed = 5.
• Schedule the departure: D = 4.9 + 3.7 = 8.6 (uses S5).
• Q = 0, array moves up one place: empty.

Event 10, t = 5.6: arrival of customer 6

• Timing routine: event list holds A = 5.6 and D = 8.6, the smaller is A = 5.6.
• Areas first, with the previous state: Q: 2.7 + 0 x (5.6 - 4.9) = 2.7 and B: 4.0 + 1 x (5.6 - 4.9) = 4.7.
• Schedule the next arrival: A = 5.6 + 0.2 = 5.8 (uses A7).
• Server busy: customer 6 joins the queue, Q = 1, time 5.6 stored in location 1.

Event 11, t = 5.8: arrival of customer 7

• Timing routine: event list holds A = 5.8 and D = 8.6, the smaller is A = 5.8.
• Areas first, with the previous state: Q: 2.7 + 1 x (5.8 - 5.6) = 2.9 and B: 4.7 + 1 x (5.8 - 5.6) = 4.9.
• Schedule the next arrival: A = 5.8 + 1.4 = 7.2 (uses A8).
• Server busy: customer 7 joins the queue, Q = 2, time 5.8 stored in location 2.

Event 12, t = 7.2: arrival of customer 8

• Timing routine: event list holds A = 7.2 and D = 8.6, the smaller is A = 7.2.
• Areas first, with the previous state: Q: 2.9 + 2 x (7.2 - 5.8) = 5.7 and B: 4.9 + 1 x (7.2 - 5.8) = 6.3.
• Schedule the next arrival: A = 7.2 + 1.9 = 9.1 (uses A9).
• Server busy: customer 8 joins the queue, Q = 3, time 7.2 stored in location 3.

Event 13, t = 8.6: departure of customer 5

• Timing routine: event list holds A = 9.1 and D = 8.6, the smaller is D = 8.6.
• Areas first, with the previous state: Q: 5.7 + 3 x (8.6 - 7.2) = 9.9 and B: 6.3 + 1 x (8.6 - 7.2) = 7.7.
• Customer 6 leaves the queue: delay 8.6 - 5.6 = 3.0, read before the shift.
• Total delay 2.7 + 3.0 = 5.7, number delayed = 6.
• Schedule the departure: D = 8.6 + 0.6 = 9.2 (uses S6).
• Q = 2, array moves up one place: 5.8, 7.2.
• Number delayed = 6 = n: stopping rule met, the report generator runs.

The whole run in one table

The six delays

Total delay = 0 + 0.8 + 1.0 + 0 + 0.9 + 3.0 = 5.7. Customers 1 and 4 found the server idle, so their delay is 0, but each still counts in number delayed.

5. Q(t), B(t) and the areas

Q(t)

Grouping the intervals by queue length:

area under Q(t) = 1 x [(2.1 - 1.6) + (3.1 - 2.4) + (4.9 - 4.0) + (5.8 - 5.6)] + 2 x [(2.4 - 2.1) + (7.2 - 5.8)] + 3 x [(8.6 - 7.2)]
                = 1 x 2.3 + 2 x 1.7 + 3 x 1.4
                = 2.3 + 3.4 + 4.2 = 9.9

This is exactly the value the area-under-Q counter reached at t = 8.6: the event routines build the same sum one rectangle at a time.

B(t)

area under B(t) = 1 x [(3.3 - 0.4) + (8.6 - 3.8)] = 2.9 + 4.8 = 7.7

6. The report generator

Once number delayed reaches 6, the main program calls the report generator:

d(6) = 5.7 / 6   = 0.95
q(6) = 9.9 / 8.6 = 1.15
u(6) = 7.7 / 8.6 = 0.90   (89.5 percent)

The exercise slide writes the utilization as 0.9; to two decimals it is 0.90.

7. Common mistakes

1. Updating the areas with the new state. At t = 2.1 the queue goes from 1 to 2. The correct update is 0 + 1 x (2.1 - 1.6) = 0.5; using the new value gives 0 + 2 x (2.1 - 1.6) = 1.0, which is wrong.
2. Forgetting D = ∞ when the server goes idle. At t = 3.3 the queue is empty, so the server becomes idle and D = ∞; the next event is then the arrival at 3.8. A stale D would make the timing routine pick a departure for a customer who does not exist. Server status must drop to 0 as well, so nothing is added to the area under B(t) from 3.3 to 3.8.
3. Shifting the array before computing the delay. At t = 2.4 the array holds 1.6, 2.1. Customer 2's delay is 2.4 - 1.6 = 0.8. Shifting first would give 2.4 - 2.1 = 0.3, which is customer 3's arrival time, not customer 2's.
4. The stopping rule. The run stops when number delayed = 6, at t = 8.6, so T(6) = 8.6. It does not stop when customer 6 arrives (5.6) or when he departs (9.2).

Quick self-check: zero delays count in number delayed, the counters never decrease, and after every event the time of last event equals the clock.

8. Practice

Trace each run event by event, starting from the t = 0 snapshot, until number delayed reaches n. Give the snapshot after every event, then compute d(n), q(n) and u(n). Answers are at the end of this page.

Run 1: n = 4

Run 2: n = 5

Checklist for every event:

1. Pick the smaller of A and D and set the clock to it.
2. Add the previous queue length times the lag, and the previous server status times the lag, to the two areas.
3. Arrival: schedule the next arrival, then join the queue or start service.
4. Departure: an empty queue gives D = ∞; otherwise compute the delay first, then shift.
5. Set time of last event = clock and compare number delayed with n.

Key takeaways

• The clock jumps from event to event: clock = min(A, D).
• Every event updates the areas first, with the previous state.
• An idle server always means D = ∞.
• A departure reads the delay before shifting the times-of-arrival array.
• The run ends when number delayed = n, and T(n) is that clock value.
• The report generator divides total delay by n, and each area by T(n).

Answers

Run 1

Event 1, t = 0.5: arrival of customer 1. Areas first, with the previous state: Q: 0 + 0 x (0.5 - 0) = 0 and B: 0 + 0 x (0.5 - 0) = 0. Schedule the next arrival: A = 0.5 + 0.3 = 0.8 (uses A2). Server idle: customer 1 starts service at once, delay 0, number delayed = 1. Server status = 1, schedule the departure: D = 0.5 + 1.2 = 1.7 (uses S1).

Event 2, t = 0.8: arrival of customer 2. Areas first, with the previous state: Q: 0 + 0 x (0.8 - 0.5) = 0 and B: 0 + 1 x (0.8 - 0.5) = 0.3. Schedule the next arrival: A = 0.8 + 1.8 = 2.6 (uses A3). Server busy: customer 2 joins the queue, Q = 1, time 0.8 stored in location 1.

Event 3, t = 1.7: departure of customer 1. Areas first, with the previous state: Q: 0 + 1 x (1.7 - 0.8) = 0.9 and B: 0.3 + 1 x (1.7 - 0.8) = 1.2. Customer 2 leaves the queue: delay 1.7 - 0.8 = 0.9, read before the shift. Total delay 0 + 0.9 = 0.9, number delayed = 2. Schedule the departure: D = 1.7 + 0.6 = 2.3 (uses S2). Q = 0, array moves up one place: empty.

Event 4, t = 2.3: departure of customer 2. Areas first, with the previous state: Q: 0.9 + 0 x (2.3 - 1.7) = 0.9 and B: 1.2 + 1 x (2.3 - 1.7) = 1.8. Queue empty: server status = 0 and D = ∞.

Event 5, t = 2.6: arrival of customer 3. Areas first, with the previous state: Q: 0.9 + 0 x (2.6 - 2.3) = 0.9 and B: 1.8 + 0 x (2.6 - 2.3) = 1.8. Schedule the next arrival: A = 2.6 + 0.4 = 3.0 (uses A4). Server idle: customer 3 starts service at once, delay 0, number delayed = 3. Server status = 1, schedule the departure: D = 2.6 + 0.7 = 3.3 (uses S3).

Event 6, t = 3.0: arrival of customer 4. Areas first, with the previous state: Q: 0.9 + 0 x (3.0 - 2.6) = 0.9 and B: 1.8 + 1 x (3.0 - 2.6) = 2.2. Schedule the next arrival: A = 3.0 + 0.6 = 3.6 (uses A5). Server busy: customer 4 joins the queue, Q = 1, time 3.0 stored in location 1.

Event 7, t = 3.3: departure of customer 3. Areas first, with the previous state: Q: 0.9 + 1 x (3.3 - 3.0) = 1.2 and B: 2.2 + 1 x (3.3 - 3.0) = 2.5. Customer 4 leaves the queue: delay 3.3 - 3.0 = 0.3, read before the shift. Total delay 0.9 + 0.3 = 1.2, number delayed = 4. Schedule the departure: D = 3.3 + 1.1 = 4.4 (uses S4). Q = 0, array moves up one place: empty. Number delayed = 4 = n: stopping rule met, the report generator runs.

T(4) = 3.3
d(4) = 1.2 / 4 = 0.30
q(4) = 1.2 / 3.3 = 0.36
u(4) = 2.5 / 3.3 = 0.76   (75.8 percent)

Run 2

Event 1, t = 1.0: arrival of customer 1. Areas first, with the previous state: Q: 0 + 0 x (1.0 - 0) = 0 and B: 0 + 0 x (1.0 - 0) = 0. Schedule the next arrival: A = 1.0 + 0.5 = 1.5 (uses A2). Server idle: customer 1 starts service at once, delay 0, number delayed = 1. Server status = 1, schedule the departure: D = 1.0 + 1.4 = 2.4 (uses S1).

Event 2, t = 1.5: arrival of customer 2. Areas first, with the previous state: Q: 0 + 0 x (1.5 - 1.0) = 0 and B: 0 + 1 x (1.5 - 1.0) = 0.5. Schedule the next arrival: A = 1.5 + 0.6 = 2.1 (uses A3). Server busy: customer 2 joins the queue, Q = 1, time 1.5 stored in location 1.

Event 3, t = 2.1: arrival of customer 3. Areas first, with the previous state: Q: 0 + 1 x (2.1 - 1.5) = 0.6 and B: 0.5 + 1 x (2.1 - 1.5) = 1.1. Schedule the next arrival: A = 2.1 + 2.5 = 4.6 (uses A4). Server busy: customer 3 joins the queue, Q = 2, time 2.1 stored in location 2.

Event 4, t = 2.4: departure of customer 1. Areas first, with the previous state: Q: 0.6 + 2 x (2.4 - 2.1) = 1.2 and B: 1.1 + 1 x (2.4 - 2.1) = 1.4. Customer 2 leaves the queue: delay 2.4 - 1.5 = 0.9, read before the shift. Total delay 0 + 0.9 = 0.9, number delayed = 2. Schedule the departure: D = 2.4 + 0.8 = 3.2 (uses S2). Q = 1, array moves up one place: 2.1.

Event 5, t = 3.2: departure of customer 2. Areas first, with the previous state: Q: 1.2 + 1 x (3.2 - 2.4) = 2.0 and B: 1.4 + 1 x (3.2 - 2.4) = 2.2. Customer 3 leaves the queue: delay 3.2 - 2.1 = 1.1, read before the shift. Total delay 0.9 + 1.1 = 2.0, number delayed = 3. Schedule the departure: D = 3.2 + 0.5 = 3.7 (uses S3). Q = 0, array moves up one place: empty.

Event 6, t = 3.7: departure of customer 3. Areas first, with the previous state: Q: 2.0 + 0 x (3.7 - 3.2) = 2.0 and B: 2.2 + 1 x (3.7 - 3.2) = 2.7. Queue empty: server status = 0 and D = ∞.

Event 7, t = 4.6: arrival of customer 4. Areas first, with the previous state: Q: 2.0 + 0 x (4.6 - 3.7) = 2.0 and B: 2.7 + 0 x (4.6 - 3.7) = 2.7. Schedule the next arrival: A = 4.6 + 0.3 = 4.9 (uses A5). Server idle: customer 4 starts service at once, delay 0, number delayed = 4. Server status = 1, schedule the departure: D = 4.6 + 1.2 = 5.8 (uses S4).

Event 8, t = 4.9: arrival of customer 5. Areas first, with the previous state: Q: 2.0 + 0 x (4.9 - 4.6) = 2.0 and B: 2.7 + 1 x (4.9 - 4.6) = 3.0. Schedule the next arrival: A = 4.9 + 0.4 = 5.3 (uses A6). Server busy: customer 5 joins the queue, Q = 1, time 4.9 stored in location 1.

Event 9, t = 5.3: arrival of customer 6. Areas first, with the previous state: Q: 2.0 + 1 x (5.3 - 4.9) = 2.4 and B: 3.0 + 1 x (5.3 - 4.9) = 3.4. Schedule the next arrival: A = 5.3 + 1.1 = 6.4 (uses A7). Server busy: customer 6 joins the queue, Q = 2, time 5.3 stored in location 2.

Event 10, t = 5.8: departure of customer 4. Areas first, with the previous state: Q: 2.4 + 2 x (5.8 - 5.3) = 3.4 and B: 3.4 + 1 x (5.8 - 5.3) = 3.9. Customer 5 leaves the queue: delay 5.8 - 4.9 = 0.9, read before the shift. Total delay 2.0 + 0.9 = 2.9, number delayed = 5. Schedule the departure: D = 5.8 + 1.3 = 7.1 (uses S5). Q = 1, array moves up one place: 5.3. Number delayed = 5 = n: stopping rule met, the report generator runs.

T(5) = 5.8
d(5) = 2.9 / 5 = 0.58
q(5) = 3.4 / 5.8 = 0.59
u(5) = 3.9 / 5.8 = 0.67   (67.2 percent)