## An Almost Exact Solution to the Min Completion Time Variance in a Single Machine

We consider a single machine scheduling problem to minimize the completion time variance of n jobs. This problem is known to be NP-hard and our contribution is to establish a novel bounding condition for a characterization of an optimal sequence. Specifically, we prove a necessary and sufficient condition (which can be verified in O(n\log n)) … Read more

## Sufficient condition on Schrage conjecture about the completion time variance

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 … Read more