A parallel approximation scheme for the multiprocessor scheduling problem

✍ Scribed by Ricardo C. Corrêa

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 433 KB
• Volume: 26
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(99)00095-2

✦ Synopsis

In this paper, a parallel branch-and-bound approach for ®nding approximate solutions to a general version of the multiprocessor scheduling problem is presented and analyzed. In this approach, a list heuristic and a genetic algorithm are used to ®nd solutions to the subproblems enumerated during the branch-and-bound search. The strategy used to guide the search is based on the lower bound and the best solution known to each subproblem. With this strategy, the subproblems are branched only according to the precedence constraints, without generating duplicated subproblems. This algorithm was implemented in sequential and parallel, and experiments were carried out with instances from a synthetic benchmark. In these experiments, the results show that this algorithm is better than each of its components (list, genetic and best-®rst branch-and-bound) used separately, in terms of the quality of the schedule found.