New results on the completion time variance minimization

DOI10.1016/0166-218X(93)E0125-IzbMath0833.90070MaRDI QIDQ1805454

Wiesław X. Kubiak

Publication date: 20 March 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

single machine schedulingMonge propertysubmodular functionsworst case time complexityvariance of job completion times

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items

Scheduling chains to minimize mean flow time, Introduction to QUBO, Complexity and Polynomially Solvable Special Cases of QUBO, Fast Heuristics and Approximation Algorithms, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, A branch-and-bound algorithm for single machine scheduling with quadratic earliness and tardiness penalties, Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions, Pseudopolynomial algorithms for CTV minimization in single machine scheduling, `Strong'-`weak' precedence in scheduling: extensions to series-parallel orders, Job scheduling methods for reducing waiting time variance, A lower bound for weighted completion time variance, Multi-machine scheduling with variance minimization, The symmetric quadratic knapsack problem: approximation and scheduling applications, Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance, An almost exact solution to the min completion time variance in a single machine, A branch and price algorithm for single-machine completion time variance, Pseudo-Boolean optimization, Minimization of ordered, symmetric half-products, Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications, A half-product based approximation scheme for agreeably weighted completion time variance, Positive half-products and scheduling with controllable processing times, Algorithms for minclique scheduling problems, FPTAS for half-products minimization with scheduling applications, A tight lower bound for the completion time variance problem, A combinatorial approach to level of repair analysis, Bounds for the position of the smallest job in completion time variance minimization, Two-stage no-wait proportionate flow shop scheduling with minimal service time variation and optional job rejection, Fast fully polynomial approximation schemes for minimizing completion time variance, A survey of the state-of-the-art of common due date assignment and scheduling research, Completion time variance minimization on a single machine is difficult, Maximizing total tardiness on a single machine in \(O(n^2)\) time via a reduction to half-product minimization, Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product

Cites Work

• Unnamed Item
• Scheduling about a common due date with earliness and tardiness penalties
• Mimimization of agreeably weighted variance in single machine systems
• Completion time variance minimization on a single machine is difficult
• Sequencing with Earliness and Tardiness Penalties: A Review
• Minimizing Mean Squared Deviation of Completion Times About a Common Due Date
• Simultaneous Minimization of Mean and Variation of Flow Time and Waiting Time in Single Machine Systems
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Minimizing Variation of Flow Time in Single Machine Systems
• On the Minimization of Completion Time Variance with a Bicriteria Extension
• 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
• Note—A Note on the Minimization of Mean Squared Deviation of Completion Times About a Common Due Date
• Variance Minimization in Single Machine Sequencing Problems