Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines.
Xiao MinJing LiuYuqing WangPublished in: Inf. Process. Lett. (2011)
Keyphrases
- competitive ratio
- scheduling problem
- processing times
- single machine
- identical machines
- online algorithms
- worst case
- precedence constraints
- tabu search
- np hard
- lower bound
- flowshop
- setup times
- learning algorithm
- optimal solution
- dynamic programming
- online learning
- completion times
- support vector
- asymptotically optimal