Ordonnancement de tâches pondérées

Pourquoi le glouton échoue. Le chapitre chap:gloutons traite la sélection d'activités : maximiser le nombre de tâches, en prenant toujours celle qui finit le plus tôt. Avec des poids, cette règle n'a plus aucune raison d'être optimale — une tâche longue et lourde peut valoir mieux que trois courtes et légères. Le glouton perd sa preuve d'échange, et il perd le résultat avec.

La formulation dynamique. On trie les tâches par date de fin croissante. Pour la tâche $j$, on note $p(j)$ l'indice de la dernière tâche compatible avec elle (celle de plus grande date de fin $\le$ début de $j$), ou $0$ s'il n'y en a aucune. Alors, avec $M[j]$ le poids optimal des $j$ premières tâches :

$$M[0]=0,M[j]=\max (\underset{\text{on eˊcarte }j}{\underbrace{M[j-1]}},\underset{\text{on prend }j}{\underbrace{w_j+M[p(j)]}}).$$

C'est la structure du sac à dos : prendre ou ne pas prendre, et la sous-structure optimale vient de ce que le reste d'une solution optimale contenant $j$ est une solution optimale sur les tâches compatibles avec $j$.

Mesure sur huit tâches, déjà triées par date de fin :

j     1        2        3        4        5        6        7        8
tache (1,4,3)  (3,5,4)  (0,6,5)  (4,7,6)  (3,8,2)  (5,9,7)  (6,10,1) (8,11,4)
p(j)  0        0        0        1        0        2        3        5
M[j]  3        4        5        9        9       11       11       13

L'optimum est $M[8]=13$, atteint par les tâches $(1,4,3)$, $(4,7,6)$ et $(8,11,4)$. Une énumération exhaustive des $2^8$ sous-ensembles confirme la valeur $13$ et la même sélection.

Complexité. Le tri coûte $\Theta (n\log n)$. Le calcul des $p(j)$ se fait par recherche dichotomique dans le tableau des dates de fin, $\Theta (n\log n)$ également (chapitre chap:sequentielles). Le remplissage est $\Theta (n)$. Total : $\Theta (n\log n)$ — et c'est ici la seule fois du chapitre où le coût dominant n'est pas celui de la table.