Algorithm To Schedule Processes with Dependencies, (Linear Time)

Question

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,

Answer 1

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