Stochastic Machine Minimization with Constant Service Times.

We consider the non-preemptive scheduling of n >= 1 jobs on identical parallel machines. With job running times all given by some constant, the objective is to minimize the expected number of machines needed throughout a schedule subject to the following waiting-time constraints. At time 0, a timer with (random) initial value W is started; after time W all jobs must either be finished or running on a machine. The value of W is not known in advance, but its distribution is made available to the scheduler. In general, if job running times are random, there might be situations in which, after running jobs on a given number of machines, it would be desirable to activate new machines because the remaining times of unfinished jobs are stochastically too large compared to the time remaining on the timer.