Online nonpreemptive scheduling of equal-length jobs on two identical machines.
Michael H. GoldwasserMark PedigoPublished in: ACM Trans. Algorithms (2008)
Keyphrases
- identical machines
- equal length
- single machine
- precedence constraints
- processing times
- scheduling problem
- job scheduling
- unrelated parallel machines
- setup times
- parallel machines
- scheduling jobs
- release dates
- completion times
- minimize total
- branch and bound algorithm
- competitive ratio
- identical parallel machines
- polynomial time approximation
- approximation algorithms
- upper bound
- dynamic programming
- np hard