This question is a followup to: Heuristics for topological sort
I have a number of modules connected in a Directed Acyclic Graph. My problem is to find an optimal execution order (minimize the total execution time). Any topological sort suffices for a valid solution, but the total execution time is depends on the transitions from a module to another, not just the execution time of the module. If the next module has the same type, executing it will have the cost $c_1$, otherwise $c_2$, $c_1 < c_2$.
A bit more in detail, having the graph
both $S_a = m_0, m_1, m_2, m_3, m_4, m_5$ and $S_b = m_0, m_2, m_4, m_3, m_1, m_5$ are valid solutions (topological sort or the graph),
the cost of the solutions are:
$c(S_a) = c_2 + c_2 + c_2 + c_2 + c_2 = 5\times c_2$
$c(S_b) = c_2 + c_1 + c_2 + c_1 + c_1 = 2\times c_2 + 3\times c_1$
So $c(S_b) < c(S_a)$, and $S_b$ is the optimal solution.
I am trying to prove that the problem is NP-complete, but I can't manage to find a good reduction.
First rewrote the problem as a decidability problem by writing it like this: Is there any sorting of the modules that will have the cost less then a value $V$ (as: is there any $c(S) \leq V$)?
I was thinking to reduce the 3Sat problem to mine, but I have no idea how to deal with the value $V$. Any ideas on what reductions are possible in this case?