Maximizing the minimum load for random processing times

Stefanie Gerke, Konstantinos Panagiotou, Justus Schwartz, Angelika Steger

Research output: Contribution to journalArticlepeer-review


In this article, we consider a stochastic variant of the so-called Santa Claus problem. The Santa Claus problem is equivalent to the problem of scheduling a set of n jobs on m parallel machines without preemption, so as to maximize the minimum load. We consider the identical machine version of this scheduling problem with the additional restriction that the scheduler has only a guess of the processing times; that is, the processing time of a job is a random variable. We show that there is a critical value ρ (n,m) such that if the duration of the jobs is exponentially distributed and the expected values deviate by less than a multiplicative factor of ρ (n,m) from each other, then a greedy algorithm has an expected competitive ratio arbitrarily close to one; that is, it performs in expectation almost as good as an algorithm that knows the actual values in advance. On the other hand, if the expected values deviate by more than a multiplicative factor of ρ (n,m), then the expected performance is arbitrarily bad for all algorithms.
Original languageEnglish
Article number17
Pages (from-to)1-19
Number of pages19
JournalACM Transactions on Algorithms (TALG)
Issue number3
Publication statusPublished - Jan 2015

Cite this