Proof of a conjecture of Schrage about the completion time variance problem

DOI10.1016/0167-6377(91)90024-JzbMath0751.90037OpenAlexW1974085404WikidataQ123127412 ScholiaQ123127412MaRDI QIDQ1183389

Nicholas G. Hall, Wiesław X. Kubiak

Publication date: 28 June 1992

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(91)90024-j

zbMATH Keywords

one machinecompletion time variance schedulingSchrage's conjecture

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (20)

A quadratic integer programming method for minimizing the mean squared deviation of completion times ⋮ Completion time variance minimisation on two identical parallel processors ⋮ Optimal sequencing of a set of positive numbers with the variance of the sequence's partial sums maximized ⋮ Pseudopolynomial algorithms for CTV minimization in single machine scheduling ⋮ Job scheduling methods for reducing waiting time variance ⋮ Mimimization of agreeably weighted variance in single machine systems ⋮ A lower bound for weighted completion time variance ⋮ Multi-machine scheduling with variance minimization ⋮ Time-flexible min completion time variance in a single machine by quadratic programming ⋮ A branch and bound algorithm to minimize completion time variance on a single processor. ⋮ An almost exact solution to the min completion time variance in a single machine ⋮ A SINGLE-MACHINE DETERIORATING JOB SCHEDULING PROBLEM WITH A NON-REGULAR CRITERION ⋮ An efficient local search for minimizing completion time variance in permutation flow shops ⋮ Completion time variance minimization in single machine and multi-machine systems ⋮ Scheduling about a given common due date to minimize mean squared deviation of completion times ⋮ A tight lower bound for the completion time variance problem ⋮ Bounds for the position of the smallest job in completion time variance minimization ⋮ Fast fully polynomial approximation schemes for minimizing completion time variance ⋮ Completion time variance minimization on a single machine is difficult ⋮ An exact algorithm to minimize mean squared deviation of job completion times about a common due date

Cites Work

• Minimizing Variation of Flow Time in Single Machine Systems
• Minimizing the Time-in-System Variance for a Finite Jobset
• Minimising Waiting Time Variance in the Single Machine Problem
• Deterministic and Random Single Machine Sequencing with Variance Minimization
• Variance Minimization in Single Machine Sequencing Problems

This page was built for publication: Proof of a conjecture of Schrage about the completion time variance problem