V-shape property for job sequences that minimize the expected completion time variance

摘要

We consider the problem of sequencing n jobs with random processing time on a single machine so as to minimize the expected variance of job completion times. Our main result is a new sufficient condition for an optimal sequence to be V-shaped in terms of the mean processing times when n 3. We show that this condition is satisfied by a wide variety of problem instances, including those in which the processing times follow different patterns of distributions. This result relaxes a condition proposed before.