Abstract:

The multiclass many server queue with abandonment (specifically, the GI/GI/N+GI queue) is a canonical model for service systems. One key operational question is how to schedule; that is, how to choose the customer that a newly available server will serve. The scheduling question is of fundamental importance because scheduling determines which customer classes will experience short waits, and which ones will experience long waits. However, even though there is much work on scheduling in queueing systems, there is comparatively less work on scheduling in queueing systems when parameters are unknown and may be learned.

Our objective in this work is to determine a scheduling policy that minimizes long-run average abandonment costs, when system parameters are unknown. The difficulty is that the state space is very complex, because in order for the system to be Markovian we must track: (i) the time elapsed since the last arrival for each class; (ii) the amount of time each customer in service has been in service; and (iii) the amount of time each customer in queue has spent waiting. We propose and analyze a Learn-Then-Schedule algorithm. The algorithm is composed of a learning phase, during which point estimates of the mean service times are formed, and an exploitation phase, during which a simple static ranking rule (based on those point estimates) is applied. We compare the performance of our Learn-Then-Schedule algorithm to the performance of a policy derived when system parameters are known, that is optimal asymptotically for large systems (as the arrival rates and number of servers tend to infinity). We show that the Learn-Then-Schedule algorithm has regret of order log T (where T is the system run-time), which is the smallest order achievable.

个人简介：

Yueyang Zhong is an Assistant Professor of Management Science and Operations at London Business School. Yueyang received her PhD in Management Science and Operations Management at the University of Chicago Booth School of Business. Previously, she received her bachelor’s degree in Industrial Engineering and Economics from Tsinghua University. Yueyang’s primary research interests are in behavior-aware and socially-aware stochastic modeling and optimization of modern service systems, with consideration of human strategic behavior and imperfect systemic information.