Competitive Analysis of a Better On-line Algorithm to Minimize Total Completion Time on a Single-machine.
Jairo R. Montoya-TorresPublished in: J. Glob. Optim. (2003)
Keyphrases
- single machine
- competitive ratio
- minimize total
- scheduling problem
- weighted tardiness
- release dates
- dynamic programming
- computational complexity
- single machine scheduling problem
- objective function
- sequence dependent setup times
- np hard
- processing times
- optimal solution
- combinatorial optimization
- worst case
- optimal strategy
- learning algorithm
- optimization problems
- parallel machines
- multi class
- search space
- search algorithm