Approximation Algorithms for Multiprocessor Scheduling under Uncertainty

作     者：Lin, Guolong Rajaraman, Rajmohan 

作者机构：Northeastern Univ Coll Comp & Informat Sci Boston MA 02115 USA Akamai Technol Cambridge MA 02142 USA 

出 版 物：《THEORY OF COMPUTING SYSTEMS》 (计算系统理论)

年 卷 期：2010年第47卷第4期

页      面：856-877页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：NSF [CCF-0635119] 

主　　题：Approximation algorithms Multiprocessor scheduling 

摘      要：Motivated by applications in grid computing and project management, we study multiprocessor scheduling in scenarios where there is uncertainty in the successful execution of jobs when assigned to processors. We consider the problem of multiprocessor scheduling under uncertainty, in which we are given n unit-time jobs and m machines, a directed acyclic graph C giving the dependencies among the jobs, and for every job j and machine i, the probability p (ij) of the successful completion of job j when scheduled on machine i in any given particular step. The goal of the problem is to find a schedule that minimizes the expected makespan, that is, the expected time at which all of the jobs are completed. The problem of multiprocessor scheduling under uncertainty was introduced by Malewicz and was shown to be NP-hard even when all the jobs are independent. In this paper, we present polynomial-time approximation algorithms for the problem, for special cases of the dag C. We obtain an O(log n)-approximation for the case of independent jobs, an O(log mlog nlog (n+m)/log log (n+m))-approximation when C is a collection of disjoint chains, an O(log mlog (2) n)-approximation when C is a collection of directed out- or in-trees, and an O(log mlog (2) nlog (n+m)/log log (n+m))-approximation when C is a directed forest.