A new, tighter tardiness bound has been found for global Earliest-Deadline-First scheduling of jobs on symmetric multiprocessors. But this bound seems to be particularly hard to compute. In particular, we were not able either to find a polynomial-time algorithm to compute this bound, or to prove that the problem is NP-hard. In this respect, a sufficient condition for the problem to be NP-hard, is that the following sub-problem is NP-complete.


  • a set $\tau$ of $N$ pairs $(C_i, U_i) \in \mathbb{Q}^2$, with $C_i > 0$ and $0 < U_i \le 1$ for all $i \in \{1, 2, \ldots, N\}$,
  • the smallest natural number $M$ such that $\sum_{i=1}^{N} U_i \le M$ (which implies $M \le N$, because $U_i \le 1$),
  • an integer $M'$ with $1 \le M' \le M$,
  • a strictly positive value $b \in \mathbb{Q}$;

does a permutation $\tau' = ( (C_{i_1},U_{i_1}), (C_{i_2},U_{i_2}), \ldots, (C_{i_{M'-1}}, U_{i_{M'-1}}))$ of $M' - 1$ pairs in $\tau$ exist, such that $$ \sum_{g = 1}^{M'-1}\frac{C_{i_g}}{M - \sum_{v=1}^{g-1}U_{i_v}} \ge b \quad ? $$

Any suggestion for proving that this is problem is NP-hard, or, on the other hand, for finding a way to solve the problem in polynomial time?

  • 2
    $\begingroup$ Simultaneously cross-posted at mathoverflow.net/q/216142 $\endgroup$ Sep 1, 2015 at 14:39
  • $\begingroup$ @EmilJeřábek Actually, I posted this question on Math Stackexchange first. After that, Mike Haskell kindly suggested me to post it also on cstheory and math overflow, to have more chances to get a good answer. But, most certainly, I had to wait for a few days between each cross-post. I am sorry for not waiting. If it is better to remove the question for now, I will do it. $\endgroup$ Sep 2, 2015 at 7:57
  • $\begingroup$ Since it's already posted, it's probably better to leave it as is, but please keep the rule in mind for future. Also, if you crosspost under any circumstances, mention it in the question and include links in both directions. $\endgroup$ Sep 2, 2015 at 10:29
  • $\begingroup$ Please do not post the same question on multiple sites. Cross-posting violates site rules. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration. $\endgroup$
    – D.W.
    Sep 3, 2015 at 17:30
  • 1
    $\begingroup$ @D.W. I have removed the other copies, so this is now the only remaining copy. I apologize again for the mistake. $\endgroup$ Sep 4, 2015 at 13:42


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.