Completion time variance minimization on a single machine is difficult

DOI10.1016/0167-6377(93)90019-DzbMATH Open0794.90024OpenAlexW1993900332MaRDI QIDQ1317023FDOQ1317023

Authors: Wieslaw Kubiak 

Publication date: 17 April 1994

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

Full work available at URL: https://doi.org/10.1016/0167-6377(93)90019-d

Recommendations

• A solvable case of the variance minimization problem
• Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard.
• A branch and bound algorithm to minimize completion time variance on a single processor.
• New results on the completion time variance minimization
• Complexity of a scheduling problem with controllable processing times

zbMATH Keywords

NP-completenesssingle machinecompletion time variance minimization

Mathematics Subject Classification ID

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

Cites Work

• New results on the completion time variance minimization
• Sequencing with Earliness and Tardiness Penalties: A Review
• Variance Minimization in Single Machine Sequencing Problems
• Proof of a conjecture of Schrage about the completion time variance problem
• Minimizing the Time-in-System Variance for a Finite Jobset
• Minimising Waiting Time Variance in the Single Machine Problem
• Simultaneous Minimization of Mean and Variation of Flow Time and Waiting Time in Single Machine Systems
• Minimizing Variation of Flow Time in Single Machine Systems
• Deterministic and Random Single Machine Sequencing with Variance Minimization
• Mimimization of agreeably weighted variance in single machine systems
• On the Minimization of Completion Time Variance with a Bicriteria Extension

Cited In (52)

• Time-flexible min completion time variance in a single machine by quadratic programming
• The single machine weighted mean squared deviation problem
• A single-machine deteriorating job scheduling problem with a non-regular criterion
• Complexity of a class of nonlinear combinatorial problems related to their linear counterparts
• Minimizing weighted mean absolute deviation of job completion times from their weighted mean
• Algorithms for minclique scheduling problems
• A half-product based approximation scheme for agreeably weighted completion time variance
• A tight lower bound for the completion time variance problem
• A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems
• BEAM SEARCH HEURISTICS FOR THE SINGLE MACHINE SCHEDULING PROBLEM WITH LINEAR EARLINESS AND QUADRATIC TARDINESS COSTS
• Mimimization of agreeably weighted variance in single machine systems
• Hierarchical minimization of completion time variance and makespan in jobshops
• Scheduling deteriorating jobs with a learning effect on unrelated parallel machines
• A survey of the state-of-the-art of common due date assignment and scheduling research
• A branch and price algorithm for single-machine completion time variance
• Minimization of ordered, symmetric half-products
• New results on the completion time variance minimization
• Fast fully polynomial approximation schemes for minimizing completion time variance
• Using a hybrid evolutionary algorithm to minimize variance in response time for multimedia object requests
• Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs
• Completion time variance minimization in single machine and multi-machine systems
• Another well-solvable case of the QAP: maximizing the job completion time variance
• The symmetric quadratic knapsack problem: approximation and scheduling applications
• An almost exact solution to the min completion time variance in a single machine
• On the complexity of the single machine scheduling problem minimizing total weighted delay penalty
• Minimizing completion time variance with compressible processing times
• Completion time variance minimisation on two identical parallel processors
• A note on lower bound for completion time variance in single machine scheduling.
• A lower bound for weighted completion time variance
• Solving a stochastic single machine problem with initial idle time and quadratic objective
• A survey of scheduling with controllable processing times
• Multi-machine scheduling with variance minimization
• An exact algorithm to minimize mean squared deviation of job completion times about a common due date
• Sequencing heuristic for bicriteria scheduling in a single machine problem
• Due date assignments and scheduling a single machine with a general earliness/tardiness cost function
• Variability of completion time differences in permutation flow shop scheduling
• Total absolute deviation of job completion times on uniform and unrelated machines
• Bounds for the position of the smallest job in completion time variance minimization
• \(V\)- and \(\Lambda\)-shaped properties for optimal single machine schedules for a class of non-separable penalty functions
• Flow shop scheduling algorithms for minimizing the completion time variance and the sum of squares of completion time deviations from a common due date
• Scheduling about a common due date with job-dependent asymmetric earlines and tardiness penalties
• Minimising variance of job completion times in a single machine
• Pseudopolynomial algorithms for CTV minimization in single machine scheduling
• Optimal sequencing of a set of positive numbers with the variance of the sequence's partial sums maximized
• Minimizing variation of production rates in just-in-time systems: A survey
• Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
• Machine scheduling with earliness, tardiness and non-execution penalties
• Job scheduling methods for reducing waiting time variance
• Two-stage no-wait proportionate flow shop scheduling with minimal service time variation and optional job rejection
• Scheduling with common due date assignment to minimize generalized weighted earliness-tardiness penalties
• An efficient local search for minimizing completion time variance in permutation flow shops
• Processing-plus-wait due dates in single-machine scheduling

This page was built for publication: Completion time variance minimization on a single machine is difficult

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1317023)