Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime.
Peruvemba Sundaram RaviLevent TunçelMichael HuangPublished in: J. Sched. (2016)
Keyphrases
- approximation algorithms
- minimizing makespan
- scheduling problem
- worst case
- np hard
- flowshop
- special case
- single machine
- lower bound
- minimum cost
- vertex cover
- average case
- np hardness
- tabu search
- setup times
- integer programming
- parallel machines
- optimal solution
- processing times
- approximation ratio
- constant factor
- randomized algorithms
- flowshop scheduling
- precedence constraints
- upper bound
- approximation schemes
- set cover
- job shop
- open shop
- linear programming
- sequence dependent setup times
- permutation flowshop
- constant factor approximation
- undirected graph
- online algorithms
- lagrangian relaxation
- greedy algorithm
- computational complexity
- combinatorial auctions
- knapsack problem
- error bounds