What is the best Approximation algorithm to schedule a task graph? If I have a task graph T and want a schedule to optimize the make-span, what is currently the best approximation algorithm for this problem? Are there any constant approximation algorithms?
You get a $2-\frac1m$-approximation (where $m$ is the number of machines), by greedily scheduling tasks as they become available, and this is essentially the best we can do at the moment. Improving this is actually a major open problem in scheduling (see e.g. this ).