DYNAMIC SCHEDULING WITH CONVEX DELAY COSTS: THE GENERALIZED cμ RULE
成果类型：
Article
署名作者：
van Mieghem, Jan A.
署名单位：
Stanford University
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
DOI：
10.1214/aoap/1177004706
发表日期：
1995
页码：
809-833
关键词：
摘要：
We consider a general single-server multiclass queueing system that incurs a delay cost C-k(tau(k)) for each class k job that resides tau(k) 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 by c(k) = C'(k) and 1/mu(k), respectively, and let a(k)(t) be the age or time that the oldest class k job has been waiting at time t. We call the scheduling policy that at time t serves the oldest waiting job of that class k with the highest index mu(k)(t)c(k)(a(k)(t)), the generalized c mu rule. As a dynamic priority rule that depends on very little data, the generalized c mu rule is attractive to implement. We show that, with nondecreasing convex delay costs, the generalized c mu 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.
来源URL：