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