SINGLE-MACHINE SCHEDULING WHEN PROCESSING TIMES ARE CORRELATED NORMALRANDOM-VARIABLES

A single machine is available to process a collection of jobs whose pr ocessing times are jointly multivariate normal. Processing is nonpreem ptive. We show that in the equicorrelation case, the permutation polic y which schedules the jobs in ascending order of their (marginal) mean processing times is optimal for general order-specific costs and also for job-specific costs under an agreeability condition. Suboptimality bounds on the performance of Smith's rule are obtained for the weight ed flow-time criterion. A computational study shows that a dynamic ver sion of Smith's rule comes very close to optimality. (C) 1997 Elsevier Science B.V.