A Survey on Approximation Algorithms for Scheduling with Machine Unavailability.
Florian DiedrichKlaus JansenUlrich M. SchwarzDenis TrystramPublished in: Algorithmics of Large and Complex Networks (2009)
Keyphrases
- approximation algorithms
- precedence constraints
- np hard
- batch processing
- scheduling problem
- special case
- parallel machines
- strongly np hard
- sequence dependent setup times
- flowshop
- vertex cover
- manufacturing cell
- worst case
- minimum cost
- network design problem
- scheduling algorithm
- set cover
- wafer fabrication
- open shop
- approximation schemes
- resource allocation
- facility location problem
- release dates
- constant factor
- disjoint paths
- lower bound
- approximation ratio
- np hardness
- job shop scheduling
- single machine scheduling problem
- primal dual
- resource consumption
- polynomial time approximation
- network flow
- resource constraints
- processing times
- single machine
- upper bound
- search algorithm