Due-Date Scheduling : Asymptotic Optimality of Generalized Longest Queue and Generalized Largest Delay Rules

Consider the following due-date scheduling problem in a multiclass, acyclic, single-station service system: any class k job arriving at time t must be served by its due date t D_{k}. Equivalently, its delay ¦Ó_{k} must not exceed a given delay or lead-time D_{k}. In a stochastic system the constraint ¦Ó_{k}¡ÜD_{k} must be interpreted in a probabilistic sense. Regardless of the precise probabilistic formulation, however, the associated optimal control problem is intractable with exact analysis. This article proposes a new formulation that incorporates the constraint through a sequence of convex-increasing delay cost functions. This formulation reduces the intractable optimal scheduling problem into one for which the Generalized c¦Ì (Gc¦Ì) scheduling rule is known to be asymptotically optimal. The Gc¦Ì rule simplifies here to a generalized longest queue (GLQ) or generalized largest delay (GLD) rule, which are defined as follows. Let N_{k} be the number of class k jobs in system, ¦Ë_{k} their arrival rate and a_{k} the age of their oldest job in the system. GLQ and GLD are dynamic priority rules, parameterized by ¦È: GLQ(¦È) serves FIFO within class and prioritizes the class with highest index ¦È_{k}N_{k}, whereas GLD(¦È) uses index ¦È_{k}¦Ë_{k}a_{k}. The argument is presented first intuitively, but is followed by a limit analysis that expresses the cost objective in terms of the maximal due-date violation probability. This proves that GLQ(¦È_{∗}) and GLD(¦È_{∗}), where ¦È_{∗,k}=1/¦Ë_{k}D_{k}, asymptotically minimize the probability of maximal due-date violation in heavy traffic. Specifically, they minimize liminf_{n¡ú¡Þ}Pr{max_{k}sup_{s¡Ê[0,t]}((¦Ó_{k}(ns))/(n^{1/2}D_{k}))¡Ýx} for all positive t and x, where ¦Ó_{k}(s) is the delay of the most recent class k job that arrived before time s. GLQ with appropriate parameter ¦È_{¦Á} also reduces "total variability" because it asymptotically minimizes a weighted sum of ¦Á^{th} delay moments. Properties of GLQ and GLD, including an expression for their asymptotic delay distributions, are presented