# Response time of scheduling a DAG where each vertex is a task

Suppose I have a directed acyclic graph where each vertex $$v$$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $$v_i$$ has to execute before task $$v_j$$ if there exists an edge $$(v_i,v_j)$$ between those two tasks. I have $$x$$ threads that can execute those tasks.

Is there a (simple) formula to determine the response time (or at least an upper bound) for the given setup using any work-conserving scheduler?

• @Apass.Jack Please post the link if you find it. I am quite curious about the answer. Commented Apr 4, 2019 at 15:24
• This seems like a variant of Job shop scheduling. My suspicion is that this may be NP-complete. See also this for your variant.
– ryan
Commented Apr 4, 2019 at 18:00

Found it! This problem is NP-complete when the goal is to minimize total execution time.

The scheduling problem (P1) is the following. We are given

(1) a set $$S = \{J_1 , \ldots , J_n\}$$ of jobs,

(2) a partial order $$\prec$$ on $$S$$,

(3) a weighting function $$W$$ from $$S$$ to the positive integers, giving the number of time units required by each job, and

(4) a number of processors, $$k$$.

Please see the following paper, which immediately discusses it from the introduction onward:

J.D. Ullman. Np-complete scheduling problems. Journal of Computer andSystem Sciences, 10(3):384 – 393, 1975.

There are a few other cases that may be of interest that are discussed in the paper:

• When $$\prec$$ is empty (no edges in the DAG)
• (P2) When $$W(J_i) = 1$$ for all $$i$$.
• (P3) When $$k = 2$$ and $$W(J_i) \in \{1, 2\}$$ for all $$i$$.

You can show 3-SAT reduces to (P2) through and intermediate problem (P4) that Ullman discusses. Then it is clear that (P2) reduces to (P1).

A simple upper bound on the response time, for any work-conserving scheduler, is $$\frac{\mathit{vol} - L}{x} + L,$$ where $$\mathit{vol}$$ is the sum of all the execution times and $$L$$ is the sum of the execution times along a critical path in the DAG.

• It is a nice upper bound that can be applied on sub-problems to be refined. Commented Apr 5, 2019 at 8:24
• @Pontus Do you have a source for this upper bound? Commented Apr 8, 2019 at 11:28
• @MikevanDyke: Sorry, I'm not sure what the original source is. It is easy enough to prove though. The key observation to make is that whenever any machine/thread is idle, all maximal paths in the DAG must be shortened. So at all times we either get to exploit full parallelism, or we get to shorten the critical paths. In practice it can of course happen that we do both at the same time, which is why this is an upper bound. Commented Apr 9, 2019 at 18:12
• In case someone is interested, I found a source on this upper bound Commented Sep 27, 2019 at 11:29
• Thanks, @MikevanDyke. I would think that this was known long before 2004, though. Commented Sep 28, 2019 at 15:13