WS-SSA : ordonnancement de workflows dans le cloud en utilisant l’algorithme de l’essaim de salpes

Pourquoi un trafic numérique plus intelligent compte

Derrière chaque carte en ligne, analyse médicale ou découverte d’ondes gravitationnelles se cache un dédale de tâches informatiques qui doivent être exécutées dans le bon ordre, sur les bonnes machines, aussi vite et aussi peu cher que possible. Dans l’informatique en nuage moderne, ces travaux sont répartis en milliers d’étapes interconnectées réparties dans des centres de données à travers le monde. Si ce trafic numérique est mal dirigé, les chercheurs attendent plus longtemps des résultats et les fournisseurs consomment plus d’électricité que nécessaire. Cet article présente une nouvelle façon d’orchestrer de tels workflows complexes, en s’inspirant d’une source surprenante : des chaînes de petits organismes marins appelés salpes.

Comment les gros travaux scientifiques sont découpés

Les grandes applications scientifiques et commerciales ne s’exécutent que rarement comme un seul programme. Elles sont décomposées en de nombreuses tâches plus petites qui dépendent les unes des autres. Les chercheurs représentent cette structure sous la forme d’un graphe orienté acyclique : les nœuds représentent les tâches et les flèches montrent quels résultats doivent être produits avant que d’autres tâches puissent commencer. Dans un centre de données cloud, ces tâches sont mappées sur des machines virtuelles — des ordinateurs logiciels qui diffèrent par leur vitesse, leur mémoire et leur capacité réseau. Le défi consiste à décider quelle tâche doit s’exécuter sur quelle machine, et quand, afin que l’ensemble du workflow se termine le plus rapidement possible tout en faisant un bon usage des ressources.

Pourquoi trouver le meilleur plan est si difficile

Choisir un ordonnancement idéal pour des milliers de tâches interdépendantes sur de nombreuses machines différentes est un exemple classique d’un problème dit NP-difficile : le nombre d’affectations possibles explose si rapidement qu’il est pratiquement impossible de toutes les vérifier. Pour cette raison, les systèmes cloud reposent sur des raccourcis intelligents, appelés heuristiques et métaheuristiques, pour rechercher des solutions bonnes — mais pas garanties optimales. Des règles traditionnelles comme premier arrivé-premier servi ou round robin sont simples mais gaspillent des ressources à grande échelle. Des approches plus avancées, incluant les algorithmes génétiques, l’optimisation par essaim de particules et l’optimisation par colonies de fourmis, recherchent de manière plus intelligente mais peuvent néanmoins rester bloquées dans des solutions médiocres, nécessiter un réglage fin des paramètres ou ignorer des dépendances importantes entre les tâches.

S’inspirer des chaînes de salpes dans l’océan

La nouvelle méthode, appelée WS-SSA, adapte l’algorithme de l’essaim de salpes aux réalités des workflows cloud. Dans la nature, les salpes se déplacent en chaînes avec un leader en tête et des suiveurs derrière, ajustant leur trajectoire en cherchant de la nourriture. WS-SSA considère chaque plan d’ordonnancement possible comme un membre de cette chaîne. Le meilleur plan connu joue le rôle de « nourriture », guidant le mouvement du leader, tandis que les suiveurs s’ajustent progressivement vers des régions prometteuses. Un choix de conception clé est que chaque position dans cet essaim artificiel encode directement quelle machine virtuelle exécute chaque tâche, en utilisant des entiers simples plutôt que des valeurs continues qui devraient ensuite être traduites. Combiné à un ordonnancement attentif des tâches respectant toujours leurs dépendances, cela garantit que chaque planning candidat considéré par l’essaim est valide et immédiatement exécutable.

Évaluer le nouvel ordonnanceur

Pour mesurer les performances de WS-SSA, les auteurs ont réalisé des simulations étendues en utilisant WorkflowSim, un ensemble d’outils qui reproduit de vrais workflows scientifiques au-dessus de l’environnement CloudSim largement utilisé. Ils ont testé cinq applications de référence issues de l’astronomie, de la sismologie, de la physique des ondes gravitationnelles et de la bioinformatique, avec des workflows allant de quelques dizaines à mille tâches et des configurations cloud allant de quelques machines virtuelles à une centaine. WS-SSA a été comparé à six règles d’ordonnancement classiques et à trois méthodes métaheuristiques modernes, dont l’algorithme d’optimisation des baleines, les algorithmes génétiques et l’optimisation par essaim de particules. Le principal indicateur était le temps total d’exécution, ou makespan, tandis que la consommation totale d’énergie des machines virtuelles a été suivie comme mesure secondaire étroitement liée.

Ce que signifient les résultats pour le temps et l’énergie

Sur cet ensemble large d’expériences, WS-SSA a systématiquement produit des ordonnancements plus rapides que les méthodes concurrentes. En moyenne, il a réduit le makespan d’environ un tiers par rapport aux heuristiques traditionnelles, et a conservé un gain de plusieurs à plus de vingt pour cent par rapport à des métaheuristiques bien établies. Parce que les temps d’inactivité et les calculs gaspillés ont également été réduits, la consommation totale d’énergie a diminué en parallèle — souvent dans des marges similaires — sans que l’algorithme n’ait à optimiser explicitement la consommation électrique. Des tests statistiques sur 30 exécutions indépendantes ont confirmé que ces améliorations n’étaient pas dues au hasard, en particulier pour les workflows plus grands et plus complexes. L’étude montre qu’une version discrète et simple de la stratégie inspirée des salpes peut naviguer de manière fiable dans l’immense espace des plannings possibles et s’adapter à différentes structures de workflow et configurations de machines.

Une science plus rapide avec des clouds plus sobres

Pour dire les choses simplement, WS-SSA est un contrôleur de trafic plus intelligent pour l’autoroute de données qui soutient la science moderne et les services cloud. En coordonnant quand et où chaque tâche s’exécute, il raccourcit le délai entre le lancement d’un travail complexe et l’obtention du résultat final, tout en réduisant la facture énergétique des centres de données sous-jacents. Ce travail ne change pas la façon dont les workflows eux-mêmes sont définis ; il offre plutôt une manière plus efficace de les exécuter sur les plateformes cloud existantes. Des extensions futures qui prendraient en compte simultanément le coût, l’énergie et les délais pourraient faire de ces ordonnanceurs inspirés par les essaims un outil important pour des infrastructures informatiques plus vertes et plus réactives.

Citation: Sharawy, A.A., Sakr, R.H., Eladrosy, W. et al. WS-SSA: workflow scheduling in cloud computing using salp swarm algorithm. Sci Rep 16, 13402 (2026). https://doi.org/10.1038/s41598-026-48037-w

Mots-clés: ordonnancement de workflows cloud, optimisation métaheuristique, algorithme de l’essaim de salpes, informatique scientifique, cloud économe en énergie