Deterministic and Random Single Machine Sequencing with Variance Minimization

Abstract

We discuss the problem of scheduling several jobs on a single machine so as to minimize the variance of the jobs' completion times. By exploiting the well-known pooled variance formula, we obtain a general formula for the change in variance due to the interchange of two specified jobs whose positions have not been fixed in the sequence. This result permits us to obtain explicit optimal sequences for problems with 6 or 7 jobs, and to show that Schrage's conjecture on positioning the job with the third largest processing time is true for problems with up to 18 jobs. We then develop a heuristic procedure based on a variance interchange formula and compare it with other known heuristic methods. We also consider a problem never before examined, namely, the case when processing times are not known deterministically but are random variables. We obtain some general results, under certain assumptions on the parameters of the distributions of processing times, and extend to the random situation many results applicable to the deterministic case. Finally, we give some results for the exponential distribution of processing times.