Recursive Refinement of Lower Bounds in the Multiprocessor Scheduling Problem.
Satoshi FujitaMasayuki MasukawaShigeaki TagashiraPublished in: Euro-Par (2003)
Keyphrases
- scheduling problem
- lower bound
- np hard
- upper bound
- single machine
- iterative refinement
- strongly np hard
- randomly generated test problems
- branch and bound algorithm
- setup times
- flowshop
- tabu search
- permutation flowshop
- processing times
- branch and bound
- lower bounding
- minimizing makespan
- lower and upper bounds
- precedence constraints
- optimal solution
- worst case
- parallel machines
- database machines
- integer programming
- maximum lateness
- objective function
- vc dimension
- single processor
- approximation algorithms
- multiprocessor systems
- min sum
- distributed memory
- refinement process
- sample complexity