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}$.

• Please don't cross-post. It's against site policy because it fragments answers and wastes people's time when they work on a question that's already been answered somewhere else. – David Richerby Dec 9 '14 at 7:23
• What have you tried and where did you get stuck? What kind of reading did you do? Scheduling is a broad field with lots of literature. – Raphael Dec 9 '14 at 13:15
• I found only that this problem is called DAG Layering Assignment, but usually they try to minimize number of crossings or number of dummy vertices. I've read a lot of articles, but haven't found anything that correspond to my problem. – John Goldman Dec 10 '14 at 10:27
• @John Goldman Posting link to the articles you read will be very nice. Btw, in your 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. – InformedA Dec 10 '14 at 19:16

These kinds of problems are usually studied under the banner of Operations Research or Operational Research, and this is still an active area after several decades. See the Graham et al. survey from 1979 (doi:10.1016/S0167-5060(08)70356-X) for the standard terminology and many older references. It looks like your problem is $P|\text{prec},p_{ij}=1|\sum_j C_{ij}$ which seems too general to have been studied back then.