Minimizing the Time-in-System Variance for a Finite Jobset

Linus Schrage
Linus Schrage
University of Chicago
Search for more papers by this author

University of Chicago

Published Online:1 Jan 1975https://doi.org/10.1287/mnsc.21.5.540

Abstract

There are a finite number of jobs to be scheduled on a single machine. All jobs are available from the start and the objective is to sequence the jobs so that the time-in-system (or equivalently, the completion time) variance is minimized. A number of necessary conditions for an optimal sequencing (which for small jobsets turn out to be sufficient) are presented.

Cited by
- The minimization of the weighted completion time variance in a single machine: A specialized cutting-plane approach
  European Journal of Operational Research, Vol. 334, No. 3
- Minimizing range of job completion times with general position-dependent processing times and job-rejection
  13 May 2026 | Computational and Applied Mathematics, Vol. 45, No. 9
- Exact and resilient heuristic approaches to minimize completion time variance on a restricted parallel machine system
  21 November 2025 | OPSEARCH, Vol. 31
- Exact algorithms and resilient heuristic approaches to minimize the completion time variance of jobs on a single machine
  5 March 2025 | Flexible Services and Manufacturing Journal, Vol. 28
- Trade-offs between optimal and robust scheduling in one-stage production
  Manufacturing Letters, Vol. 41
- Resilient Scheduling Heuristic for Single Machine Systems to Minimize Variance of Job Completion Time
  27 August 2024
- Time-flexible min completion time variance in a single machine by quadratic programming
  European Journal of Operational Research, Vol. 312, No. 2
- A multi-machine scheduling solution for homogeneous processing: Asymptotic approximation and applications
  International Journal of Production Economics, Vol. 251
- A Multi-Machine Scheduling Solution for Homogeneous Processing: Asymptotic Approximation and Applications
  SSRN Electronic Journal, Vol. 44
- An almost exact solution to the min completion time variance in a single machine
  European Journal of Operational Research, Vol. 294, No. 2
- Balancing trade-offs in one-stage production with processing time uncertainty
  Procedia Manufacturing, Vol. 53
- A branch and price algorithm for single-machine completion time variance
  Computers & Operations Research, Vol. 109
- On generalized weighted completion time deviation model
- Completion time variance minimisation on two identical parallel processors
  Computers & Operations Research, Vol. 86
- Heuristics Techniques for Scheduling Problems with Reducing Waiting Time Variance
  30 August 2017
- Heuristics to minimize the completion time variance of jobs on a single machine and on identical parallel machines
  26 May 2016 | The International Journal of Advanced Manufacturing Technology, Vol. 88, No. 5-8
- A Heuristic for Scheduling of Uniform Parallel Processors
- A heuristic job scheduling algorithm for minimizing the waiting time variance
- Scheduling deteriorating jobs with a learning effect on unrelated parallel machines
  Applied Mathematical Modelling, Vol. 38, No. 21-22
- An exact algorithm to minimize mean squared deviation of job completion times about a common due date
  European Journal of Operational Research, Vol. 231, No. 3
- Dependability of computer and network systems
  7 October 2013
- Optimal sequencing of a set of positive numbers with the variance of the sequence’s partial sums maximized
  3 February 2012 | Optimization Letters, Vol. 7, No. 6
- Another well-solvable case of the QAP: Maximizing the job completion time variance
  Operations Research Letters, Vol. 40, No. 5
- A joint model of production scheduling and predictive maintenance for minimizing job tardiness
  4 October 2011 | The International Journal of Advanced Manufacturing Technology, Vol. 60, No. 9-12
- An efficient local search for minimizing completion time variance in permutation flow shops
  Computers & Operations Research, Vol. 39, No. 5
- Minimizing weighted waiting time variance on a single processor
  Computers & Industrial Engineering, Vol. 61, No. 4
- Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties
  Applied Mathematics and Computation, Vol. 217, No. 20
- A SINGLE-MACHINE DETERIORATING JOB SCHEDULING PROBLEM WITH A NON-REGULAR CRITERION
  20 November 2011 | Asia-Pacific Journal of Operational Research, Vol. 28, No. 03
- Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties
  Applied Mathematical Modelling, Vol. 35, No. 3
- A lower bound for weighted completion time variance
  European Journal of Operational Research, Vol. 207, No. 3
- Single-machine-based production scheduling model integrated preventive maintenance planning
  5 February 2010 | The International Journal of Advanced Manufacturing Technology, Vol. 50, No. 1-4
- Minimizing job completion time variance for service stability on identical parallel machines
  Computers & Industrial Engineering, Vol. 58, No. 4
- Completion time variance minimization in single machine and multi-machine systems
  Computers & Operations Research, Vol. 37, No. 1
- Minimizing total absolute deviation of job completion times: extensions to position-dependent processing times and parallel identical machines
  21 December 2017 | Journal of the Operational Research Society, Vol. 59, No. 10
- Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times
  Computers & Operations Research, Vol. 35, No. 6
- Job scheduling methods for reducing waiting time variance
  Computers & Operations Research, Vol. 34, No. 10
- Minimization of Job Waiting Time Variance on Identical Parallel Machines
  IEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews), Vol. 37, No. 5
- Job scheduling to minimize the weighted waiting time variance of jobs
  Computers & Industrial Engineering, Vol. 52, No. 1
- Single machine scheduling problems with controllable processing times and total absolute differences penalties
  European Journal of Operational Research, Vol. 177, No. 1
- Dependability of Computer and Network Systems
  13 December 2009
- Three new approaches for adjustment and improvement of the RR scheduler in a dynamic resource environment
  Computer Communications, Vol. 28, No. 8
- A branch and bound algorithm to minimize completion time variance on a single processor
  Computers & Operations Research, Vol. 30, No. 8
- Minimization of squared deviation of completion times about a common due date
  Computers & Operations Research, Vol. 29, No. 14
- A vector space model for variance reduction in single machine scheduling
  17 April 2007 | IIE Transactions, Vol. 34, No. 11
- Single machine MAD/Tmax problem with a common due date
  Computers & Operations Research, Vol. 29, No. 8
- Permutation Polyhedra and Minimisation of the Variance of Completion Times on a Single Machine
  Journal of Heuristics, Vol. 8, No. 4
- Fast fully polynomial approximation schemes for minimizing completion time variance
  European Journal of Operational Research, Vol. 137, No. 2
- Scheduling with random processing times to minimize completion time variance on a single machine subject to stochastic breakdowns
- Tabu search for a class of single-machine scheduling problems
  Computers & Operations Research, Vol. 28, No. 12
- Minimizing mean absolute deviation of job completion times from the mean completion time
  1 January 2000 | Naval Research Logistics, Vol. 47, No. 8
- Probabilistic analysis of an asymptotically optimal solution for the completion time variance problem
  Naval Research Logistics, Vol. 46, No. 4
- An Approximation Scheme for Minimizing Agreeably Weighted Variance on a Single Machine
  Gerhard J. Woeginger,
  1 May 1999 | INFORMS Journal on Computing, Vol. 11, No. 2
- Bounds for the position of the smallest job in completion time variance minimization
  European Journal of Operational Research, Vol. 114, No. 2
- An FPTAS for Agreeably Weighted Variance on a Single Machine (Extended Abstract)
  18 January 2002
- Multi-machine scheduling with variance minimization
  Discrete Applied Mathematics, Vol. 84, No. 1-3
- Sequencing jobs with random processing times to minimize weighted completion time variance
  Annals of Operations Research, Vol. 70, No. 0
- Minimizing the mean squared deviation from a common due date: unconstrained and constrained cases
  27 April 2007 | Production Planning & Control, Vol. 7, No. 5
- A tight lower bound for the completion time variance problem
  European Journal of Operational Research, Vol. 92, No. 1
- Scheduling to minimize the coefficient of variation
  International Journal of Production Economics, Vol. 44, No. 3
- Variance Minimization – Relationship between Completion-Time Variance and Waiting-Time Variance
  17 February 2009 | The Journal of the Australian Mathematical Society. Series B. Applied Mathematics, Vol. 38, No. 1
- A branch and bound procedure to minimize mean absolute lateness on a single processor
  Computers & Operations Research, Vol. 23, No. 2
- Scheduling about a given common due date to minimize mean squared deviation of completion times
  European Journal of Operational Research, Vol. 88, No. 2
- Minimization of agreeably weighted variance in single machine systems
  European Journal of Operational Research, Vol. 85, No. 3
- New results on the completion time variance minimization
  Discrete Applied Mathematics, Vol. 58, No. 2
- The stochastic single machine scheduling problem with earliness and tardiness costs
  European Journal of Operational Research, Vol. 77, No. 2
- A quadratic integer programming method for minimizing the mean squared deviation of completion times
  Operations Research Letters, Vol. 15, No. 4
- Simultaneous optimization of efficiency and performance balance measures in single-machine scheduling problems
  Naval Research Logistics, Vol. 40, No. 7
- Minimizing flow time variance in a single machine system using genetic algorithms
  European Journal of Operational Research, Vol. 70, No. 3
- A solvable case of the variance minimization problem
  Applied Mathematics Letters, Vol. 6, No. 6
- Completion time variance minimization on a single machine is difficult
  Operations Research Letters, Vol. 14, No. 1
- Single-machine scheduling with early and tardy completion costs
  Naval Research Logistics, Vol. 40, No. 1
- A hybrid simulated annealing approach for single machine scheduling problems with non-regular penalty functions
  Computers & Operations Research, Vol. 20, No. 2
- On the general solution for a class of early/tardy problems
  Computers & Operations Research, Vol. 20, No. 2
- Scheduling with monotonous earliness and tardiness penalties
  European Journal of Operational Research, Vol. 64, No. 2
- Single machine scheduling with coefficient of variation minimization
  European Journal of Operational Research, Vol. 62, No. 3
- AN EFFICIENT SCHEDULE APPROACH FOR CUSTOMER TREATMENT
  5 March 2018 | Engineering Optimization, Vol. 20, No. 1
- Heuristic Estimation of the Efficient Frontier for a Bi‐Criteria Scheduling Problem
  7 June 2007 | Decision Sciences, Vol. 23, No. 3
- Proof of a conjecture of Schrage about the completion time variance problem
  Operations Research Letters, Vol. 10, No. 8
- A proof for the longest-job-first policy in one-machine scheduling
  Naval Research Logistics, Vol. 38, No. 5
- Minimizing the Weighted Sum of Late and Early Completion Penalties in a Single Machine
  IIE Transactions, Vol. 22, No. 3
- Scheduling about a common due date with earliness and tardiness penalties
  Computers & Operations Research, Vol. 17, No. 2
- Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date
  Naval Research Logistics, Vol. 34, No. 5
- Single machine scheduling research
  Omega, Vol. 15, No. 3
- A single‐machine scheduling problem with random processing times
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 33, No. 3
- Minimizing mean absolute deviation of completion times about a common due date
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 33, No. 2
- Minimizing the sum of absolute lateness in single‐machine and multimachine scheduling
  10 October 2006 | Naval Research Logistics Quarterly, Vol. 31, No. 2
- Minimizing the average deviation of job completion times about a common due date
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 28, No. 4

Volume 21, Issue 5

January 1975

Pages 491-612

Article Information

Metrics

Information

Published Online:January 01, 1975

Cite as

Linus Schrage, (1975) Minimizing the Time-in-System Variance for a Finite Jobset. Management Science 21(5):540-543.

https://doi.org/10.1287/mnsc.21.5.540

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Minimizing the Time-in-System Variance for a Finite Jobset

Abstract

Volume 21, Issue 5

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News