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?

  • $\begingroup$ @Apass.Jack Please post the link if you find it. I am quite curious about the answer. $\endgroup$ – Optidad Apr 4 '19 at 15:24
  • $\begingroup$ @Vince, I was referring to your answer, which describes an algorithm that shows how to complete the tasks as soon as possible, by making sure of maximum parallelism. The questions are not the same, although a slight modification of your algorithm will yield the shortest response time as well. $\endgroup$ – John L. Apr 4 '19 at 15:33
  • $\begingroup$ @Vince A closer look at this question tells me the two questions are very different since this question restricts the number of available threads to $x$. (All of my comments will be deleted.) $\endgroup$ – John L. Apr 4 '19 at 15:36
  • $\begingroup$ This seems like a variant of Job shop scheduling. My suspicion is that this may be NP-complete. See also this for your variant. $\endgroup$ – ryan Apr 4 '19 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.

  • $\begingroup$ It is a nice upper bound that can be applied on sub-problems to be refined. $\endgroup$ – Optidad Apr 5 '19 at 8:24
  • $\begingroup$ @Pontus Do you have a source for this upper bound? $\endgroup$ – Mike van Dyke Apr 8 '19 at 11:28
  • $\begingroup$ @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. $\endgroup$ – Pontus Apr 9 '19 at 18:12
  • $\begingroup$ In case someone is interested, I found a source on this upper bound $\endgroup$ – Mike van Dyke Sep 27 '19 at 11:29
  • 1
    $\begingroup$ Thanks, @MikevanDyke. I would think that this was known long before 2004, though. $\endgroup$ – Pontus Sep 28 '19 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.