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.
Given:
- 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?
