Single machine scheduling with coefficient of variation minimization (Q1205688)

The problem of scheduling \(n\) non-preemptive and simultaneously available jobs on a single machine is considered. The aim is to minimize \(\sum^ n_{i=1} C^ 2_ i\left/\left(\sum^ n_{i=1} C_ i\right)^ 2\right.\), where \(C_ i\) is the completion time of job \(i\). Two properties of optimal schedules are established: (1) The job with the largest processing time is always scheduled first in an optimal schedule. (2) Any optimal schedule is \(V\)-shaped (a schedule is \(V\)-shaped if all jobs preceding the job with shortest processing time are sequenced in non-increasing order of their processing times and jobs following the shortest time job are sequenced in non-decreasing order of their processing times). For \(n=3,4,5\) simple procedures for finding optimal schedules are obtained. A heuristic method is proposed for the general case.