Job scheduling: minimizing number of reads Consider the following scheduling problem:

input: 


set of computations $C = \{c_1, ..., c_n\}$ 
set of computing nodes $P = \{p_1, ..., p_n\}$
Dependency graph $D$ between jobs (DAG) $(c_i,c_j)$ means $c_i$ depends on/reads $c_j$ 


output:

Schedule S = subset of $C \times [1,n]$ where $(c_i,k)$ means that job $c_i$ will be executed in timeslot $k$
the following conditions hold:


precisely one timeslot per job
dependencies have lower timeslots


Now, we want to minimize the cost of the schedule:


$cost(c_i,S) = |\{ k \mid (c_j,k) \in S \wedge (c_i, c_j) \in D \}|$
i.e. the cost of a job is the number of levels where it is read
$totalCost(S) = \sum_{c_i \in C} cost(c_i,S)$


Hence, we want to calculate the best way of assigning the computations to timeslots, such that the number of reads are minimized. Note that the number of computing nodes is irrelevant.

I cannot seem to find any papers on this specific problem. Does anyone know whether this has been investigated? It seems it has to be... :) 

Edit:

we can rephrase this as a graph problem:
Consider a DAG $G = (V,E)$. 

A schedule is a mapping $S:V\rightarrow\mathbb{N}$ which assigns a number to each node, such that if $v_1$ is reachable from $v_2$, then $S(v_1) &lt; S(v_2)$.

Define the cost of a node $v_1$ is defined as $cost(v_1) = |\{S(v_2) \mid (v_2,v_1) \in E\}|$, i.e., the number of different numbers that are assigned to parent nodes.

The problem: find a schedule S that minimizes the total cost over the nodes.
After a failed polynomial-time quick attempt, here it is an idea to prove that it is NP-complete using a reduction from 3SAT.

Given a 3SAT formula with $x_1,...,x_n$ variables and $C_1,...,C_m$ clauses, first build a variable assignment gadget like in the figure below (thanks to @Jukka for the clarifications, the graph drawing style, and the hint for the gadget with two configurations and same cost!).



Each blue horizontal line corresponds to a different schedule time ($s=1,2,...$).
On the left of the picture there is a complete assignment gadget for three variable ($x1,x2,x3$).
The red nodes correspond to a $true$ assignment ($+x_i$), the blue nodes to a $false$ assignment ($-x_i$). A green node correspond to a variable $x_i$ and can be placed
on the same schedule time of the red or the blue node, without afftecting the total cost of the gadget. The three possible combinations for $x_1$ are showed on the right. The number in the nodes represents the cost (the number of distinct parents). Both $x_1 = true, x_1 = false$ have a cost of 7 ($c=7$). Note that the last combination has a greater cost so it cannot be used.

Now we extend the assignment gadget to "simulate" the clauses of the formula.



First we add a top node, and a mirror chain of $3n+2$ nodes (the chain of nodes on the left of the picture). By construction some of the nodes of the mirror chain must be on the same schedule time of the $true/false$ assignments; we call them $+x'_1, -x'_1, +x'_2, -x'_2,...$ (yellow nodes of the mirror chain in the figure).
Now we add a clause node $C_j$ for each clause and we force it to be at schedule time $s=1$ by adding two directed edges from the bottom of the mirror chain and assignment gadget.

We link the clause node to the three variables it contains (green edges in the figure), and to the corresponding positive/negative literal in the mirror chain (red edges in the figure). Finally we link the clause node to the top node using a chain of 6 clause pegs $P_{j_1},...,P_{j_6}$ (purple nodes in the figure).

How it works

The clause pegs of $C_j$ are linked together so they must be placed at different schedule times. So the cost of $C_j$ is greater than or equal to $6$. We can keep the cost of $C_j$ equal to 6 if and only if the assignment corresponding to the position of the green variables nodes contained in $C_j$ satisfies $C_j$.

First of all note that the bottom peg $P_{j,1}$ must be put at schedule time $s=2$ because $C_j$ is linked to the bottom of the assignment gadget and mirror chain. So only 5 of the pegs are "free" to be assigned to greater schedule times (otherwise the cost of $C_j$ is \geq 7$).

Now, suppose for example that $C_1$ is $(x_1 \lor \bar{x}_2 \lor x_3)$ (like in the figure). We have the green edges: $x_1 \to C_1, x_2 \to C_1, x_3 \to C_1$ and the red edges $+x'_1 \to C_1, -x'_2 \to C_1, +x'_3 \to C_1$.

Suppose that we set $x_1 = true, x_2 = true, x_3=false$ then the green variable $x_1$ will be on the same schedule time of $+x'_1$. But $x_2, -x'_2$ and $x_3, +x'_3$ will be on different schedule times. We can put a peg on the same schedule time of $x_1=true$, and the remaining 4 can be placed on the same schedule times of $x_2=true, -x'_2, +x'_3, x_3=false$ ("mask" them). The total cost of $C_1$ is still 6.

But what happens if we cannot find an assignment that satisfy all clauses? Then, in at least one clause (suppose $C_1$), the green variable nodes $x_1=false,x_2=true,x_3=false$ are all on a different schedule time of the corresponding $+x'_1, -x'_2, +x'_3$. So the 5 free pegs are not enough to "mask" them and the number of distinct parents of $C_1$ increases to $7$, like in the figure below.



Note that without the pegs, the (minimum) total cost $c_t$ of the schedule is fixed, so we can conclude that after adding the pegs, the original formula is satisfiable if and only if the total cost of the graph is less than $c_t + 6*m$.