David Glesser personal website

"We are writing this sentence two days before the deadline", c'est ainsi que commence l'article académique Scheduling Algorithms for Procrastinators de Michael A. Bender, Raphaël Clifford et Kostas Tsichlas. Cette première phrase donne immédiatement le ton : nous sommes face à un papier qui allie rigueur scientifique et humour, une tradition bien ancrée dans certains cercles de l'informatique théorique.

Publié dans le très sérieux Journal of Scheduling, cet article n'est pas qu'une simple plaisanterie académique. Derrière son ton léger se cache une contribution réelle à la théorie de l'ordonnancement (scheduling en anglais), un domaine fondamental de l'informatique qui étudie comment organiser l'exécution de tâches.

Le problème étudié dans l'article part d'une observation simple : dans de nombreuses situations réelles, notre productivité augmente à mesure que l'échéance approche. Les auteurs modélisent mathématiquement ce phénomène en considérant des tâches dont la vitesse d'exécution suit une fonction linéaire croissante du temps, partant de zéro au moment de la publication de la tâche pour atteindre son maximum juste avant la deadline.

Cette modélisation capture des phénomènes très réels. Pensez à cette présentation importante que vous préparez : vous tournez autour du pot pendant des jours, puis dans les dernières heures avant l'échéance, vous entrez dans un état de flow où votre productivité explose.

La solution proposée par les auteurs s'appelle "Latest Release Time Backwards" (LRTB). L'algorithme est contre-intuitif : au lieu de commencer par les tâches les plus urgentes, LRTB démarre à partir de la deadline la plus tardive et remonte dans le temps, priorisant les tâches par leur temps de publication le plus tardif.

L'intuition derrière cet algorithme est brillante : il pousse chaque tâche aussi près que possible de sa deadline pour maximiser la vitesse de traitement. C'est exactement ce que fait naturellement un procrastinateur expert !

Les choses se compliquent quand on passe au contexte "en ligne", où les tâches arrivent dynamiquement sans qu'on connaisse les tâches futures. Les auteurs démontrent un résultat d'impossibilité élégant : il existe des adversaires qui peuvent forcer n'importe quel algorithme en ligne à rater des deadlines. Un peu comme un prof mesquin qui vous rajouterait des devoirs pile avant le rendu d'un projet.

Loin d'être uniquement théorique, ce type de modélisation trouve des applications concrètes en informatique embarquée. Les techniques de "procrastination scheduling" sont utilisées pour l'économie d'énergie dans les processeurs. En retardant l'exécution des tâches, on peut étendre les périodes d'inactivité du processeur, permettant de le mettre en veille plus longtemps et réduire ainsi la consommation d'énergie statique (leakage).

Dans mon papier où on gère un budget énergétique au sein d'un supercalculateur, j'obtiens un résultat semblable : il vaut mieux avoir des pics d'utilisations forts pour pouvoir "rien faire" plus tard. Dans mon cas, pouvoir éteindre des parties du supercalculateur, et donc faire des économies d'énergies conséquentes.

Au-delà de l'aspect technique, cet article nous invite à repenser notre rapport à la procrastination. Dans un monde qui valorise la productivité constante et la planification rigoureuse, les auteurs suggèrent qu'il existe des contextes où la procrastination peut être non seulement acceptable, mais optimale.

Cette perspective rejoint des recherches récentes en psychologie qui distinguent la "procrastination active" (un choix délibéré de retarder pour mieux se concentrer plus tard) de la "procrastination passive" (un évitement dysfonctionnel). Les algorithmes présentés dans l'article modélisent en fait une forme de procrastination active mathématiquement optimisée.

Je suis retombé sur cet article dans mes vieilles notes, et je me suis dit qu'il valait le coup d'être partagé. Et il est aussi drôle que peut être une démonstration !

Si vous aimez vous fendre la poire très sérieusement, voici d'autres références :