A solvable case of the variance minimization problem (Q1324501)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A solvable case of the variance minimization problem |
scientific article |
Statements
A solvable case of the variance minimization problem (English)
0 references
24 May 1994
0 references
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.
0 references
equal processing times
0 references
arbitrary weights
0 references
completion time variance
0 references
0 references