Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines.
Rubing ChenJinjiang YuanPublished in: J. Sched. (2019)
Keyphrases
- np hardness
- single machine scheduling
- single machine scheduling problem
- np hard
- approximation algorithms
- pairwise
- branch and bound algorithm
- response time
- precedence constraints
- mixed integer
- scheduling problem
- single machine
- lagrangian relaxation
- processing times
- lower bound
- optimal solution
- integer programming
- feasible solution
- linear program
- linear programming
- special case