I have some jobs, which calculate values. Some of these jobs require the calculated values of other jobs for their own calculation. An execution plan for these jobs can be found with a topological sort on the dependency graph.
However, these calculated values are huge and occupy a large chunk of memory. I want to find a topological order that minimizes memory usage.
To give a simple example, consider the following dependency graph:
There are three possible topological orders: $1\, 2\, 3\, 4$, $1\, 3\, 2\, 4$, and $3\, 1\, 2\, 4$. Let's look at each of them.
In the first case, the values of $1$ and $3$ can be discarded immediately after $2$ and $4$ have finished, respectively, so each of them must be kept in memory for one additional step. The value of $2$ has to be kept for two additional steps until $4$ has finished. So in total we have to keep $4$ results in memory over the whole execution.
In the second case the values of $1$ and $3$ have to be kept for two steps and the value of $2$ for one step. This makes $5$ in total, so this ordering is worse in terms of memory usage.
In the third case the value of $3$ has to be kept for three steps and the values of $1$ and $2$ for one step each. Again we have a total of $5$, so this ordering is also worse than the first one. Thus the first ordering should be chosen.
Is there an efficient algorithm to find an optimal ordering without needing to inspect all possible orderings?
Bonus: is it also possible to give an optimal solution, if the values would need different amounts of memory per job?
