Better Approximation Guarantees for Job-shop Scheduling.
Leslie Ann GoldbergMike PatersonAravind SrinivasanElizabeth SweedykPublished in: SODA (1997)
Keyphrases
- job shop scheduling
- approximation guarantees
- greedy algorithm
- approximation algorithms
- np hard
- scheduling problem
- lower bound
- job shop scheduling problem
- objective function
- approximation ratio
- linear programming relaxation
- combinatorial optimization problems
- constant factor
- upper bound
- greedy algorithms
- tabu search
- special case
- machine learning
- resource constraints
- simulated annealing
- worst case
- minimum cost
- multi objective
- computational complexity
- genetic programming
- optimal solution
- optimization problems
- dynamic programming