  Consider the workload process for a single server queue with deterministic
service times in which customers arrive according to a scheduled traffic
process. A scheduled arrival sequence is one in which customers are scheduled
to arrive at constant interarrival times, but each customer actual arrival time
is perturbed from her scheduled arrival time by a random perturbation. In this
paper, we consider a critically loaded queue in which the service rate equals
the arrival rate. Unlike a queue fed by renewal traffic, this queue can be
stable even in the presence of critical loading. We identify a necessary and
sufficient condition for stability when the perturbations have finite mean.
Perhaps surprisingly, the criterion is not reversible, in the sense that such a
queue can be stable for a scheduled traffic process in forward time, but
unstable for the time-reversal of the same traffic process.
