Pourquoi « au plus tard » et non « au plus tôt »

On compare trois quantités sur la même instance : la pénalité du glouton du cours, celle de sa variante « au plus tôt », et l'optimum — ce dernier obtenu en énumérant les $2^n$ sous-ensembles de tâches et en retenant le meilleur qui soit réalisable (voir problème 16.2).

Sur l'instance à sept tâches $(e,p)=(4,70),(2,60),(4,50),(3,40),(1,30),(4,20),(6,10)$ :

Le contre-exemple minimal, à quatre tâches : $(4,17),(1,3),(4,16),(3,19)$.

• Triées par pénalité décroissante : $(3,19),(4,17),(4,16),(1,3)$.
• Au plus tard : $19$ va au créneau $3$ ; $17$ au créneau $4$ ; $16$ au $2$ ; $3$ au $1$. Tout le monde est à l'heure, pénalité 0.
• Au plus tôt : $19$ va au créneau $1$ ; $17$ au $2$ ; $16$ au $3$ ; et $(1,3)$ n'a plus que le créneau $1$, occupé. Pénalité 3.

La tâche de pénalité $19$, dont l'échéance était $3$, a pris le créneau $1$ — un créneau dont elle n'avait aucun besoin, et dont la tâche d'échéance $1$ ne pouvait pas se passer.

La mesure systématique. Sur $100000$ instances de quatre tâches tirées au hasard :

• le glouton du cours a donné l'optimum à chaque fois ;
• la variante « au plus tôt » s'est trompée $66150$ fois, soit $66,2\%$ des instances.

Le principe, et il vaut au-delà de cet exercice. Un créneau tardif est une ressource peu demandée : seules les tâches à échéance lâche peuvent l'occuper. Un créneau précoce est une ressource rare : toutes les tâches y ont droit, et les tâches à échéance serrée n'ont que lui. Le glouton doit donc consommer d'abord ce qui est abondant. C'est le même raisonnement qu'à l'exercice 16.2 : choisir de manière à laisser le plus de possibilités, et non de manière à s'avantager sur le moment.