Pseudopolynomial algorithms for CTV minimization in single machine scheduling

DOI10.1016/S0305-0548(97)00032-4zbMATH Open0893.90092OpenAlexW2076034394MaRDI QIDQ1373152FDOQ1373152

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)