We are given a DAG (directed acyclic graph) in which every node $v$ represents an operation and every edge $e=(v,u)$ represents a dependency of $u$ on the output of $v$. We are also given weights $w(v)\in\mathbb{N}$ representing the amount of memory needed for the output of $v$.
By a legal operation of $v$, we mean that all of the inputs of $v$ have been performed (their outputs ready in the memory) and the output of $v$ of size $w(v)$ is written to unallocated memory (the inputs of $v$ cannot be overwritten by the output of $v$).
A schedule of the DAG is some topological sort of the DAG given with memory allocations for every operation in the DAG so that we can legally operate all of them.
What is the minimum amount of memory needed for a schedule of the DAG (with the schedule and memory allocations)?
I tried finding a representation of the problem using dynamic online bin packing algorithms, but we have no bins here, rather, one single infinite bin (and we also can't rearrange the units after they were added). I thought that there might be some representation of this problem as a 1 dimensional dynamic tiling, but I had no luck so far.
I would appreciate any reference to similar problems. Thanks!
I can't name a problem that's a close match, but I can say that your problem has similarities to machine scheduling (job precedence, resource blocking). It would not be hard to formulate and solve a model using either mixed integer linear programming (MILP) or constraint programming (CP). I'm not sure which would prove faster in practice. Also, if you would be satisfied with a "good" (rather than provably optimal) sequence, you could probably have good luck with a metaheuristic (guided random search).
I jotted down a MILP model that looks plausible. It has $N^2$ 0-1 variables and about twice that many continuous variables, where $N$ is the number of nodes in the DAG. For $N$ not too large, it should be pretty solvable.