Proof of a conjecture of Schrage about the completion time variance problem (Q1183389)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Proof of a conjecture of Schrage about the completion time variance problem
scientific article

    Statements

    Proof of a conjecture of Schrage about the completion time variance problem (English)
    0 references
    0 references
    0 references
    28 June 1992
    0 references
    The paper concerns the completion time variance scheduling problem in one machine, when jobs from a given set are to be scheduled for completion time variance of the jobs to be minimal. It was proved in the preliminary papers that the longest job must be scheduled first [\textit{L. Schrage}, Manage. Sci., Theory 21, 540-543 (1975; Zbl 0302.90021)], and that an optimal schedule must be \(V\)-shaped [\textit{S. Eilon} and \textit{I. G. Chowdhury}, Manage. Sci. 23, 567-575 (1977; Zbl 0362.90051)], what means the jobs must be ordered by nonincreasing processing time if placed before the shortest job, and by nondecreasing order if placed after the shortest job. The weaker form of Schrage's conjecture was formulated that for every instance there is an optimal schedule where the longest job is first, the second longest job is last and the third longest job is second. This Schrage's conjecture was proved for less than or equal to 18 jobs in the preliminary paper by \textit{V. Vani} and \textit{M. Raghavachari} [Oper. Res. 35, 111-120 (1987; Zbl 0616.90027)]. The current paper provides a proof of Schrage's conjecture for any problem size using the preliminary results and carrying out careful analysis of five cases.
    0 references
    completion time variance scheduling
    0 references
    one machine
    0 references
    Schrage's conjecture
    0 references

    Identifiers