Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors

作     者：Kubiak, Wieslaw Rebaine, Djamal Potts, Chris 

作者机构：Mem Univ Newfoundland Fac Business Adm St John NF Canada Univ Quebec Dept Math & Informat Chicoutimi PQ Canada Univ Southampton Sch Math Southampton Hants England 

出 版 物：《DISCRETE OPTIMIZATION》 (离散优化)

年 卷 期：2009年第6卷第1期

页      面：79-91页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070102[理学-计算数学] 0701[理学-数学] 

基　　金：Natural Sciences and Engineering Research Council of Canada (NSERC) [OPG0105675, 262465] Ministry of Science of Poland [N519188933] 

主　　题：Complexity Divide-and-conquer graph HLF Identical parallel processors Makespan 

摘      要：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 N P-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. (C) 2008 Elsevier B.V. All rights reserved.