7
$\begingroup$

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:

  1. precisely one timeslot per job
  2. 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) < 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.

$\endgroup$
  • 1
    $\begingroup$ If I understood correctly, here is another way to state the problem: given a DAG $D$, label the nodes with integers so that predecessors have smaller labels and the cost of a node is the number of predecessors with distinct labels? $\endgroup$ – Jukka Suomela May 23 '14 at 16:59
  • $\begingroup$ actually yes, except that the cost is the number of distinct labelled successors (children). I clarified the DAG usage. $\endgroup$ – Jonny5 May 26 '14 at 6:25
  • 1
    $\begingroup$ Could you perhaps edit the question and rephrase it as a graph problem? It might be easier to get answers if the question is short and easy to understand. $\endgroup$ – Jukka Suomela May 26 '14 at 10:42
  • $\begingroup$ What is $J$? I don't understand the cost/objective in the question. $\endgroup$ – R B May 26 '14 at 10:46
  • $\begingroup$ @RB: I guess $J = C$ (i.e., the set of nodes in DAG $D$). $\endgroup$ – Jukka Suomela May 26 '14 at 10:54
6
$\begingroup$

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!).

enter image description here

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.

enter image description here

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.

enter image description here

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$.

$\endgroup$
  • 1
    $\begingroup$ The induced graph on $X_1$ can be arbitrary large for example $n/2$. How do you want assign numbers in polynomial time? $\endgroup$ – Saeed May 26 '14 at 23:08
  • $\begingroup$ @Saeed: I've switched from polynomial-time to NPC :-))) ... if you want take a look at the proof (I wrote it quickly so it can be wrong, as well). $\endgroup$ – Marzio De Biasi May 28 '14 at 18:51
  • $\begingroup$ Hi Marzio, I tried to read it but I failed. At least I didn't get why "$x_1$ will be on the same schedule time of $+x′_1$" $\endgroup$ – Saeed May 28 '14 at 20:41
  • $\begingroup$ Also I think this sentence is not correct while the aim you want to achieve is correct: "First of all note that the bottom peg Pj,1 must be put at schedule time s=2 because Cj is linked to the bottom of the assignment gadget and mirror chain. " $\endgroup$ – Saeed May 28 '14 at 20:44
  • $\begingroup$ What is your hunch: is there any hope that a greedy solution could be e.g. a constant-factor approximation? $\endgroup$ – Jukka Suomela May 28 '14 at 21:55
3
$\begingroup$

This is a non-answer, but it might help to understand the question (assuming that I understood it correctly).

Here is a simple but slightly non-trivial example:

enter image description here

Here:

  • input = black graph
  • output = on which blue line we place each node = when to schedule each job
  • costs = orange numbers = number of predecessors with different labels

Left = simple greedy solution, right = optimal solution.


I would not be surprised if this was NP-hard. There seem to be opportunities for designing all kinds of gadgets. For example, here is a gadget in which we have two optimal solutions—one of the sink nodes has to pay 2 units, but you can choose which one.

enter image description here

$\endgroup$
  • $\begingroup$ I still don't understand the problem :-S. The OP says that if $v_2 \to v_1$ then $S(v_1) < S(v_2)$, but in your (top) examples the constraint is not satisfied. Furthermore in your top two figures, the blue numbers (the legend says that is is the output) are the same. I was thinking of a greedy approach starting from the end of one of the longest path (that must have different decreasing costs) and going backward; but probably my interpretation is wrong. The question remains a mistery :-) And what is the role (if any) of P? $\endgroup$ – Marzio De Biasi May 26 '14 at 21:46
  • $\begingroup$ @MarzioDeBiasi: In my drawing, e.g. $S(v) = 3$ is denoted by placing the node $v$ on top of the blue line labelled with "3". The constraints are satisfied; all edges point from larger labels towards smaller labels. $\endgroup$ – Jukka Suomela May 26 '14 at 22:15
  • $\begingroup$ @MarzioDeBiasi: And forget about $P$, as far as I can see, it plays no role here. $\endgroup$ – Jukka Suomela May 26 '14 at 22:21
  • $\begingroup$ Now I see it, thanks! :-) It seems it matches my interpretation. I'll post the greedy algorithm, perhaps you scan easily check if it is wrong and find a counterexample. $\endgroup$ – Marzio De Biasi May 26 '14 at 22:35
1
$\begingroup$

I found a reduction from the Partition Problem to a modified version of the proposed problem.

Partition Problem (Optimization)

  • input: set of integers S
  • output: partition of S into S1 and S1 such that the difference of the sums of S1 and S2 is minimized: $$\lvert\sum_{s\in S1}s - \sum_{s\in S2}s\lvert.$$

This problem is NP-hard.

Level Assignment Problem (Optimization)

  • input: a DAG $G = (V,E)$, a weight function $w:V\rightarrow\mathbb{Z}$
  • output: a mapping $m:V\rightarrow[1,depth(G)]$ such that:
    1. $(v1,v2) \in E \Rightarrow m(v1) > m(v2)$
    2. the following is minimized: $$sum\{ numlevels(v) \times w(v) \mid v \in V\},$$ where $$numlevels(v) = |\{m(v') \mid (v',v) \in E \}|.$$

Reduction

The reduction from the partition problem to the level assignment problem can be done as follows: for each $s_i \in S$, create the following gadget, where the weights are indicated between brackets:

gadget for a number si

It is easy to see that the following mappings are obligatory:

  • $m(A_i) = 1$
  • $m(B_i) = 1$
  • $m(A'_i) = 2$
  • $m(B'_i) = 3$

Hence, the only choice left is $m(v_i)$. When choosing $m(v_i) = 2$, this gadget will contribute $s_i$ to the total sum. When $m(v_i) = 3$, it will contribute $-s_i$.

Now, after solving the level assignment problem, group the $s_i$ in the following way:

  • $S_1 = \{s_i \in S \mid m(v_i) = 2\}$
  • $S_2 = \{s_i \in S \mid m(v_i) = 3\}$

The gadgets related to $S_1$ will contribute positively, those to $S_2$ negatively. Hence, we get a total cost of: $$\sum_{s \in S_1} s + \sum_{s \in S_2} (-s) = \sum_{s \in S_1} s - \sum_{s \in S_2} s.$$

This is the function that is minimized and it corresponds to the minimization problem of the partition problem. Hence, our problem must be NP-hard as well.

Note: the partition problem has an absolute value in the function to be minimized. This is no problem, as this can be accomplished by swapping $S_1$ and $S_2$.

$\endgroup$
  • $\begingroup$ I didn't read the full reduction, yet; however in the equivalent DAG formulation of your original scheduling problem there are no "weights", but only "costs" and the cost of each node is the number of distinct parents (levels). Furthermore the cost of each node (and also the final total cost) is not given as input, but it is a function of the final level assignment (schedule). So is this a different version from your original question? $\endgroup$ – Marzio De Biasi Jun 3 '14 at 12:24
  • $\begingroup$ @Marzio: when you use unit weights, this gives the same problem as the original level assignment problem. the costs in the original problem are 1 for each level, here, it is w(v_i) for each level, so it is a more general problem. $\endgroup$ – Jonny5 Jun 3 '14 at 12:26
  • $\begingroup$ Ok! (but the partition problem is not strongly np-hard so I think that you cannot use the same approach to prove the unit weights version). Did you check my reduction? $\endgroup$ – Marzio De Biasi Jun 3 '14 at 12:29
  • $\begingroup$ yes, your reduction seems ok. Could it also be possible to reduce from the Partition Decision problem (sums of S1 and S2 must be equal) and creating $s$ nodes for each $s \in S$? Or is it not allowed to created this amount of nodes in a poly reduction? $\endgroup$ – Jonny5 Jun 3 '14 at 12:52
  • $\begingroup$ I think it's not possible because the partition problem is not strongly NP-complete. But perhaps you can try with the 3-PARTITION PROBLEM, which is strongly NPC (it is still NPC even if numbers are represented in unary) and end up with a reduction that is simpler than mine. $\endgroup$ – Marzio De Biasi Jun 3 '14 at 13:01

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.