Due-date scheduling: Asymptotic optimality of generalized longest queue and generalized largest delay rules
成果类型：
Article
署名作者：
Van Mieghem, JA
署名单位：
Northwestern University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
发表日期：
2003
页码：
113-122
关键词：
摘要：
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) less than or equal to 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 cmu (Gcmu) scheduling rule. is known to be asymptotically optimal. The Gcmu 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 lim inf(n-->infinity)Pr{max(k)sup(sis an element of[0,t])tau(k)(ns)/n(1/2)D(k) greater than or equal to x} 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 alphath delay moments. Properties of GLQ and GLD, including an expression for their asymptotic delay distributions, are presented.