STOCHASTIC MACHINE MINIMIZATION WITH CONSTANT SERVICE TIMES

We consider the nonpreemptive scheduling of n greater-than-or-equal-to 1 jobs on identical, parallel machines. With job running times all gi ven by some constant, the objective is to minimize the expected number of machines needed throughout a schedule subject to the following wai ting-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 distrib ution is made available to the scheduler. In general, if job running t imes are random, there might be situations in which, after running job s on a given number of machines, it would be desirable to activate new machines, because the remaining times of unfinished jobs are stochast ically too large compared to the time remaining on the timer. A princi pal result of this paper is that randomness of job running times is es sential to such situations; if running times are deterministic, then i rrespective of the distribution of W, an optimal policy initially assi gns jobs to some number of machines k(n) (which depends on the distrib ution of W), and maintains that number while there are jobs available, until the timer has expired, at which point any remaining, as yet uns cheduled jobs are assigned to new, unused machines. This paper also an alyzes the dependence of k(n) and the minimal expected cost on the par ameters of the timer distribution when W is either exponentially distr ibuted or uniformly distributed on a finite interval. The determinatio n of k(n) turns out to have an intriguing number-theoretic flavor.