Patent ID: 8332862

Claim:
A flow based scheduling method, comprising: receiving a job of a plurality of jobs at a scheduler, each job of the plurality of jobs comprising a root task and a plurality of worker tasks; allocating, by the scheduler, a computer in a computer cluster for execution of each of the root tasks of the plurality of jobs, the computer cluster comprising a plurality of computers; receiving information, at the scheduler from the root task, regarding the worker tasks and locations of execution of the worker tasks, wherein the received information comprises a list of ready worker tasks of the plurality of worker tasks, and, for each ready worker task, affinities between the ready worker task and the computers of the plurality of computers for execution; determining, by the scheduler based on the received information, which one of the plurality of computers each of the ready worker tasks is to execute on by generating a network flow graph using the root tasks and the ready worker tasks, wherein the network flow graph comprises a plurality of edges, wherein at least some of the edges encode the affinities between the ready workers tasks and the plurality of computers in the computer cluster; determining a solution to the network flow graph; determining an assignment of the ready worker tasks to the computers using the solution to the network flow graph; and executing each of the ready worker tasks based on the assignment on an assigned computer of the plurality of computers.