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

Jan A. Van Mieghem ()
Additional contact information
Jan A. Van Mieghem: Kellogg School of Management, Northwestern University, Evanston, Illinois 60208-2009

Operations Research, 2003, vol. 51, issue 1, 113-122

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 (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.

Keywords: Queues; optimization: optimal control to meet due-dates or lead-times; Production/scheduling; sequencing; stochastic: lead-time constrained scheduling; Inventory/production; policies; review/lead-times: production policies to guarantee lead-times (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.51.1.113.12793 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:51:y:2003:i:1:p:113-122

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().