On the Approximability of Related Machine Scheduling Under Arbitrary Precedence

作     者：Aggarwal, Vaneet Lan, Tian Subramaniam, Suresh Xu, Maotong 

作者机构：Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA George Washington Univ Dept Elect & Comp Engn Washington DC 20052 USA Facebook News Feed Menlo Pk CA 94025 USA 

出 版 物：《IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT》 (IEEE网络与服务管理汇刊)

年 卷 期：2021年第18卷第3期

页      面：3706-3718页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：ONR [N00014-20-1-2146] U.S. National Science Foundation [CNS-1618335] CISCO 

主　　题：Related machine scheduling precedence constraints directed acyclic graph approximation algorithm 

摘      要：Distributed computing systems often need to consider the scheduling problem involving a collection of highly dependent data-processing tasks that must work in concert to achieve mission-critical objectives. This paper considers the unrelated machine scheduling problem for minimizing weighted sum completion time under arbitrary precedence constraints and on heterogeneous machines with different processing speeds. The problem is known to be strongly NP-hard even in the single machine setting. By making use of Queyranne s constraint set and constructing a novel Linear Programming relaxation for the scheduling problem under arbitrary precedence constraints, our results in this paper advance the state of the art. We develop a 2(1 + (m-1)/D)-approximation algorithm (and 2(1 + (m-1)/D) + 1-approximation) for the scheduling problem with zero release time (and arbitrary release time), where m is the number of servers and D is the task-skewness product. The algorithm can be efficiently computed in polynomial time using the Ellipsoid method and achieves nearly optimal performance in practice as D O(m) when the number of tasks per job to schedule is sufficiently larger than the number of machines available. Our implementation and evaluation using a heterogeneous testbed and real-world benchmarks confirms significant improvement in weighted sum completion time for dependent computing tasks.