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