Due-date scheduling: Asymptotic optimality of generalized longest queue and generalized largest delay rules

Jan A. Van Mieghem*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

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 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μ. (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 OLD are dynamic priority rules, parameterized by θ: GLQ(θ) serves FIFO within class and prioritizes the class with highest index θ kN k, whereas GLD(θ) uses index θ kλ ka 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/λ kD k, asymptotically minimize the probability of maximal due-date violation in heavy traffic. Specifically, they minimize lim inf n→ Pr{max ksup s≡[0,t] τ k(ns)/n 1/2D 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 OLD, including an expression for their asymptotic delay distributions, are presented.

Original languageEnglish (US)
Pages (from-to)113-122+174
JournalOperations Research
Volume51
Issue number1
DOIs
StatePublished - Jan 1 2003

Keywords

  • Inventory/production, policies, review/lead-times: production policies to guarantee lead-times
  • Production/scheduling, sequencing, stochastic: lead-time constrained scheduling
  • Queues, optimization: optimal control to meet due-dates or lead-times

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Due-date scheduling: Asymptotic optimality of generalized longest queue and generalized largest delay rules'. Together they form a unique fingerprint.

Cite this