Multiprocessing scheduling under uncertainty
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 pij, 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.