Job scheduling problem


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


Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: