Name
Abstract | ||
|---|---|---|
In this article, we present different approximation algorithms for the scheduling of parallel modules. Each module can be executed on an arbitrary number of processors, and its execution time depends on the number of processors assigned to it. The scheduling algorithms assume that there is no dependence between the modules. In the first part of the article, we present algorithms that are based on results for the classical rectangle filling problem. Afterwards we modify an approximation algorithm for the shop scheduling problem. The resulting algorithms are simple, but efficient and guarantee tight worst-case bounds on the suboptimality of the solution. We test the quality of the generated schedules by applying the scheduling algorithm to randomly generated problem instances. |
Year | Venue | Keywords |
|---|---|---|
2011 | SpringSim (HPC) | execution time,parallel module,arbitrary number,scheduling algorithm,problem instance,shop scheduling problem,classical rectangle,present algorithm,approximation algorithm,independent multiprocessor task,different approximation algorithm |
Field | DocType | Volume |
Approximation algorithm,Multiprocessor scheduling,Fair-share scheduling,Computer science,Parallel computing,Flow shop scheduling,Two-level scheduling,Rate-monotonic scheduling,Dynamic priority scheduling,Earliest deadline first scheduling,Distributed computing | Conference | 43 |
Issue | ISSN | Citations |
2 | 0735-9276 | 0 |
PageRank | References | Authors |
0.34 | 11 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kai Baumgarten | 1 | 0 | 0.34 |
| Thomas Rauber | 2 | 415 | 64.60 |