Sequencing Stochastic Jobs with a Single Sample

This paper revisits the well known single machine scheduling problem to minimize total weighted completion times. The twist is that job sizes are stochastic from unknown distributions, and the scheduler has access to only a single sample from each of the distributions. For this restricted information regime, we analyze the simplest and probably only reasonable scheduling algorithm, namely to schedule by ordering the jobs by weight over sampled processing times. In general, this algorithm can be tricked by adversarial input distributions, performing in expectation arbitrarily worse even in comparison to choosing a random schedule. The paper suggests notions to capture the idea that this algorithm, on reasonable inputs, should exhibit a provably good expected performance. Specifically, we identify three natural classes of input distributions, such that for these classes, the algorithm performs better than random on any input.
Comment: 12 pages, 1 figure