A branch and bound algorithm for scheduling jobs with controllable processing times on a single machine to meet due dates.
Kailiang XuZuren FengLiangjun KePublished in: Ann. Oper. Res. (2010)
Keyphrases
- single machine
- scheduling jobs
- branch and bound algorithm
- processing times
- single machine scheduling problem
- scheduling problem
- np hard
- lower bound
- branch and bound
- release dates
- precedence constraints
- upper bound
- lower bounding
- optimal solution
- maximum lateness
- release times
- sequence dependent setup times
- combinatorial optimization
- setup times
- dynamic programming
- identical machines
- lagrangian relaxation
- special case
- resource consumption
- competitive ratio
- flowshop
- approximation algorithms
- integer programming
- linear programming
- shortest processing time