Approximation Results for Makespan Minimization with Budgeted Uncertainty.
Marin BougeretKlaus JansenMichael PossLars RohwedderPublished in: WAOA (2019)
Keyphrases
- makespan minimization
- polynomial time approximation
- job shop scheduling problem
- approximation algorithms
- metaheuristic
- processing times
- parallel machines
- scheduling problem
- special case
- error bounds
- np hard
- polynomially solvable
- flowshop
- single machine
- total weighted tardiness
- setup times
- job shop scheduling
- np complete
- bin packing
- approximation ratio
- release dates
- genetic algorithm
- simulated annealing
- distributed systems