CODEWITHSUNDEEP
algorithmdirected-acyclic-graphstopological-sort
asudoiha oaihd
asudoiha oaihd

Reputation: 31

Algorithm To Schedule Processes with Dependencies, (Linear Time)

I'm having a bit of trouble trying to figure out how to create an algorithm that creates a schedule to minimise the smallest possible time used. Here is the problem.

Consider a program with processes 1,2,3,4...n . All processes must be completed for the program to work and some processes may be dependent on another process to complete. (E.G Process 2 is dependent on Process 1, meaning we must complete process 1 before starting process 2)

We are given an unlimited number of machines so that Processes can be run in parallel

All processes take the same time to complete

Design an algorithm to use the lowest amount of time to run the program, given the lists of dependencies for all processes as input.

Thanks for any help!

So the way I wanted to make this algorithm was to think of the problem as a DAG (directed acyclic graph), then use topological sort to create an order to complete the tasks however, I am confused as to how to find the quickest solution.

For example lets say we have:

A is dependent on nothing \
B is dependent on A \
C is dependent on A \
D is dependent on C \
E is dependent on nothing \
F is dependent on B, D, E \

If each process takes 1 second to complete and we can use unlimited machines to process them in parallel, then we can complete the program in 4 seconds right?

But how do I create an algorithm to find out that 4 second is the smallest number?

Sorry If I haven't been able to explain the problem clearly,

Upvotes: 3

Views: 839

Answers (3)

Sam Ginrich
Sam Ginrich

Reputation: 841

Pathes of a depedency graph display the run time, which cannot be reduced by parallel processsing. The longest one in time among these is your "smallest number".

Upvotes: 0

Rajesh Kumar
Rajesh Kumar

Reputation: 70

Build a dependency graph where entry for a process will contain list of processes which depends on that process. Also create a degree array for all the processes which counts the number of processes a process depends on. Iterate throught the degree array and add the process having 0 degree in a queue. Now write a while loop which will run while count of queue is greater than 0. In each loop deque one process and from graph get the processes dependent on this this process decrease their degree by 1 and if degree becomes 0 then add the process to queue. https://leetcode.com/problems/course-schedule/

https://leetcode.com/problems/course-schedule/submissions/1228251959/

Upvotes: 2

pasthec
pasthec

Reputation: 339

Since we have an unlimited number of machines, as soon as it is possible to process a task, it is optimal to allocate a new machine to do it. So we can do a greedy algorithm from this observation :

Let ToDo be an empty queue
Let time = 0

For every node u :
   If u has no dependency :
      Add (u, 1) at the end of the ToDo
  
While ToDo is not empty :
   Let (u, t) be the head of ToDo
   Let time = max(time, t)
   For all nodes v depending on u :
         If u was the only dependency of v :
            Add (v, t+1) to the end of ToDo
   Remove u from the graph //(Hence no node depend on u anymore)

Return time

Upvotes: 2

Related Questions