Fast fully polynomial approximation schemes for minimizing completion time variance

DOI10.1016/S0377-2217(01)00211-9zbMath0998.90038MaRDI QIDQ1600838

Jinliang Cheng, Mikhail Y. Kovalyov, Wiesław X. Kubiak

Publication date: 16 June 2002

Published in: European Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

schedulingfully polynomial approximation schemecompletion time variance

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, Job scheduling methods for reducing waiting time variance, A lower bound for weighted completion time variance, The symmetric quadratic knapsack problem: approximation and scheduling applications, Time-flexible min completion time variance in a single machine by quadratic programming, 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, Minimization of ordered, symmetric half-products, Minimizing weighted mean absolute deviation of job completion times from their weighted mean, A half-product based approximation scheme for agreeably weighted completion time variance, FPTAS for half-products minimization with scheduling applications

Cites Work

• Mimimization of agreeably weighted variance in single machine systems
• Proof of a conjecture of Schrage about the completion time variance problem
• Completion time variance minimization on a single machine is difficult
• New results on the completion time variance minimization
• 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
• Algorithms for Scheduling Independent Tasks
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Minimising Waiting Time Variance in the Single Machine Problem
• An Approximation Scheme for Minimizing Agreeably Weighted Variance on a Single Machine
• A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem
• Variance Minimization in Single Machine Sequencing Problems