Adaptive Lexicographic Optimization in Multi-Class M/GI/1 Queues

We consider a multi-class M/GI/1 system, 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 required to find a policy that lexicographically minimizes the vector of performance ratios arranged in nonincreasing order. We provide such a policy that is adaptive, uses only knowledge of arrival and departure instants, and is thus easy to implement. We also consider 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.