Optimality and finite time behavior of an adaptive multi-objective scheduling algorithm

A multi-class M/GI/1 system is considered in which an average response time objective is associated with each class. The performance of each class is measured by the ratio of the average response time over the corresponding value of the objective. To achieve fairness in service allocation it is necessary to find a policy that lexicographically minimizes the vector of performance ratios arranged in non-increasing order. An adaptive policy is provided that only uses knowledge of arrival and departure instants and is easy to implement. Also considered is a variant of this policy which adapts faster to changes in the statistical parameters of the model. Both policies are analyzed via associated stochastic recursions using techniques of stochastic approximation.