New approximation algorithms for machine scheduling with rejection on single and parallel machine.
Peihai LiuXiwen LuPublished in: J. Comb. Optim. (2020)
Keyphrases
- approximation algorithms
- parallel machines
- precedence constraints
- np hard
- scheduling problem
- open shop
- special case
- worst case
- vertex cover
- minimum cost
- sequence dependent setup times
- release dates
- primal dual
- earliness tardiness
- approximation ratio
- setup times
- randomized algorithms
- single machine scheduling problem
- disjoint paths
- linear programming