title: How to parallelize a Task Graph which has precedence constraints and resource constraints in order to obtain minimum makespan?
body: <p>I have a Task Graph which is a DAG (Directed Acyclic Graph). Each node in the graph is a task and the edges in the graph are its dependencies/precedence constraints. This is shown in the image attached. Each task (i.e 1, 2, 3, 4, 5) is associated with a particular type of resource. There are 2 types of resources - A, B. The count of these resources can vary. For now, lets assume we have 1 resource of type A, and 1 resource of type B. A resource can execute only 1 task at a time and the tasks are non-preemptive. Resource A and B can be executed in parallel. The time taken to execute each task is also given in the graph. What is the best way to reorder the DAG such that the tasks can be executed in parallel (to obtain minimum makespan) without violating their precedence constraints?
  Is the problem NP-complete? Are there scheduling algorithms/ heuristics algorithms available for such scenarios?</p>
  
  <p><a href="https://i.stack.imgur.com/7Npl2.png" rel="nofollow noreferrer">DAG with precedence and resource contraints</a></p>