Logo Logo

Dynamic Scheduling with Convex Delay Costs: The Generalized c-mu Rule, Annals of Applied Probability

Abstract

We consider a general single-server multiclass queueing system that incurs a delay cost Csubk/sub(tsubk/sub) for each class k job that resides tsubk/sub units of time in the system. This paper derives a scheduling policy that minimizes the total cumulative delay cost when the system operates during a finite time horizon. Denote the marginal delay cost function and the (possibly nonstationary) average processing time of class k. We call the scheduling policy that at time t serves the oldest waiting job of that class k with the highest index, the generalized "c" rule. As a dynamic priority rule that depends on very little data, the generalized "c" rule is attractive to implement. We show that, with nondecreasing convex delay costs, the generalized "c" rule is asymptotically optimal if the system operates in heavy traffic and give explicit expressions for the associated performance characteristics: the delay (throughput time) process and the minimum cumulative delay cost. The optimality result is robust in that it holds for a countable number of classes and several homogeneous servers in a nonstationary, deterministic or stochastic environment where arrival and service processes can be general and interdependent.

Type

Article

Author(s)

Jan A. Van Mieghem

Date Published

1995

Citations

Van Mieghem, A. Jan. 1995. Dynamic Scheduling with Convex Delay Costs: The Generalized c-mu Rule. Annals of Applied Probability. 5(3): 809-833.

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