Single-machine scheduling to minimize the total earliness and tardiness is strongly NP-hard.
Long WanJinjiang YuanPublished in: Oper. Res. Lett. (2013)
Keyphrases
- single machine scheduling
- strongly np hard
- single machine scheduling problem
- sequence dependent setup times
- setup times
- branch and bound algorithm
- scheduling problem
- precedence constraints
- lower bound
- single machine
- processing times
- approximation algorithms
- np hard
- combinatorial optimization
- upper bound
- lagrangian relaxation
- flowshop
- resource consumption
- branch and bound
- worst case
- special case
- optimal solution
- search procedure