Proof of a conjecture of Schrage about the completion time variance problem (Q1183389): Difference between revisions

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.