Due-Date Scheduling: Asymptotic Optimality of Generalized Longest Queue and Generalized Largest Delay Rules
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
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 ¦O_{k} must not exceed a given delay or lead-time D_{k}. In a stochastic system the constraint ¦O_{k}iUD_{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¦I (Gc¦I) scheduling rule is known to be asymptotically optimal. The Gc¦I 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, ¦E_{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 ¦E: GLQ(¦E) serves FIFO within class and prioritizes the class with highest index ¦E_{k}N_{k}, whereas GLD(¦E) uses index ¦E_{k}¦E_{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(¦E_{∗}) and GLD(¦E_{∗}), where ¦E_{∗,k}=1/¦E_{k}D_{k}, asymptotically minimize the probability of maximal due-date violation in heavy traffic. Specifically, they minimize liminf_{niuiÞ}Pr{max_{k}sup_{siE[0,t]}((¦O_{k}(ns))/(n^{1/2}D_{k}))iÝx} for all positive t and x, where ¦O_{k}(s) is the delay of the most recent class k job that arrived before time s. GLQ with appropriate parameter ¦E_{¦A} also reduces total variability because it asymptotically minimizes a weighted sum of ¦A^{th} delay moments. Properties of GLQ and GLD, including an expression for their asymptotic delay distributions, are presented.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.001 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.001 | 0.000 |
| Bibliometrics | 0.000 | 0.001 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.001 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.001 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it