Optimal Scheduling with Strict Deadlines .

Abstract

We consider the problem of dynamic scheduling of customers (messages) in time-critical environments. First, we 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. We are interested in minimizing in the sense of stochastic order, the number of messages lost over any time interval. We 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 distribution of the deadlines (rather than their exact values), similar but somewhat stronger results are proven. Finally, we 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, we show that the EDD (Earliest Due Date) policy minimizes a form of average tardiness incurred over a finite operating horizon among all nonidling, nonpremptive policies. We formulate these problems in the context of stochastic dominance, and use simple interchange arguments to establish all our results.