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)) for the characterization of five scheduling positions in the optimal sequence. Applying this characterization, we propose a new approach to derive the highest lower bound for the minimal completion time variance, outperforming the existing bounds for this problem. The numerical tests indicate that the novel lower bound is, on average, less than 0.01% far away from the optimal solution, outperforming all the existing lower bounds on the minimum completion time variance.
Article
View An Almost Exact Solution to the Min Completion Time Variance in a Single Machine