Well,

This problem was written on whiteboard by manoj for others to solve and finally arpita solved it for the most part with me chipping in at the end.

**Problem : **There are n jobs to be done and 2 processor available. Each job take the same amount of time ( so for simplicity one can assume it takes unit time ). Both processor have the same capabilities. A job may depend on other jobs, for example if job A is dependent on B and C then A can not be scheduled before B and C both are finished. Dependancies amogst jobs are given. Give an algorithm to find the optimum schedule ( in terms of time to finish all jobs ).

**Solution ; **Because dependacies are given, one can generate a dependacy graph. This graph is a DAG ( Directed Acyclic Graph ). Because if there is a cycle then all jobs which participate in the cycle can never be scheduled. Now, compute the transitive closure, in a sense that if there are edges A -> B and B -> C, then add an edge A -> C.

This way we have obtained all dependencies, direct as well as indirect, in this graph G. Forget about the direction of the edges for a moment and compute a complement graph G’. It is easy to see two jobs can be scheduled in parallel if and only if there is an edge between them in G’. Find a maximum matching ( 1-factor ) of G’. Minimum time taken would

# of edges in G’ + # of unmatched nodes in G’.

Of course, the ordering is still needs to be decided.

Let’s get back to G now. We will merge nodes which were matched in G’, that will give us another DAG. Topological sort on this DAG would give us the order in which we should schedule the jobs.

Though I am not fully confident, I believe that this method would give us the optimum schedule. One more point to ponder is that whether this can be generalized for k-processors.

— Saurabh Joshi

### Like this:

Like Loading...

*Related*

Tags: graph theory, job scheduling, math

This entry was posted on December 29, 2008 at 6:28 am and is filed under math. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply