Queues, scheduling and variability in operations

Separate waiting from service

A queue forms when a ready job cannot immediately obtain its required resource. Arrival time, service start and completion define two useful quantities: waiting time=start−arrival; total time in this system=completion−arrival. Service time fills the interval from start to completion in our simple non-preemptive model. Define whether a reported delay includes that service interval.

For a single first-come, first-served resource, a job starts at the later of its arrival and the previous job’s completion. Completion then equals start plus its service time. Resolve ties explicitly. This small recurrence lets us inspect an event record before relying on a complicated simulation. Real systems may also have setups, priorities, interruptions, deadlines and resource compatibility.

Variability and timing affect the experience

In the even case, arrivals at 0, 2, 4, 6 minutes each need 2 minutes of service. Starts equal arrivals and all waits are zero. In the paired case, arrivals are 0, 0, 4, 4. With job number breaking ties, starts remain 0, 2, 4, 6; waits become 0, 2, 0, 2. Mean waiting is 1 minute although the service blocks are identical.

Both finish all four jobs at 8 minutes. This finite example demonstrates that workload totals do not determine waiting. It is not a steady-state queue forecast, nor does it establish a general waiting-time formula from a few observations. Long-run stochastic analysis requires assumptions about arrivals, service, policy and stability; those assumptions should accompany its conclusions.

A schedule embodies an objective

Consider three jobs available at time zero, needing 6, 2 and 1 minutes. Serving them in that order yields completion times 6, 8, 9. Serving shortest first yields 1, 3, 9. The second sequence lowers the mean completion time in this constructed batch, while the six-minute job waits longer before starting. The final completion time stays 9 because the total work is unchanged.

Shortest-first is not a universal service rule. Urgency, deadlines, fairness, knowledge of durations and compatibility may change the objective. A continuing stream of short jobs could repeatedly postpone a long one under an unrestricted policy. State what is being optimised and inspect individual outcomes, rather than reporting a smaller average as if everyone necessarily benefits.

Calculate the two batch summaries

For order 6, 2, 1, mean completion time is(6+8+9)/3=7.67 minutes. For 1, 2, 6, it is(1+3+9)/3=4.33 minutes. All jobs arrived at zero, so completion time also equals total time in this batch system.

The long job completes at 6 minutes in the first sequence and 9 in the second. Its outcome worsens even though the mean improves. The comparison assumes no setup, no preemption and all three jobs ready initially; it does not resolve deadlines or how a continuing arrival stream should be managed.

Try the reasoning

1. Why do paired arrivals create waiting here?

   Show the answer and reasoning

   Two jobs need the same single resource at once. One must wait for the other’s 2-minute service.

2. Does the unchanged final completion imply unchanged customer experience?

   Show the answer and reasoning

   No. Waiting and individual completion times can change while the total batch work stays the same.

3. What should accompany a claimed scheduling improvement?

   Show the answer and reasoning

   The objective, resource and timing assumptions, policy, aggregate measures and the affected individual or class outcomes.

What to carry forward

Reconstruct the events and choose the objective explicitly; less average waiting can redistribute delay.