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

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?

  • $\begingroup$ 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? $\endgroup$ – R B Jan 26 '15 at 10:03
  • $\begingroup$ Yes it only depends on the current task and the previous task (sequence dependance). $\endgroup$ – 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).

| cite | improve this answer | |

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.