Approximating the optimal competitive ratio for an ancient online scheduling problem
Lin ChenDeshi YeGuochuan ZhangPublished in: CoRR (2013)
Keyphrases
- competitive ratio
- single machine
- scheduling problem
- online algorithms
- processing times
- lower bound
- online learning
- initially unknown
- identical parallel machines
- flowshop
- optimal strategy
- setup times
- np hard
- release dates
- tabu search
- average case
- dynamic programming
- single machine scheduling problem
- worst case
- parallel machines
- asymptotically optimal
- learning algorithm
- special case