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?
Is this permutation-sum problem NP-complete?
np hardness;time complexity;np complete