A monotone approximation algorithm for scheduling with precedence constraints.
Sven Oliver KrumkeAnne SchwahnRob van SteeStephan WestphalPublished in: Oper. Res. Lett. (2008)
Keyphrases
- precedence constraints
- vertex cover
- search space
- linear programming
- parallel processors
- objective function
- worst case
- dynamic programming
- cost function
- special case
- single machine scheduling problem
- computational complexity
- np hard
- multi dimensional
- combinatorial optimization
- error bounds
- branch and bound algorithm
- space complexity
- evolutionary algorithm
- approximation ratio
- release dates