Approximation Results for Makespan Minimization with Budgeted Uncertainty.

Marin Bougeret Klaus Jansen Michael Poss Lars Rohwedder

Published in: Theory Comput. Syst. (2021)

Keyphrases

makespan minimization
polynomial time approximation
approximation algorithms
parallel machines
job shop scheduling problem
metaheuristic

error bounds
processing times
np hard
scheduling problem
single machine
special case

flowshop
total weighted tardiness
polynomially solvable
simulated annealing
tabu search

upper bound
genetic algorithm
dynamic programming
computational complexity
objective function