Take Action

Home | Faculty & Research Overview | Research

Research Details

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

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. Equivalently, its delay must not exceed a given delay or lead-time D_{k}. In a stochastic system the constraint 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 (Gc rule) 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.

Type

Article

Author(s)

Jan A. Van Mieghem

Date Published

2003

Citations

Van Mieghem, A. Jan. 2003. Due Date Scheduling: Asymptotic Optimality of Generalized Longest-Queue and Generalized Largest Delay Rules. Operations Research. 51(1): 113-122.

KELLOGG INSIGHT

Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more

COURSE CATALOG

Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.
LEARN MORE

DEGREE PROGRAMS

Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more

Take Action