Ordonnancement de workflows DAG : une étude contrôlée met en défaut un MCTS face à une méthode plus simple

Une étude récente déposée sur arXiv examine une question souvent laissée de côté dans la littérature sur l’ordonnancement de workflows en graphe acyclique dirigé (DAG) : que se passe-t-il lorsque l’on accorde exactement le même effort de recherche à une méthode sophistiquée comme le Monte Carlo Tree Search (MCTS) et à une approche beaucoup plus simple ? Les auteurs comparent trois bras dans un protocole contrôlé : un MCTS défini comme bras principal, un ordonnanceur par liste avec redémarrages aléatoires servant de contrôle, et une variante MCTS-UCT issue des formulations classiques.

Le point central de l’étude est l’égalité stricte du budget : chaque méthode construit et évalue le même nombre de plannings candidats. Au budget principal de 2 048 plannings évalués, le MCTS principal obtient des résultats 2,88 % inférieurs à ceux de la méthode par redémarrages aléatoires, avec un intervalle de confiance à 95 % allant de -3,62 % à -2,15 %. Les auteurs indiquent aussi qu’un contrôle indépendant a validé l’ensemble des 768 plannings de la phase de confirmation.

L’article suggère que cet écart ne s’explique pas simplement par un manque de budget. Dans un ensemble séparé dédié à l’exploration, la méthode par redémarrages continue de s’améliorer davantage que le MCTS. Les auteurs avancent qu’une règle de sélection étudiée dans l’arbre conduit le MCTS à se verrouiller de manière déterministe sur le premier enfant exploré, ce qui limiterait la diversité effective des essais. Ils précisent toutefois que le lien causal exact avec le makespan reste une inférence.

Les résultats varient selon la structure des workflows : les redémarrages aléatoires dominent sur des graphes clairsemés et irréguliers, aucune différence nette n’est détectée sur des graphes plus réguliers en couches, et les graphes denses offriraient peu de marge d’amélioration. En remplaçant la règle de sélection par une version UCT plus standard, l’écart devient faible (-0,26 %, IC 95 % [-0,71 % ; +0,23 %]), sans basculer en faveur du MCTS. Les auteurs rappellent enfin que ces conclusions restent limitées à un domaine synthétique contrôlé, avec 8 à 32 tâches, 2 à 8 processeurs et des budgets allant jusqu’à 2 048 évaluations.