Two NP-Hardness Results for Preemptive Minsum Scheduling of Unrelated Parallel Machines.
René SittersPublished in: IPCO (2001)
Keyphrases
- scheduling problem
- np hard
- unrelated parallel machines
- np hardness
- min sum
- parallel machines
- setup times
- single machine
- flowshop
- approximation algorithms
- processing times
- lower bound
- special case
- optimal solution
- branch and bound algorithm
- integer programming
- tabu search
- linear programming
- precedence constraints
- linear program
- job shop
- knapsack problem
- worst case
- decision problems
- computational complexity
- lagrangian relaxation
- identical parallel machines