Better Approximation Guarantees for Job-Shop Scheduling.
Leslie Ann GoldbergMike PatersonAravind SrinivasanElizabeth SweedykPublished in: SIAM J. Discret. Math. (2001)
Keyphrases
- job shop scheduling
- approximation guarantees
- greedy algorithm
- approximation algorithms
- np hard
- scheduling problem
- job shop scheduling problem
- lower bound
- approximation ratio
- objective function
- combinatorial optimization problems
- knapsack problem
- worst case
- constant factor
- linear programming relaxation
- upper bound
- resource constraints
- greedy algorithms
- optimal solution
- special case
- np complete
- genetic programming
- branch and bound algorithm
- minimum cost
- neural network