0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – prubin Jul 11 '17 at 22:23
  • $\begingroup$ 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. $\endgroup$ – Daugmented Jul 11 '17 at 22:31
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks @prubin, the graphs can have a few hundred nodes. I think that ILP might not be realistic (but I'm no expert). A "good" solution in reasonable time is perfect for my situation. The guided random approach sounds interesting, what do you mean? $\endgroup$ – Daugmented Jul 12 '17 at 19:12
  • $\begingroup$ There are a variety of metaheuristics, many (but not all) patterned on biology or physical phenomena. The latter category includes simulated annealing and (I think) particle swarm search; the former includes genetic/evolutionary algorithms, ant colony optimization, a bunch I can't remember now, and my personal favorite (name-wise), slime mold optimization. (No, I did not make that last one up.) ... $\endgroup$ – prubin Jul 12 '17 at 23:00
  • $\begingroup$ ... Fundamentally, you define what constitutes a solution (usually a permutation of the nodes, but could be something else), what constitutes a "neighborhood" of a solution (other solutions you can get to from the current solution) and some logic about how to explore. $\endgroup$ – prubin Jul 12 '17 at 23:03
  • $\begingroup$ You might want to take a look at CP first. If the number of jobs that would fit in each slot (meaning all prereqs are done) tends to be modest, it might be fast enough for you. (Sorry for all the comments; the character limit forced a lot of chunking.) $\endgroup$ – prubin Jul 12 '17 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.