A solvable case of the variance minimization problem (Q1324501)

The completion time variance (CTV) problem was first proposed by \textit{A. G. Merten} and \textit{M. E. Muller} [Management Sci., Theory 18, 518-528 (1972; Zbl 0254.90040)]. It is a scheduling problem. The general CTV problem involves arbitrary processing times and weights. The equal weight case has already been studied extensively and shown to be NP-complete (references are given). The case where processing times are equal but weights are arbitrary is investigated in this paper. It is shown that this case is well solvable and an algorithm is derived which can yield an optimal solution in \(O(n\log n)\) time. The algorithm may be extended as a heuristic to the general CTV problem.