Consider a set of processes ($P=\{p_1, p_2,\dots, p_n \}$) and their data dependencies. Each process $p_i$ has an execution runtime which is denoted by $d_i$. We are interested to parallelize these processes on $k$ processors. Note that if process $p_i$ depends on process $p_j$ (which is denoted by $p_j \rightarrow p_i$), it cannot be executed until $p_j$ is finished so it can provide the necessary data that $p_i$ requires. Moreover, if processes $p_i$ and $p_j$ are assigned to different processors and $p_i \rightarrow p_j$, there is a delay associated for moving data from one processor to another. On the other hand, if processes $p_i$ and $p_j$ are assigned to one processor $p_i \rightarrow p_j$, the data can be provided to $p_i$ in zero time.
Now we want to divide these processes into $k$ partitions such that the overall execution time of them (i.e., their makespan) are minimized.
Please note that this problem is different from the standard graph partitioning problem since we are dealing with a DAG rather than an undirected graph. "Graph partitioning models for parallel computing" by Hendrickson and Kolda has pointed to the aforesaid problem but does not provide any solution to it.
