Practical 4 continued: Simulating a Customer Service Queue

Read the last column. It grows, because with a 45 per cent chance of an arrival every minute and a service taking two to four minutes, one counter cannot keep up. That is the finding the simulation exists to produce, and the next section turns it into a number.

Why one counter is not enough, in arithmetic

Before running anything, the answer can be estimated, and doing so is what makes a simulation a check rather than a guess.

arrival_chance = 0.45
service_low, service_high = 2, 4

arrivals_per_minute = arrival_chance
mean_service = (service_low + service_high) / 2
work_per_minute = arrivals_per_minute * mean_service

print(f"customers arriving per minute : {arrivals_per_minute}")
print(f"average minutes to serve one  : {mean_service}")
print(f"counter-minutes of work created each minute: "
      f"{arrivals_per_minute} × {mean_service} = {work_per_minute}")
print()
print(f"one counter supplies 1 counter-minute per minute.")
print(f"needed: {work_per_minute}, supplied: 1, so one counter is short by "
      f"{work_per_minute - 1:.2f}")
print(f"the smallest number of counters that keeps up is "
      f"{int(work_per_minute) + 1 if work_per_minute % 1 else int(work_per_minute)}")

customers arriving per minute : 0.45
average minutes to serve one  : 3.0
counter-minutes of work created each minute: 0.45 × 3.0 = 1.35

one counter supplies 1 counter-minute per minute.
needed: 1.35, supplied: 1, so one counter is short by 0.35
the smallest number of counters that keeps up is 2

That is the whole of queueing theory in five lines. If more work arrives each minute than the counters can do, the queue grows without limit. One counter can do one counter-minute per minute, and this system creates more than that, so the queue must grow. A simulation cannot contradict that arithmetic; it shows how bad it gets and how quickly.

Several counters

import random
from collections import deque


def simulate(counters, minutes=200, arrival_chance=0.45,
             service_range=(2, 4), seed=7):
    """Run the queue and return (average wait, longest wait, left waiting, served)."""
    random.seed(seed)
    queue = deque()
    free_at = [0] * counters
    waits = []
    served = 0
    longest_queue = 0
    next_number = 1

    for minute in range(minutes):
        if random.random() < arrival_chance:
            queue.append(minute)
            next_number += 1
        for i in range(counters):
            if free_at[i] <= minute and queue:
                arrived_at = queue.popleft()
                waits.append(minute - arrived_at)
                free_at[i] = minute + random.randint(*service_range)
                served += 1
        longest_queue = max(longest_queue, len(queue))

    average = sum(waits) / len(waits) if waits else 0.0
    return average, max(waits) if waits else 0, len(queue), served, longest_queue


print(f"  {'counters':>9} {'avg wait':>10} {'worst wait':>12} {'left waiting':>14}"
      f" {'served':>8} {'longest queue':>15}")
for counters in [1, 2, 3, 4]:
    average, worst, left, served, longest = simulate(counters)
    print(f"  {counters:>9} {average:>10.2f} {worst:>12} {left:>14} {served:>8} "
          f"{longest:>15}")

   counters   avg wait   worst wait   left waiting   served   longest queue
          1      32.27           67             26       67              26
          2       0.44            3              0       88               2
          3       0.09            1              0       97               1
          4       0.00            0              0       96               0

Read the table down. One counter is hopeless and two are enough, and the third and fourth buy almost nothing. That is the answer a manager actually wants, and it is why a simulation is written: the arithmetic said "more than one", and the simulation says how much more and what it is worth.

This is MU's Course Objective 8 in its purest form. The structure chosen is a queue, and the justification is that fairness requires the longest waiting customer to be served next, which is exactly FIFO.

The queue length over time, drawn

import random
from collections import deque


def queue_lengths(counters, minutes=60, arrival_chance=0.45,
                  service_range=(2, 4), seed=7):
    random.seed(seed)
    queue = deque()
    free_at = [0] * counters
    lengths = []
    for minute in range(minutes):
        if random.random() < arrival_chance:
            queue.append(minute)
        for i in range(counters):
            if free_at[i] <= minute and queue:
                queue.popleft()
                free_at[i] = minute + random.randint(*service_range)
        lengths.append(len(queue))
    return lengths


for counters in [1, 2]:
    lengths = queue_lengths(counters)
    print(f"{counters} counter(s), the queue length each minute for 60 minutes:")
    for start in range(0, 60, 20):
        row = lengths[start:start + 20]
        bars = "".join(str(min(n, 9)) for n in row)
        print(f"  minute {start:>2} to {start + 19:>2}: {bars}")
    print(f"  ends at {lengths[-1]}, worst {max(lengths)}")
    print()

1 counter(s), the queue length each minute for 60 minutes:
  minute  0 to 19: 01122223333455445656
  minute 20 to 39: 66566666665677678776
  minute 40 to 59: 67666777888777678889
  ends at 9, worst 9

2 counter(s), the queue length each minute for 60 minutes:
  minute  0 to 19: 00001111211000000000
  minute 20 to 39: 00000000000000000000
  minute 40 to 59: 00100000000000000000
  ends at 0, worst 2

With one counter the digits climb and never come back down. With two they stay near zero. That picture, drawn with nothing but digits, is worth more in a journal than a paragraph claiming the same thing.

A priority queue, for the question that follows

The examiner's next question on this exercise is usually "what if some customers are more urgent". That is no longer a queue: it is a priority queue, and the standard library has one.

import heapq

# (priority, arrival order, name). Lower priority number is served first.
counter = []
for priority, name in [(2, "Aarti"), (1, "Bhavesh, urgent"), (3, "Chetan"),
                       (1, "Divya, urgent"), (2, "Eshan")]:
    heapq.heappush(counter, (priority, len(counter), name))

print("served in this order:")
while counter:
    priority, order, name = heapq.heappop(counter)
    print(f"  priority {priority}  {name}")

served in this order:
  priority 1  Bhavesh, urgent
  priority 1  Divya, urgent
  priority 2  Aarti
  priority 2  Eshan
  priority 3  Chetan

The middle item of the tuple, the arrival order, is what keeps it fair inside one priority level: two customers of priority 1 are served in the order they arrived, because tuples compare item by item. Without it, a heap gives no promise about ties.

A heap is a tree, not an array of this kind, and [Practical 5: the Binary Search Tree, Create, Insert and Search] is where trees begin.

The one line that makes this checkable

import random

print("with the seed set, the same numbers every time:")
for _ in range(3):
    random.seed(7)
    print("  ", [random.randint(1, 100) for _ in range(6)])

print("without it, a different sequence every run, which nobody can check:")
random.seed()
first = [random.randint(1, 100) for _ in range(6)]
random.seed()
second = [random.randint(1, 100) for _ in range(6)]
print("   two unseeded runs agreed?", first == second)

with the seed set, the same numbers every time:
   [42, 20, 51, 84, 7, 10]
   [42, 20, 51, 84, 7, 10]
   [42, 20, 51, 84, 7, 10]
without it, a different sequence every run, which nobody can check:
   two unseeded runs agreed? False

random.seed(7) at the top of a simulation is not optional in a journal entry. Without it, the teacher cannot reproduce your output, you cannot reproduce it yourself the next day, and a bug that appears once can never be found again. Put the seed in, and say in the writeup that changing it gives a different run of the same system.

Procedure

1. Save as practical2-4b.py. import random and random.seed(7) at the top.
2. Choose an arrival chance and a service time range, and write them as named constants at the top so

they can be changed in one place.

1. Use a deque as the queue, storing the minute each customer arrived.
2. Loop over the minutes. Each minute: maybe add an arrival; free any counter whose service has

finished; start serving from the front of the queue if a counter is free.

1. Record each customer's wait as the minute served minus the minute they arrived.
2. Print a table of minute, arrival, queue length, what the counter did, and who is waiting.
3. Report the average wait, the longest wait, the number served and the number still waiting.
4. Work out on paper how many counters the system needs, from the arrival rate times the mean service

time, before running the multi-counter version.

1. Run the simulation for one, two, three and four counters and tabulate the results.
2. Print the queue length each minute as a row of digits for one counter and for two.

Result

With one counter, an arrival chance of 0.45 and a service time of 2 to 4 minutes, the queue grew throughout the run and customers were still waiting at the end. The arithmetic predicted it: 0.45 arrivals a minute × a mean service of 3 minutes is 1.35 counter-minutes of work created per minute against 1 supplied, so the queue must grow. Over 200 minutes, one counter left an average wait of 32.27 minutes, a worst wait of 67 and 26 customers still waiting; two counters brought the average to 0.44 with nobody left waiting; and three and four counters improved it only to 0.09 and 0.00, so two is the answer. Printing the queue length each minute as digits showed the one counter case climbing and not recovering while the two counter case stayed near zero. All figures are reproducible because random.seed(7) is set.

Where marks are lost

• No seed. The output cannot be reproduced by the teacher or by you.
• Serving from the wrong end. pop() instead of popleft() serves the newest arrival first,

which is a stack, not a queue.

• Not recording the arrival minute, so the wait cannot be computed at all.
• Only one counter tried. The interesting result is how many are needed.
• No arithmetic. One line of arrival rate times mean service predicts the answer and shows you

understand it.

• Reporting only the average wait. The worst wait and the number left waiting are what matter to a

customer.

• Using list.pop(0) for the queue, which is O(n) as the previous chapter measured.
• Constants buried in the loop instead of named at the top.

For the journal

The aim in MU's words, including her own example of a customer service queue. The four row table of what a simulation needs. The seed line, called out, with one sentence saying why. Then the minute by minute table for one counter, which is the entry's centrepiece, and the summary figures under it. Then the arithmetic: arrivals per minute × mean service time against the counters available, and the conclusion that one is not enough. Then the table for one to four counters and the sentence naming the smallest number that works. Then the digit rows of queue length for one and two counters. The conclusion: a queue is the right structure because fairness means serving the longest waiting customer, and the simulation turns a guess about how many counters are needed into a number.

Quick revision

• A simulation needs a clock, arrivals, a queue and one or more servers.
• The queue is FIFO because fairness means the longest waiting customer is next. popleft(), never

pop().

• Store the minute of arrival with each customer; the wait is the minute served minus that.
• random.seed(n) at the top, or nothing in the output can be reproduced or checked.
• The stability test: arrivals per minute × mean service time against the number of counters. If

the work created exceeds the work supplied, the queue grows without limit.

• Here 0.45 × 3 = 1.35 counter-minutes per minute against 1 from one counter, so one counter cannot

keep up and two can.

• Report the average wait, the worst wait, the number served and the number left waiting. The

average alone hides the worst case.

• A queue length printed as a row of digits per minute shows the trend at a glance.
• If some customers are urgent it is a priority queue, built on a heap, O(log n) per

operation. Include the arrival order in the tuple to keep ties fair.

Questions you should be able to answer

1. Why is a queue the right structure for a service counter? Because fairness requires the customer who has waited longest to be served next, which is exactly FIFO.

2. What would happen if you used pop() instead of popleft()? The most recent arrival would be served first. That is a stack, and it is the opposite of fair.

3. Why is random.seed(7) in the program? So the run is reproducible: the teacher can get the same output, you can get it again tomorrow, and a bug that appears once can be found again.

4. How do you compute each customer's wait? Store the minute they arrived, and subtract it from the minute they begin to be served.

5. Without running anything, how do you tell whether one counter is enough? Multiply the arrivals per minute by the mean service time. That is the counter-minutes of work created per minute. If it exceeds the number of counters, the queue grows without limit.

6. Do the arithmetic for an arrival chance of 0.45 and a service time of 2 to 4 minutes. The mean service time is 3 minutes, and 0.45 × 3 = 1.35 counter-minutes per minute. One counter supplies 1, so one is not enough and two are.

7. Why report the worst wait as well as the average? Because an average hides the customer who waited longest, and that is the one who complains.

8. What changes if some customers are urgent? It becomes a priority queue rather than a queue, built on a heap, with O(log n) per operation instead of O(1).

9. In heapq, why put the arrival order in the tuple? Because a heap makes no promise about items of equal priority. Including the arrival order makes tuples compare by priority and then by order, so ties are served fairly.

10. Why does adding a third and fourth counter change so little? Because two already supply more work per minute than arrives, so the queue is already near zero and there is almost nothing left for extra counters to do.