Name
Abstract | ||
|---|---|---|
In this paper, a parallel branch-and-bound approach for finding 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 find 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-first branch-and-bound) used separately, in terms of the quality of the schedule found. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1016/S0167-8191(99)00095-2 | Parallel Computing |
Keywords | Field | DocType |
approximation scheme,multiprocessor scheduling problem,scheduling problems,branch-and-bound,parallel approximation scheme,parallelism,genetic algorithm,branch and bound,lower bound,multiprocessor scheduling,genetics,scheduling problem | Branch and bound,Mathematical optimization,Multiprocessor scheduling,Overlapping subproblems,Fair-share scheduling,Computer science,Parallel computing,Nurse scheduling problem,Rate-monotonic scheduling,Dynamic priority scheduling,Genetic algorithm,Distributed computing | Journal |
Volume | Issue | ISSN |
26 | 1 | Parallel Computing |
Citations | PageRank | References |
2 | 0.37 | 14 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ricardo C. Corrêa | 1 | 207 | 18.74 |