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 (tau) k must not exceed a given delay or lead-time D k . In a stochastic system, the constraint (tau) k (le) 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 which 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(mu) (G c(mu) ) scheduling rule is known to be asymptotically optimal. The G c(mu) 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, (lambda) 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 (theta) : GLQ( (theta) ) serves FIFO within class and prioritizes the class with highest index (theta) k N k , whereas GLD( (theta) ) uses index (theta) k (lambda) 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( (theta) * ) and GLD( (theta) * ), where (theta) * ,k = 1/ (lambda) k D k , asymptotically minimize the probability of maximal due-date violation in heavy traffic. Specifically, they minimize \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$\mbox{lim}\, \mbox{inf}_{n\to\infty}\mbox{Pr}\{\max_k \mbox{sup}_{s\in [0,t]}\tfrac{\tau_k(ns)}{n^{1/2}D_k}\geq x\}$\end{document} for all positive t and x , where (tau) k ( s ) is the delay of the most recent class k job that arrived before time s . GLQ with appropriate parameter (theta) (alpha) also reduces “total variability” because it asymptotically minimizes a weighted sum of (alpha)th delay moments. Properties of GLQ and GLD, including an expression for their asymptotic delay distributions, are presented.