Approximation Algorithms for Multiprocessor Scheduling under Uncertainty

Details Approximation Algorithms for Multiprocessor Scheduling under Uncertainty Approximation Algorithms for Multiprocessor Scheduling under Uncertainty

2007-03-21

arxiv.org/abs/cs/0703100v1

Computer Science

Distributed, Parallel, and Cluster Computing

12 pages, 2 encapsulated postscript figures

Scientific paper

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 completion time of all the jobs. 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(m)log(n)log(n+m)/loglog(n+m))-approximation when C is a collection of disjoint chains, an O(log(m)log^2(n))-approximation when C is a collection of directed out- or in-trees, and an O(log(m)log^2(n)log(n+m)/loglog(n+m))-approximation when C is a directed forest.

Affiliated with

Also associated with

No associations

Rating

Approximation Algorithms for Multiprocessor Scheduling under Uncertainty does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximation Algorithms for Multiprocessor Scheduling under Uncertainty, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Algorithms for Multiprocessor Scheduling under Uncertainty will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-168164