Approximation algorithms for scheduling a single machine to minimize total late work.
Chris N. PottsLuk N. Van WassenhovePublished in: Oper. Res. Lett. (1992)
Keyphrases
- minimize total
- approximation algorithms
- single machine
- scheduling problem
- np hard
- release dates
- weighted tardiness
- precedence constraints
- special case
- worst case
- processing times
- sequence dependent setup times
- parallel machines
- single machine scheduling problem
- dynamic programming
- setup times
- production scheduling
- competitive ratio
- optimal solution
- lower bound
- total cost
- polynomial time approximation
- flowshop
- completion times
- hybrid algorithm
- knapsack problem
- tabu search
- simulated annealing