INEQUALITIES AND BOUNDS FOR THE SCHEDULING OF STOCHASTIC JOBS ON PARALLEL MACHINES

Consider n jobs and m machines. The m machines are identical and set up in parallel. All n jobs are available at t equals 0 and each job has to be processed on one of the machines; any one can do. The processing time of job j is X//j, a random variable with distribution F//j. The sequence in which the jobs start with their processing is predetermined and preemptions are not allowed. We investigate the effect of the variability of the processing times on the expected makespan and the expected time to first idleness. Bounds are presented for these quantities in case the distributions of the processing times of the jobs are new better (worse) than used.