A $(2 + ε)$-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective.
René SittersLiya YangPublished in: CoRR (2017)
Keyphrases
- release dates
- parallel machine scheduling problem
- precedence constraints
- single machine scheduling problem
- processing times
- completion times
- single machine
- approximation algorithms
- scheduling problem
- sequence dependent setup times
- maximum lateness
- parallel machines
- branch and bound algorithm
- total weighted tardiness
- resource consumption
- release times
- np hard
- setup times
- partial order
- scheduling jobs
- global constraints
- flowshop
- combinatorial optimization
- lower bound
- partially ordered
- branch and bound
- worst case