Maximizing the minimum load for random processing times

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.