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)) 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. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

A new approach is proposed for deriving a lower bound for minimizing completion time variance in single machine scheduling problem, outperforming existing bounds and having an average difference of less than 0.01% from the optimal solution.