I'm interested in such problem. I have a set of $n$ tasks ${T_i}$ and directed acyclic graph, which nodes correspond to tasks and edges correspond to order of execution two tasks. In other words if I have edge $T_i \rightarrow T_j$ it means that task $T_i$ should be executed in day which strictly before day of execution $T_j$. All tasks should be executed within $m$ days, every task should be executed exactly once. Execution of task $T_i$ in day $j$ costs $C_{ij}$ dollars. There is no restriction on number of tasks executed in one day. I should minimize total cost of execution all tasks.
Can one solve this problem in polynomial time?
My idea is only to bruteforce topological sorting and dynamic programming then, but it is too slow.
ADD: I can solve problem, when given DAG is forest. It can be done by simple dynamic programming, where states are $(T_i, j)$, which means that $T_i$ is executed in day $j$ and subtree tasks are executed within constraints.
ADD: I've read this paper, 13.3 Layer Assignment, p. 417. Also this problem can be formulated in terms of weighted CSP, we need to minimize such value $\sum\limits_{v \in V}C_{v \sigma(v)} + \sum\limits_{(u,v) \in E} D_{\sigma(u)\sigma(v)}$, where $\sigma(v)$ is day when task $T_v$ is executed, $D_{ij} = \begin{cases} 0 &\mbox{if } i < j \\ \infty & \mbox{if } i \ge j \end{cases}$.
ADD
, I don't think it is good. The sub-problems for different vertices can yield solutions in which a task might be executed in more than one day. I think this is what you meant by crossing and dummy vertices. $\endgroup$ – InformedA Dec 10 '14 at 19:16