Learning the Scheduling Policy in Time-Varying Multiclass Many Server Queues with Abandonment

We consider a learning variant of a canonical scheduling problem in a multiclass many server queue with abandonment (specifically, the M_t/M/N+M and the GI/GI/N+GI queues). The objective is to minimize the long-run average class-dependent expected linear holding and abandonment costs when the class-dependent model parameters (arrival rates, service rates and abandonment rates) are a priori unknown. The difficulty is that even when parameters are known, characterizing an optimal scheduling policy appears intractable. Fortunately, the simple cμ/θ rule, that prioritizes classes in accordance with a static ranking that depends on the costs, the service rates, and the abandonment rates, is asymptotically optimal as the arrival rates and number of servers become large, under certain conditions. Then, our task is to learn the service and abandonment rates well enough to determine an optimal static priority ranking for the classes, and we can benchmark our performance by defining the regret relative to the cμ/θ rule.We propose a Learn-Then-Schedule algorithm, which is composed of a learning phase during which point estimates of the mean service and patience times are formed, and an exploitation phase during which the cμ/θ rule with empirical mean estimates as a surrogate for actual parameters is followed. It is shown that the smallest achievable regret for static priority scheduling policies in T periods is Ω(logT), and we prove that our proposed algorithm achieves a regret upper bound of O(logT), which matches the lower bound