The problem is to find the minimum number of stages in which we can finish a set of processes, where we have a maximum number of processes we can do per stage, and there are prerequisites for the processes. Given a directed acyclic graph, the nodes of the graph represent processes, and the directed edges represent a prerrequisite ($A \rightarrow B$ means $A$ must be processed before $B$); there is a constant $M$ that represent the max number of processes that can be done per stage.
I tried this algorithm:
(The graph is assumed to be acyclic)
compute the in-degree of all nodes
Start a queue with all the nodes of in-degree 0
While the queue is not empty {
Dequeue up to M nodes
For each dequeued node, decrease the in-degree of each neighbor node by one, and if the in-degree becomes 0, enqueue that node.
}
This algorithm gives me a way in which I can finish all the processes, but it is not always the optimal way.
Consider this example: Nodes: A,B,C,D,E,F Prerequisites: D -> E, C -> E, E -> F
The algorithm may give different answers depending if we enqueue B,C,D in the first iteration (Optimal) or if we enqueue A,B,C.
I want to know if there is an "optimal" algorithm for doing this. At this point I could only think to check all possible ways. Is there a more optimal way?
