Faster Approximation Algorithms for Scheduling with Fixed Jobs.
Klaus JansenLars PrädelUlrich M. SchwarzOla SvenssonPublished in: CATS (2011)
Keyphrases
- approximation algorithms
- precedence constraints
- identical parallel machines
- open shop
- strongly np hard
- fixed number
- unrelated parallel machines
- release dates
- np hard
- identical machines
- special case
- parallel machines
- vertex cover
- job scheduling
- single machine scheduling problem
- worst case
- sequence dependent setup times
- scheduling problem
- setup times
- minimum cost
- primal dual
- flowshop
- batch processing
- constant factor
- scheduling strategy
- set cover
- facility location problem
- approximation ratio
- polynomial time approximation
- randomized algorithms
- computational grids
- processing times
- single machine
- approximation schemes
- combinatorial auctions
- wafer fabrication
- undirected graph
- scheduling algorithm
- branch and bound algorithm
- disjoint paths
- global constraints
- resource allocation
- deteriorating jobs
- constant factor approximation