Probleme – Tâches unitaires : quels ensembles sont réalisables, et pourquoi le glouton les trouve

1. Le critère. Appelons réalisable un ensemble $A$ de tâches qu'un ordre permet de terminer toutes à l'heure. Alors <blockquote class="border-l-4 border-gray-300 pl-4 italic my-4 text-gray-600"> $A$ est réalisable si et seulement si, ses échéances étant triées par ordre croissant $e_{(1)}\le \cdots \le e_{(m)}$, on a $e_{(k)}\ge k$ pour tout $k$.

Autrement dit : la $k$-ième échéance vaut au moins $k$.

(* Vrai si l'ensemble d'échéances est réalisable. Précondition : échéances >= 1.
   Complexité : Theta(m log m), le tri. *)
let realisable echeances =
  let l = List.sort compare echeances in
  let ok = ref true and k = ref 0 in
  List.iter (fun e -> incr k; if e < !k then ok := false) l;
  !ok

2. La démonstration.

Nécessité. Dans n'importe quel ordre valide, les $k$ tâches d'échéances les plus petites occupent $k$ créneaux, dont au moins un a l'indice $\ge k$. La tâche qui l'occupe finit à l'instant $\ge k$, et son échéance est $\le e_{(k)}$ : il faut donc $e_{(k)}\ge k$.

Suffisance. Supposons $e_{(k)}\ge k$ pour tout $k$, et exécutons les tâches dans l'ordre des échéances croissantes. La $k$-ième finit à l'instant $k$, et son échéance vaut $e_{(k)}\ge k$ : elle est à l'heure. L'ordre par échéance croissante réalise donc $A$ dès que le critère est vérifié — et il n'y avait aucun autre ordre à chercher.

La vérification. Le critère a été confronté, sur $20000$ ensembles d'échéances tirés au hasard, à une force brute énumérant les $m!$ ordres : aucun désaccord. Quelques cas :

3. L'optimalité du glouton. Le problème se reformule : choisir un ensemble réalisable de pénalité totale maximale, les tâches non choisies étant reléguées à la fin et payées. Or la famille des ensembles réalisables a deux propriétés remarquables :

• elle est héréditaire : tout sous-ensemble d'un réalisable est réalisable (retirer une tâche ne fait que baisser les rangs) ;
• elle vérifie la propriété d'échange : si $A$ et $B$ sont réalisables avec $|A|<|B|$, il existe une tâche de $B\setminus A$ que l'on peut ajouter à $A$ en le gardant réalisable.

Une famille possédant ces deux propriétés s'appelle un matroïde, et c'est le théorème structurel des gloutons : sur un matroïde, le glouton par poids décroissant donne toujours l'optimum. La démonstration en est l'argument d'échange du cours, mené une fois pour toutes.

C'est ce qui explique la forme du code : on trie par pénalité décroissante, et l'on ajoute chaque tâche si l'ensemble reste réalisable. Le placement « au créneau libre le plus tardif » n'est rien d'autre qu'un test de réalisabilité déguisé — il réussit exactement quand le critère de la question 1 reste vrai.

La mesure confirme : sur $100000$ instances de quatre tâches, le glouton du cours a donné l'optimum à chaque fois, et sur l'instance de référence à sept tâches il rend $50$, ce qui est l'optimum (exercice 16.4).

Ce que le matroïde apporte. Il change la question. Au lieu de démontrer l'optimalité de ce glouton sur ce problème, on démontre que la famille des solutions partielles est un matroïde — et l'optimalité suit. Kruskal (chapitre chap:unir) est le même théorème appliqué aux forêts d'un graphe, qui forment elles aussi un matroïde. Deux gloutons, deux problèmes, une seule preuve. À l'inverse, la sélection d'activités pondérée de l'exercice 16.9 ne forme pas un matroïde : c'est pourquoi aucun glouton n'y marche.