task scheduling optimization problem

Question

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

• David Richerby: 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.
• Raphael: 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.
• John Goldman: 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.
• InformedA: @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.

Answer 1

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.

You don't describe the kinds of task graphs you work with, but in my experience many practical task graphs from computer science lead to an explosion of chains of tasks to consider, making it hard to do dynamic programming, while task graphs from other fields often are more amenable to dynamic programming. When the structure of the task graph is "nice", then one can do better. For instance, series-parallel task graphs often lead to polynomial-time algorithms.

Without knowing more about the details of your problem, I'd say it sounds NP-hard on general task graphs due to the costs, but it may well be possible to exploit special features of the task graphs (or perhaps the costs) to design an efficient algorithm.