Dynamic scheduling with convex delay costs: The generalized \(c\mu\) rule.

*(English)*Zbl 0843.90047Summary: 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 characteristic: 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.

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 characteristic: 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.

##### MSC:

90B22 | Queues and service in operations research |

60K25 | Queueing theory (aspects of probability theory) |

90B35 | Deterministic scheduling theory in operations research |

60J70 | Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.) |

93E20 | Optimal stochastic control |

90B30 | Production models |