Pseudopolynomial algorithms for CTV minimization in single machine scheduling

DOI10.1016/S0305-0548(97)00032-4MaRDI QIDQ1373152zbMATH OpenOpenAlexFDO

Authors D. K. Manna, V. Rajendra Prasad

Publication date 6 November 1997

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0305-0548(97)00032-4

zbMATH Keywords

single machinecompletion time variancepseudopolynomial algorithmdominance criteria

Mathematics Subject Classification ID

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

Recommendations

• A branch and bound algorithm to minimize completion time variance on a single processor.
• scientific article; zbMATH DE number 764420
• A solvable case of the variance minimization problem
• On the Minimization of Completion Time Variance with a Bicriteria Extension

Cites work

• scientific article; zbMATH DE number 444985 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• A hybrid simulated annealing approach for single machine scheduling problems with non-regular penalty functions
• Completion time variance minimization on a single machine is difficult
• Deterministic and Random Single Machine Sequencing with Variance Minimization
• Minimising Waiting Time Variance in the Single Machine Problem
• Minimization of expected variance of completion times on single machine for stochastic jobs
• Minimizing Mean Squared Deviation of Completion Times About a Common Due Date
• Minimizing Variation of Flow Time in Single Machine Systems
• Minimizing flow time variance in a single machine system using genetic algorithms
• Minimizing the Flow-time Variance in Single-machine Systems
• New results on the completion time variance minimization
• On the Minimization of Completion Time Variance with a Bicriteria Extension
• Proof of a conjecture of Schrage about the completion time variance problem
• Scheduling about a common due date with earliness and tardiness penalties
• Variance Minimization in Single Machine Sequencing Problems

Cited in

(13)

• Minimizing class-based completion time variance on a single machine
• Permutation polyhedra and minimisation of the variance of completion times on a single machine
• Using a hybrid evolutionary algorithm to minimize variance in response time for multimedia object requests
• scientific article; zbMATH DE number 764420 (Why is no real title available?)
• An almost exact solution to the min completion time variance in a single machine
• Minimizing completion time variance with compressible processing times
• A lower bound for weighted completion time variance
• Bounds for the position of the smallest job in completion time variance minimization
• Empirically discovering dominance relations for scheduling problems using an evolutionary algorithm
• Time-flexible min completion time variance in a single machine by quadratic programming
• Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope
• 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

This page was built for publication: Pseudopolynomial algorithms for CTV minimization in single machine scheduling

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