Patent ID: 7908163

Claim:
A method for determining an optimal assignment of workers to tasks comprising: constructing, using a computer, a topological sort of an admissible evolution of execution for a directed acyclic graph, wherein the directed acyclic graph describes dependencies between tasks and a probability of task completion by each worker; and deriving, using the computer, the optimal assignment of workers to tasks at any stage of the execution of the tasks from the topological sort, wherein said optimal assignment is derived by, processing a node of an admissible evolution of execution; determining a set of eligible tasks for the node; determining that there exists an assignment S of workers to the set of eligible tasks that has not been previously considered; determining an optimal assignment S of workers to the set of eligible tasks by, defining a minimum value of workers and an assignment for each node; setting I equal to the set of eligible tasks; determining that there is a non-empty subset, D, of the set of eligible tasks I that has not been previously considered; determining a probability a D , for each assignment for each respective node, that the non-empty subset, D, is exactly the set of tasks executed by workers in the respective assignment; determining, using a recursive equation, an expected completion time; determining the probability b that every worker in the assignment S fails to perform an assigned task from the set of eligible tasks; determining an average of the expected completions times weighted by the a D 's and b; determining a weighted sum with the probabilities a D and b, and the average of the expected completion times, and the minimum value of workers; selecting an assignment that minimizes the weighted sum of workers assigned to eligible tasks; setting the minimum value of workers equal to the minimized weighted sum of workers assigned to eligible tasks; processing the next node; and assigning, using the computer, the optimal assignment S of workers to the tasks.