Exercice 8 - Ordonnancement

1. Montrez que SCHEDULING $\in$ NP.
2. Etant donné le problème PARTITION :
   • Données : Un ensemble de $m$ valeurs $\{v_1, \ldots, v_m\}$.
   • Question : Existe-t-il un sous-ensemble $I$ de $\{1, \ldots, m\}$ tel que $$\sum_{i \in I}v_i = \sum_{i \not \in I}v_i$$
   Autrement dit, est-il possible de partitionner l'ensemble $\{v_1, \ldots, v_m\}$ en deux sous-ensembles dont la somme des valeurs est égale ? L'instance de PARTITION suivante, $m = 7$, $(v_1, \ldots, v_7) = (1, 2, 3, 4, 5, 6, 7)$ est-elle à réponse "oui" ? Vous démontrerez la justesse de votre réponse.
3. Nous savons que PARTITION est NP-Complet. Nous allons montrer à l'aide d'une réduction polynomiale $f$, que PARTITION $\leq$ SCHEDULING. Nous construisons une fonction $f$ qui à toute instance de PARTITION associe une instance de SCHEDULING définie comme suit :
   • $n = m + 1$
   • pour tout $i \in \{1, \ldots, m\}$, $d_i = v_i$, $r_i = 1$, $f_i = \sum_{j = 1}^n v_j + 1$
   • $d_n = 1$, $r_n = \frac{1}{2}\sum_{j = 1}^n v_j + 1$, $f_n = \frac{1}{2}\sum_{j = 1}^n v_j + 1$
   • $M = 0$
   Déterminer l'image de l'instance $(1, 2, 3, 4, 5, 6, 7)$ par la fonction $f$. Vous présenterez votre solution sous forme d'un tableau, vous préciserez les valeurs de toutes les données du problème.
4. L'image de cette instance est-elle à réponse "oui" ? Vous démontrerez la justesse de votre réponse en donnant les valeurs de début d'exécution si c'est le cas, ou bien une preuve d'impossibilité dans le cas contraire.
5. Montrez, sans excès de formalisme, que $f$ est polynomiale.
6. Montrer que toute instance de PARTITION à réponse oui a une image par $f$ à réponse oui.
7. Montrer que toute instance de PARTITION dont l'image est à réponse oui est à réponse oui.
8. SCHEDULING est-il NP-Complet ? Justifiez votre réponse.