A 2.542-Approximation for Precedence Constrained Single Machine Scheduling with Release Dates and Total Weighted Completion Time Objective.
Martin SkutellaPublished in: CoRR (2016)
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
- parallel machines
- release times
- total weighted tardiness
- setup times
- scheduling jobs
- resource consumption
- np hard
- global constraints
- flowshop
- special case
- hybrid algorithm
- partial order
- combinatorial optimization
- worst case
- lower bound
- upper bound