Name
Title | ||
|---|---|---|
Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors |
Abstract | ||
|---|---|---|
The problem of scheduling a set of n unit execution time (UET) tasks subject to precedence constraints on m identical parallel processors is known to be NP-hard in the strong sense. However, polynomial time algorithms exist for some classes of precedence graphs. In this paper, we consider a class of divide-and-conquer graphs that naturally models the execution of the recursive control abstraction of divide-and-conquer algorithms. We prove that the Highest Level First (HLF) strategy minimizes the schedule length for this class, thus settling a conjecture of Rayward-Smith and Clark. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.disopt.2008.09.001 | Discrete Optimization |
Keywords | Field | DocType |
recursive control abstraction,hlf,precedence graph,schedule length,divide-and-conquer algorithm,divide-and-conquer graph,m identical parallel processor,highest level first,divide-and-conquer uet task graph,complexity,strong sense,makespan,n unit execution time,polynomial time algorithm,identical parallel processors,divide and conquer | Discrete mathematics,Graph,Job shop scheduling,Abstraction,Computer science,Scheduling (computing),Divide and conquer algorithms,Time complexity,Conjecture,Recursion | Journal |
Volume | Issue | ISSN |
6 | 1 | Discrete Optimization |
Citations | PageRank | References |
1 | 0.35 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wieslaw Kubiak | 1 | 540 | 62.61 |
| Djamal Rebaine | 2 | 19 | 7.34 |
| Chris Potts | 3 | 1 | 0.35 |