# Minimal static memory allocation for a schedule

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!

• Is it correct to assume that memory consumed by output $v$ is recovered after the last of node $v$'s immediate successors has been executed (with the understanding that the last successor's output will coexist with $v$'s output for an instant)? – prubin Jul 11 '17 at 22:23
• Yes @prubin, we should assume that it is released automatically but is part of the total (with the successors) needed for an instant before it is released. – Daugmented Jul 11 '17 at 22:31

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.