Scheduling Servers with Stochastic Bilinear Rewards
  In this paper, we study scheduling in multi-class, multi-server queueing
systems with stochastic rewards of job-server assignments following a bilinear
model in feature vectors characterizing jobs and servers. A bilinear model
allows capturing pairwise interactions of features of jobs and servers. Our
goal is regret minimization for the objective of maximizing cumulative reward
of job-server assignments over a time horizon against an oracle policy that has
complete information about system parameters, while maintaining queueing system
stable and allowing for different job priorities. The scheduling problem we
study is motivated by various applications including matching in online
platforms, such as crowdsourcing and labour platforms, and cluster computing
systems. We study a scheduling algorithm based on weighted proportionally fair
allocation criteria augmented with marginal costs for reward maximization,
along with a linear bandit algorithm for estimating rewards of job-server
assignments. For a baseline setting, in which jobs have identical mean service
times, we show that our algorithm has a sub-linear regret, as well as a
sub-linear bound on the mean queue length, in the time horizon. We show that
similar bounds hold under more general assumptions, allowing for mean service
times to be different across job classes and a time-varying set of server
classes. We also show stability conditions for distributed iterative algorithms
for computing allocations, which is of interest in large-scale system
applications. We demonstrate the efficiency of our algorithms by numerical
experiments using both synthetic randomly generated data and a real-world
cluster computing data trace.
