Stochastic Scheduling in a Multiclass G/G/1 Queue

摘要

The problem of scheduling customers in a multiclass G/G/1 queue so as to minimizea weighted sum of the workloads of the different classes is addressed. The nonidling, preemptive, fixed priority policy that schedules customers belonging to the class having the maximum weight is established as minimizing the cost function pathwise at any point in time. This result is based on the application of elementary forward induction arguments and is shown to hold for a very general class of policies. A proof for the optimality of the mu-c rule in the multiclass G/M/1 queue is then obtained as an easy corollary of the first result.