Approximation Algorithms for Scheduling Jobs with Chain Precedence Constraints.
Klaus JansenRoberto Solis-ObaPublished in: PPAM (2003)
Keyphrases
- precedence constraints
- approximation algorithms
- scheduling jobs
- release dates
- identical machines
- np hard
- parallel machines
- single machine
- scheduling problem
- vertex cover
- processing times
- single machine scheduling problem
- sequence dependent setup times
- special case
- worst case
- identical parallel machines
- production system
- setup times
- approximation ratio
- branch and bound algorithm
- constant factor
- linear programming
- batch processing
- single server
- polynomial time approximation
- optimal solution
- lower bound