L'ordonnancement de tâches pondérées

La programmation dynamique · niveau 2

Énoncé

Soit un ensemble de tâches définies par (début, fin, gain) : $B (0, 3, 20)$ , $C (4, 7, 20)$ , $A (0, 10, 100)$ , $D (8, 11, 20)$ . (a) Montrer que l'algorithme glouton par temps de fin croissant échoue lorsque les tâches ont des gains différents. (b) Concevoir une programmation dynamique : trier par temps de fin, déterminer pour chaque tâche $i$ sa dernière tâche compatible $p (i)$ , formuler la récurrence du gain maximal $G (i) = max (G (i - 1), g ai n_{i} + G (p (i)))$ , puis dérouler et reconstruire la solution. (c) Évaluer la complexité globale de l'algorithme.

Corrigé

(a) Le glouton par fin croissante sélectionne successivement les tâches compatibles $B$ , puis $C$ , puis $D$ , obtenant un gain cumulé de $20 + 20 + 20 = 60$ . Ce choix bloque la tâche $A$ qui offrait à elle seule un gain supérieur de $100$ . L'optimalité locale gloutonne ne fonctionne plus. (b) Classons les tâches par fin croissante : $B (0, 3, 20)$ , $C (4, 7, 20)$ , $A (0, 10, 100)$ , $D (8, 11, 20)$ . Les prédécesseurs compatibles sont : $p (B) = aucun$ , $p (C) = B$ , $p (A) = aucun$ , $p (D) = C$ . Calculons la table des gains optimaux $G$ :

$G (B) = max (0, 20 + 0) = 20$
$G (C) = max (G (B), 20 + G (p (C))) = max (20, 20 + 20) = 40$
$G (A) = max (G (C), 100 + G (p (A))) = max (40, 100 + 0) = 100$
$G (D) = max (G (A), 20 + G (p (D))) = max (100, 20 + 40) = 100$ Le gain optimal est de $100$ . Reconstruction :
$G (D) = G (A) ⟹$ la tâche $D$ n'est pas retenue.
$G (A) \neq = G (C) ⟹$ la tâche $A$ est sélectionnée. On passe à son prédécesseur $p (A) = aucun$ . La solution optimale est donc l'ensemble de tâches ${A}$ . (c) Complexité : Le tri initial prend $O (n lo g n)$ . La recherche des prédécesseurs compatibles par recherche dichotomique prend $O (n lo g n)$ . Le calcul de la table prend $O (n)$ . Le coût total est donc dominé par le tri et la dichotomie, soit $O (n lo g n)$ .

Énoncé

Corrigé

Exercices semblables