A Discrete-Time Single-Server Queue Simulation

Why Simulate a Queue?

A queue forms when customers arrive for service faster than a single server can handle them for some period. Even a simple queue can produce a range of outcomes: a customer may begin service immediately, or may wait while earlier customers are served. Simulation gives a direct way to represent that changing sequence and ask questions such as, “How often does an arrival wait at least two time slots?”

A simulation is only meaningful after the system’s rules are made precise. In particular, we need to specify how arrivals occur, how long service takes, which customer is served next, and exactly when events happen within a time slot. The model below uses one arrival opportunity per slot and one server. It is a simplifying model, not a claim that every real queue behaves this way.

Define the Queue Model and Its Timing

Definition: A discrete-time single-server queue is a model in which time is divided into slots, customers enter one queue, and one server serves customers in arrival order. In the model used here, $A_t$ is the number of arrivals in slot $t$, with $A_t$ equal to 0 or 1. Each customer’s service duration is a positive whole number of slots. A customer’s waiting time is the number of slots from their arrival slot to their service-start slot.

The timing convention is as follows. A customer who arrives in slot $t$ can begin service in slot $t$ if the server is available then. If a customer is being served in slot $t$, service continues through that slot. If it finishes at the end of slot $t$, the next customer can begin in slot $t+1$, not earlier. Customers arriving in the same slot, if the model is extended to permit that, need a specified tie-breaking order. In the model here there is at most one arrival in a slot.

For a basic probabilistic model, suppose each slot has an arrival with probability $p$, independently from slot to slot. Thus $A_t=1$ with probability $p$, and $A_t=0$ otherwise. A service duration $B_i$ is assigned to each customer $i$, independently from a stated distribution of positive whole numbers. We assume the service durations are independent of arrivals and of one another. These assumptions make the model easy to simulate; they may not be appropriate for every real setting.

To generate arrivals in software, draw an independent random number $U_t$ uniformly from $[0,1)$ for each slot and set $A_t=1$ if $U_t<p$, and $A_t=0$ otherwise. To generate service times, draw from the specified service-duration distribution for each arriving customer. These draws are simulated inputs; they are not observed facts about an actual queue.

For customer $i$, let $a_i$ be the arrival slot, $b_i$ the service duration, $s_i$ the service-start slot, and $w_i$ the waiting time. Customers are indexed in arrival order. The server’s first available slot after serving customer $i$ is $s_i+b_i$. Therefore the service start for the next customer is the later of that customer’s arrival slot and the server’s next available slot:

s_1=a_1,\qquad s_i=\max(a_i,\ s_{i-1}+b_{i-1})\quad (i\geq 2), \qquad w_i=s_i-a_i.

The first equation assumes the queue starts empty and the server is idle before the first arrival. For later customers, if the server is already free at the customer’s arrival, service begins on arrival; otherwise, service begins when the previous customer’s service ends. The waiting time is measured in slots and cannot be negative.

Work Through the Customer Schedule

Worked Example: Calculate Waiting Times From a Fixed Schedule

Suppose four customers arrive in slots $1,2,4,$ and $6$, and their service durations are $3,1,2,$ and $1$ slots, respectively. Treat these as hypothetical inputs to the model. There is one server, the queue starts empty, and customers are served in arrival order.

For customer 1, $s_1=a_1=1$, so $w_1=1-1=0$. The server is next available in slot $1+3=4$. Customer 2 arrives in slot 2 and must wait until slot 4, so $s_2=\max(2,4)=4$ and $w_2=4-2=2$. The server is next available in slot $4+1=5$.

Customer 3 arrives in slot 4. The server is available in slot 5, so $s_3=\max(4,5)=5$ and $w_3=5-4=1$. The server is next available in slot $5+2=7$. Customer 4 arrives in slot 6, so $s_4=\max(6,7)=7$ and $w_4=7-6=1$.

\begin{array}{c|c|c|c|c} i & a_i & b_i & s_i & w_i\\ 1 & 1 & 3 & 1 & 0\\ 2 & 2 & 1 & 4 & 2\\ 3 & 4 & 2 & 5 & 1\\ 4 & 6 & 1 & 7 & 1 \end{array}

The waits are $0,2,1,$ and $1$ slots. The first customer starts immediately, while each of the next three waits at least one slot. The arithmetic follows the timing convention: the first service occupies slots 1 through 3, and the second service begins in slot 4.

A Recursion Directly for Waiting Time

The service-start rule can also be expressed as an update to waiting time. This form makes clear how earlier congestion carries forward to later arrivals. The result is a consequence of the definitions, not an additional assumption.

Result: For customers $i-1$ and $i$ in arrival order, $$ w_i=\max\bigl(0,\ w_{i-1}+b_{i-1}-(a_i-a_{i-1})\bigr). $$ This formula applies when the queue starts empty and customers are served in arrival order.

To derive it, start with $s_i=\max(a_i,s_{i-1}+b_{i-1})$ and subtract $a_i$ from both sides. Since subtracting the same value from both arguments of a maximum preserves the maximum, this gives

\begin{aligned} w_i &=s_i-a_i\\ &=\max(a_i,\ s_{i-1}+b_{i-1})-a_i\\ &=\max(0,\ s_{i-1}+b_{i-1}-a_i). \end{aligned}

By definition, $s_{i-1}=a_{i-1}+w_{i-1}$. Substituting this expression gives

w_i =\max\bigl(0,\ a_{i-1}+w_{i-1}+b_{i-1}-a_i\bigr) =\max\bigl(0,\ w_{i-1}+b_{i-1}-(a_i-a_{i-1})\bigr).

The time between the two arrivals is $a_i-a_{i-1}$ slots. If that gap is at least the previous customer’s wait plus service duration, the server catches up and $w_i=0$. Otherwise, the difference is the next customer’s wait.

Worked Example: Update Waiting Time Across Arrivals

Suppose three customers arrive in slots $2,3,$ and $5$, with service durations $2,2,$ and $1$ slots. Assume the queue is initially empty and the listed durations are hypothetical model inputs.

Customer 1 starts in slot 2, so $w_1=0$. For customer 2, the gap since the previous arrival is $3-2=1$ slot. The waiting-time recursion gives

w_2=\max(0,\ 0+2-1)=1.

Customer 2 therefore starts in slot $3+1=4$. The gap from customer 2’s arrival to customer 3’s arrival is $5-3=2$ slots. Thus

w_3=\max(0,\ 1+2-2)=1.

The service starts are slots $2,4,$ and $6$, and the waits are $0,1,$ and $1$ slots. Customer 3 arrives two slots after customer 2, but that gap is not enough for the server to eliminate the one-slot wait already present plus the two-slot service.

From One Schedule to a Simulation

One simulated schedule illustrates how the queue behaves for one set of random inputs. To estimate how often an outcome occurs under the model, repeat the simulation many times. Each repetition is a separate run: generate a new sequence of slot arrivals and new service durations, then apply the same service and timing rules. A quantity such as “the fraction of customers who wait at least one slot” can be recorded for each run or pooled across runs, provided the denominator is defined consistently.

Here is the basic procedure for a run that generates arrivals through slot $T$:

Generate arrivals.
For each slot from 1 through $T$, generate $A_t$ according to the stated arrival rule. Record the arrival slot for each customer.

Generate service durations.
For each arriving customer, generate a positive whole-number duration $b_i$ from the stated service distribution.

Schedule service.
In arrival order, calculate $s_i=\max(a_i,s_{i-1}+b_{i-1})$, beginning with $s_1=a_1$, and then calculate $w_i=s_i-a_i$.

Record the outcome.
Count or summarize the waits relevant to the question. Repeat with new random inputs if estimating model-based probabilities or averages.

For example, if the question is about the probability that a customer waits at least two slots, define a success as $w_i\geq 2$. Across simulated customers, the proportion meeting that condition estimates the probability for an arrival selected under the simulation design. State whether the estimate pools customers across runs or averages run-specific proportions, because those calculations can differ when runs have different numbers of arrivals.

Worked Example: Estimate a Waiting Probability From Repeated Runs

Consider three hypothetical simulation runs. In each, count customers whose wait is at least one slot. The arrival and service schedules below are inputs generated for illustration; they are not observations from a real queue.

In run 1, arrivals are in slots $1,2,4$, with durations $2,1,2$. The service starts are $1,3,4$, giving waits $0,1,0$. Thus 1 of 3 customers waits at least one slot.

In run 2, arrivals are in slots $1,3,4$, with durations $1,2,1$. The starts are $1,3,5$, giving waits $0,0,1$. Again, 1 of 3 customers waits at least one slot.

In run 3, arrivals are in slots $2,3,5$, with durations $2,2,1$. The starts are $2,4,6$, giving waits $0,1,1$. Thus 2 of 3 customers wait at least one slot. Pooling all three runs gives 4 customers with waits of at least one slot out of 9 customers total:

\widehat{P}(W\geq 1\text{ slot}) =\frac{1+1+2}{3+3+3} =\frac{4}{9} \approx 0.444.

The pooled simulation estimate is about 0.444, or 44.4%. It estimates the proportion of arrivals that wait at least one slot under this model and simulation design. Three runs provide only a small illustration; the estimate can vary substantially with new random inputs. More repetitions are generally needed for a stable estimate, and simulation estimates are not exact probabilities.

Stopping the Simulation and Interpreting the Results

A simulation with arrivals generated only through slot $T$ may still have customers in the system when that arrival period ends. A customer already receiving service has a known waiting time, because their service-start slot has occurred. A customer still waiting has not yet had a service-start slot, so their final waiting time is not yet known. Do not treat that unfinished wait as a completed value.

If the goal is to calculate every arriving customer’s completed wait, continue the service schedule after slot $T$ until all customers who arrived by $T$ have started service. If the goal also requires service completions, continue until their services finish. Alternatively, define the outcome using only information available by the stopping point, and explain that definition. The choice depends on the question being simulated.

The queue model’s assumptions also limit what its results mean. At most one arrival per slot rules out multiple arrivals in the same slot. Independent arrivals with a constant $p$ rule out changing arrival rates and dependence between neighboring slots. Independent service durations rule out service times that change systematically with queue conditions or customer characteristics. The single-server and arrival-order rules exclude multiple servers and priority service. A simulation can be internally consistent and still be a poor model of a particular setting.

Common Mistakes

Using an unstated event order. If service completion and arrival timing are unclear, the same inputs can produce different waits. State when arrivals occur and when the next service may start.
Letting two customers use one server at once. Service for customer $i$ occupies $b_i$ slots, so the next start cannot be earlier than $s_i+b_i$.
Confusing arrival time with service-start time. The waiting time is $s_i-a_i$, not the service duration $b_i$.
Calling an unfinished wait zero. If a customer is still waiting when the simulation stops, their eventual service-start slot is unknown. Their wait is not yet complete.
Overgeneralizing from a simulation estimate. A simulated proportion estimates an outcome under the model’s assumptions; it does not establish that the same proportion holds in a real queue.

Key takeaway: A queue simulation depends on explicit arrival, service, and timing rules. Generate inputs under those rules, schedule each customer in arrival order, compute $w_i=s_i-a_i$, and interpret repeated-run summaries as estimates for the stated model.

Check Your Understanding

Try these questions using the timing convention in this tutorial.

A customer arrives in slot 5. The server becomes available in slot 8. What are the customer’s service-start slot and waiting time?
Two customers arrive in slots 1 and 4. The first has a service duration of 3 slots. Does the second customer wait? Show how the start rule determines the answer.
Explain why a customer who is already receiving service when arrivals stop has a known waiting time, while a customer still waiting may not.
What assumptions are made when each slot has an independent arrival probability $p$, and service durations are independently drawn from one fixed distribution?
Across repeated runs, 12 of 30 simulated customers wait at least two slots. Give the pooled estimate and state what it estimates.