Pseudopolynomial algorithms for CTV minimization in single machine scheduling

DOI10.1016/S0305-0548(97)00032-4zbMath0893.90092OpenAlexW2076034394MaRDI QIDQ1373152

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

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

Related Items

Job scheduling methods for reducing waiting time variance ⋮ A lower bound for weighted completion time variance ⋮ 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 ⋮ Bounds for the position of the smallest job in completion time variance minimization ⋮ Empirically discovering dominance relations for scheduling problems using an evolutionary algorithm ⋮ Two-stage no-wait proportionate flow shop scheduling with minimal service time variation and optional job rejection ⋮ Using a hybrid evolutionary algorithm to minimize variance in response time for multimedia object requests

Cites Work

• Unnamed Item
• Unnamed Item
• Scheduling about a common due date with earliness and tardiness penalties
• Proof of a conjecture of Schrage about the completion time variance problem
• 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
• Completion time variance minimization on a single machine is difficult
• New results on the completion time variance minimization
• Minimizing Mean Squared Deviation of Completion Times About a Common Due Date
• Minimizing Variation of Flow Time in Single Machine Systems
• On the Minimization of Completion Time Variance with a Bicriteria Extension
• Minimising Waiting Time Variance in the Single Machine Problem
• Minimization of expected variance of completion times on single machine for stochastic jobs
• Deterministic and Random Single Machine Sequencing with Variance Minimization
• Minimizing the Flow-time Variance in Single-machine Systems
• Variance Minimization in Single Machine Sequencing Problems