= Single-server queue departure-time recursion
{title2=$D_n=\max(A_n,D_{n-1})+S_n$}
For a single-server <queue> using <first come first served>, let $A_n$ be the arrival time of job $n$, $S_n\geq0$ its <service time>, and $D_n$ its departure time. Number jobs in arrival order, with an explicit order for ties. Assume the server works whenever a job is waiting, service is not interrupted, and jobs are neither lost nor dropped. If the server is initially free at time 0 and arrivals are nonnegative, set $D_0=0$. Then
$$
D_n=\max(A_n,D_{n-1})+S_n.
$$
The proof is a scheduling constraint: job $n$ cannot start before it arrives or before the preceding job has finished. Under the stated work-conserving rule it starts at the later of those times, then requires $S_n$ more units of time.
Its <queueing delay> and <customer sojourn time> are consequently
$$
W_n=\max(0,D_{n-1}-A_n),\qquad T_n=D_n-A_n=W_n+S_n.
$$
For an original four-job example, use arrivals $(0,1,1,6)$ and service times $(2,3,1,2)$. The third job follows the second in the tie:
$$
\begin{array}{c|rrrr}
n&1&2&3&4\\\hline
A_n&0&1&1&6\\
S_n&2&3&1&2\\
D_n&2&5&6&8\\
W_n&0&1&4&0
\end{array}
$$
The fourth job arrives exactly when the third finishes and therefore has zero <queueing delay>.
The same recursion also gives a sample-path comparison without assuming a particular arrival or service <probability distribution>. If every arrival time and <service time> is increased, and the initial available time is not reduced, induction through the monotone max and addition operations shows that no corresponding departure time decreases. This does not imply that every <queueing delay> increases: a later arrival can spend less time waiting for the same departure opportunity.
An initially busy server requires the appropriate initial available time in place of 0. Multiple servers, priority changes, interruption or abandonment require additional state or a different recursion. These assumptions belong to the model, not to the algebraic max operation.
Back to article page
