Optimal scheduling with strict deadlines

The authors consider the problem of dynamic scheduling of customers (messages) in time-critical environments. First, consider a single station (communication node) and assume that each customer (message) must begin service (transmission) by an individually varying ‘extinction’ time or else it is lost. The authors are interested in minimizing, in the sense of stochastic order, the number of messages lost over any time interval. They prove a variety of results that establish the optimality of the STE (shortest time to extinction) policy under rather general conditions. Similar results are also shown when messages have constraints on their complete transmission times. If the scheduler is allowed to take decisions based only on the distributions of the deadlines (rather than their exact values), similar but somewhat stronger results are proven. Finally, the authors consider a network of M stations in tandem under the hypothesis that a message is never lost and is scheduled irrespective of whether its extinction time (also called due date in this case) has expired or not. Again, under fairly general assumptions on the arrivals, deadlines, and services, they show that the EDD (earliest due date) policy minimizes a form of average tardiness incurred over a finite operating horizon among all nonidling, nonpreemptive policies. The authors formulate these problems in the context of stochastic dominance, and use simple interchange arguments to establish all the present results.