 Single-server queue departure-time recursion

For a single-server queue using first come first served, let $A_n$ be the arrival time of job $n$, $S_n\ge 0$ 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$. ThenThe 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 consequentlyFor 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: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.