Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates.
Philip M. KaminskyDavid Simchi-LeviPublished in: Oper. Res. Lett. (2001)
Keyphrases
- single machine
- release dates
- single machine scheduling problem
- scheduling problem
- competitive ratio
- total weighted tardiness
- processing times
- dynamic programming
- maximum lateness
- parallel machines
- cost function
- sequence dependent setup times
- earliness tardiness
- hybrid algorithm
- precedence constraints
- minimize total
- worst case
- scheduling jobs
- lower and upper bounds
- simulated annealing
- np hard
- search space
- release times
- particle swarm optimization
- linear programming
- objective function