Brief Announcement: Stochastic Parallel Scheduling with Bandit Feedback

We study the fundamental problem of scheduling jobs with stochastic sizes to minimize the total completion time for both single and parallel machines. Traditionally, the size distributions are assumed to be known to the scheduler; the challenge is accounting for the stochasticity. Departing from prior work, we explore the problem of efficiently learning to schedule when the size distributions are unknown and we are unable to directly obtain samples from it. We adopt an online bandit learning framework in which an algorithm interacts with a scheduling environment over a series of T periods. In each period, the algorithm commits to a schedule for n stochastic jobs on up to m parallel machines and then observes only the random cost of the schedule, and not individual job sizes. This so-called bandit-feedback provides limited information about the underlying (unknown) job size distributions. The objective is to minimize the total regret --- the difference in expected total completion time of schedules chosen by the algorithm from that of the optimal schedule under complete information.