# Is the following problem in P or in NP?

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:

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?

• 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 Jan 26 '15 at 10:03
• Yes it only depends on the current task and the previous task (sequence dependance). – Umar Jan 26 '15 at 10:11

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