Optimal Stochastic Allocation of Machines Under Waiting Time Constraints.

We consider the nonpreemptive scheduling of n>=1 stochastic jobs so as to minimize the expected number of parallel machines needed to meet given waiting-time constraints. The number of machines available is unlimited. The running times of the jobs are denoted T sub 1, ..., T sub n and are taken to be independent samples of an exponentially distributed random variable T with mean 1. Job waiting times are to be bounded stochastically by a nonnegative random variable W, independent of T sub 1, ..., T sub n. At time 0 a timer is started with an initial value W, and job scheduling begins. When the timer expires, all jobs still waiting for a machine are assigned to available machines. Only the distributions of W and the job durations T sub 1, ..., T sub n are known to the scheduler in advance.