### Multiprocessing scheduling under uncertainty

Co-authorGuolong Lin

We study a multiprocessor scheduling problem in which there is
uncertainty concerning the successful execution of a job on a given
processor. In this problem, we are given n
unit-time jobs and m machines, with
precedence constraints among the jobs. For every job j and machine i, we are
also given p_{ij}, which is the
probability that job j when scheduled on a
machine i will be successfully completed,
independent of all other job execution events. Multiple machines can
be assigned to the same job at the same time. The goal of the problem
is to find a schedule such that the expected completion time of all
the jobs is minimized.

The above scheduling problem is motivated by grid computing applications in which a large collection of unreliable machines may be handling a large collection of complex tasks with dependencies among them. The problem also models project management scenarios in which there may be uncertainty in the successful execution of the project tasks.

In this talk, we will present a polynomial time poly-logarithmic approximation algorithm for the problem when the precedence constraints form a forest. Interestingly, we achieve this approximation ratio using oblivious schedules, that do not attempt to adapt to the outcomes of uncertain job executions.