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

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.