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
    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

    Identifiers