We consider a single machine scheduling problem to minimize the completion time variance. This roblem is known to be NP-hard. We prove that if $p_{n-1} = p_{n-2$, then there is an optimal solution of the form $(n,n-2,n-3,…,n-4,n-1)$. A new lower bound are proposed for solving the problem. The test on more than 4000 instances shows that this lower bound is very tight and the heuristic (developed by Nessah and Chu [2010]) yields solutions very close to optimal ones since the gap between the solution given by the heuristic and the lower bound is very small.
Citation
Submitted to Annals of Operations Research.