Assume that there are an unlimited number of workers each of which can complete one task, each of which takes some time. There are also precedence constraints where one task cannot be completed until another is. What is the minimum amount of time needed for each task to be completed while respecting the precedence order?
As an example, lets say you have 3 tasks.
The first task takes 10 units of time to complete, the second takes 5 units of time to complete, and the third takes 6 units of time to complete.
The constraint is that the 2nd task cannot be started until the 3rd task is finished.
Given this, you can conclude that the minimum time needed for all the tasks to be completed while respecting the precedence is 11.
This is because you can do tasks 1 and 3 (which take times 10 and 6 respectively) simultaneously, and after task 3 is finished, you can begin on task 2 (which takes 5 units of time). Thus, all tasks will end at time 11.
It seems like this could be solved with a topological sort, which would give you the order in which to complete tasks in order to satisfy the constraints.
For example, in the problem, after topologically sorting the tasks you would end up with
Task 1 (10 Units of time) -> Task 3 (6 Units of time) -> Task 2 (5 Units of time)
However, once you obtain this order in which go about the tasks, how do you determine which ones can be done simultaneously and which ones need to be done one after the other? Further, how do you compute the minimum time needed for all of them to finish?