Problem 406076 · medium · Level 04 Non-Linear Data Structures

The Queue at the Coffee Cart

simulation · exponential distribution · queues · expected waiting time

A coffee cart has one barista. Customers arrive at random moments, on average arrival_rate per minute, and making a coffee takes a random time, on average 1 / service_rate minutes. Customers are served in order of arrival; a customer who arrives while the barista is busy waits until everyone before them has been served.

Write cart_queue(arrival_rate, service_rate, customers, patience, seed) that simulates the first customers customers, using the generator exactly like this:

  • Create one generator rng = random.Random(seed). The clock starts at 0 with nobody at the cart.
  • For each customer in turn: first gap = rng.expovariate(arrival_rate) (the time since the previous arrival, or since the start for the first customer), then service = rng.expovariate(service_rate) (how long their coffee takes).

Return a tuple:

  1. the average waiting time (time from arrival until the barista starts on their coffee),
  2. the fraction of customers who waited more than patience minutes,
  3. the longest wait,
  4. the long-run average wait that queueing theory predicts for this cart, arrival_rate / (service_rate · (service_rate - arrival_rate)), when arrival_rate < service_rate, and None otherwise (then the queue grows without limit).

Examples

Input:  arrival_rate = 1, service_rate = 1.25, customers = 4, patience = 0.2, seed = 2
Output: (0.850694266547941, 0.75, 2.304346236382323, 3.2)
Explanation: the draws are 3.124, 2.363 | 0.058, 0.071 | 1.805, 1.065 | 1.108, 0.295.
Customer 1 arrives at 3.124 and leaves at 5.487. Customer 2 arrives at 3.182 and waits
2.305 minutes. Customer 3 arrives at 4.987 and waits until 5.558 (0.571). Customer 4
arrives at 6.095 and waits until 6.623 (0.528). Mean wait 0.851.

Input:  arrival_rate = 0.5, service_rate = 1, customers = 100000, patience = 2, seed = 7
Output: (1.009898923673094, 0.1832, 19.014669061085442, 1.0)

Constraints

  • 0 < arrival_rate, 0 < service_rate, 1 <= customers <= 2 * 10**5, 0 <= patience
  • floats are compared with a tolerance of 1e-6; use no randomness other than rng

Goals

  • Simulate a queue customer by customer from random arrival gaps and service times
  • Update each customer's waiting time from the previous customer's finishing time
  • Compare a simulated long-run average with the known formula, and see when none exists
Starting Python…