<p>The problem can be solved in $O(n^2)$:</p>

<p>Denote $A=\{a_1,\ldots,a_n\}, B=\{b_1,\ldots,b_n\}$.
We will build a graph in which every node $(i,j,x)$ will denote which $a$'s and $b$'s we have already executed and $x$ is a bit representing if the last task was $a$.</p>

<ul>
<li>Construct the product graph $$G_p=(V_p, E_p)$$
$$V_p = A\times B\times \{0,1\}$$
$$E_p = \{((a_i,b_j,x),(a_{i+1},b_j,0))\mid x\in\{0,1\},j\leq i\in[n-1]\}$$
$$ \cup \{((a_i,b_j,x),(a_i,b_{j+1},1)\mid  x\in\{0,1\},j\leq i+1\in[n]\}$$</li>
<li>Assign weights:
$$w(((a_i,b_j,0),(a_{i+1},b_j,0)))=E(a_i,a_{i+1})$$
$$w(((a_i,b_j,1),(a_{i+1},b_j,0)))=E(b_j,a_{i+1})$$
$$w(((a_i,b_j,0),(a_i,b_{j+1},1))) = E(a_i,b_{j+1})$$
$$w(((a_i,b_j,1),(a_i,b_{j+1},1))) = E(b_j,b_{j+1})$$</li>
</ul>

<p>And now simply find the shortest path with an algorithm of your choice (run time is linear in $|G_p|$, since it is a DAG).</p>

CC BY-SA 3.0
2015-01-26T10:16:18.093Z
2015-01-26T10:34:42.947Z
2015-01-26T10:34:42.947Z
R B
<p>Given an integer $K$, a set of tasks $T=\{a_1,b_1,\dots,a_n,b_n\}$ with sequence dependent execution times $E:T \times T \rightarrow \mathbb{N}$ and precedence constraints on $T$ of the following structure:</p>

<p><img src="https://i.sstatic.net/WBdV8.jpg" alt="enter image description here"></p>

<p>Does an ordering function $F:T\rightarrow \{1,2,\dots, 2n\}$ exist such that $F(b_n) \leq K$ ($b_n$ is always the last task in the ordering)?
What is the computational complexity of the problem? </p>

<p>If arbitrary precedence constraints (or any partial orderings) are allowed then the problem is NP-Complete (becomes Jobshop / Flowshop or their variant). The question is what is the complexity in the case when the tasks have the precedence constraints with the fixed structure? </p>

CC BY-SA 3.0
2015-01-26T10:03:07.577Z
What do you mean by "execution time is specific to a pair of tasks"? Does it depend on the current task and previous task? Anything else?
R B
CC BY-SA 3.0
2015-01-26T10:11:57.540Z
Yes it only depends on the current task and the previous task (sequence dependance).
Umar
<time-complexity>
Is the following problem in P or in NP?
Umar
# Is the following problem in P or in NP?

(Asked by: username_0 on 2015-01-26)

Given an integer $K$, a set of tasks $T=\{a\_1,b\_1,\dots,a\_n,b\_n\}$ with sequence dependent execution times $E:T \times T \rightarrow \mathbb{N}$ and precedence constraints on $T$ of the following structure:

![enter image description here](https://i.sstatic.net/WBdV8.jpg)

Does an ordering function $F:T\rightarrow \{1,2,\dots, 2n\}$ exist such that $F(b\_n) \leq K$ ($b\_n$ is always the last task in the ordering)?
What is the computational complexity of the problem?

If arbitrary precedence constraints (or any partial orderings) are allowed then the problem is NP-Complete (becomes Jobshop / Flowshop or their variant). The question is what is the complexity in the case when the tasks have the precedence constraints with the fixed structure?

**Tags:** time-complexity

> **Comments:**
> **username_1**: What do you mean by "execution time is specific to a pair of tasks"? Does it depend on the current task and previous task? Anything else?  
> **username_0**: Yes it only depends on the current task and the previous task (sequence dependance).  

---

## 1 answers

### Answer by username_1 on 2015-01-26. Score: 5 | Accepted answer

The problem can be solved in $O(n^2)$:

Denote $A=\{a\_1,\ldots,a\_n\}, B=\{b\_1,\ldots,b\_n\}$.
We will build a graph in which every node $(i,j,x)$ will denote which $a$'s and $b$'s we have already executed and $x$ is a bit representing if the last task was $a$.

* Construct the product graph $$G\_p=(V\_p, E\_p)$$
  $$V\_p = A\times B\times \{0,1\}$$
  $$E\_p = \{((a\_i,b\_j,x),(a\_{i+1},b\_j,0))\mid x\in\{0,1\},j\leq i\in[n-1]\}$$
  $$ \cup \{((a\_i,b\_j,x),(a\_i,b\_{j+1},1)\mid x\in\{0,1\},j\leq i+1\in[n]\}$$
* Assign weights:
  $$w(((a\_i,b\_j,0),(a\_{i+1},b\_j,0)))=E(a\_i,a\_{i+1})$$
  $$w(((a\_i,b\_j,1),(a\_{i+1},b\_j,0)))=E(b\_j,a\_{i+1})$$
  $$w(((a\_i,b\_j,0),(a\_i,b\_{j+1},1))) = E(a\_i,b\_{j+1})$$
  $$w(((a\_i,b\_j,1),(a\_i,b\_{j+1},1))) = E(b\_j,b\_{j+1})$$

And now simply find the shortest path with an algorithm of your choice (run time is linear in $|G\_p|$, since it is a DAG).


---

