A (2+ϵ)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective.
René SittersLiya YangPublished in: Oper. Res. Lett. (2018)
Keyphrases
- release dates
- precedence constraints
- parallel machine scheduling problem
- single machine scheduling problem
- completion times
- processing times
- single machine
- approximation algorithms
- scheduling problem
- sequence dependent setup times
- maximum lateness
- branch and bound algorithm
- release times
- parallel machines
- total weighted tardiness
- setup times
- scheduling jobs
- global constraints
- resource consumption
- np hard
- flowshop
- worst case
- partially ordered
- branch and bound
- combinatorial optimization
- dynamic programming
- learning effect
- search procedure