Optimisation Métaheuristique :
Workflow Scheduling

L’objectif était d’optimiser l’ordonnancement d’un workflow complexe en environnement IoT / Edge / Fog / Cloud, en minimisant simultanément le temps d’exécution, la consommation énergétique et la latence.

De la modélisation mathématique à la création d’un simulateur dédié, en passant par l’implémentation et l’hybridation de métaheuristiques innovantes, ce projet a été une véritable immersion dans l’optimisation multi-objectif et la recherche algorithmique.

En travaillant en équipe, nous avons conçu, expérimenté et analysé nos propres solutions, dans une démarche proche de celle d’un travail scientifique, alliant rigueur technique, programmation avancée et réflexion stratégique.

outils utilisés

Langage Python

Python

Simulateur, modélisation et algorithmes d’optimisation

logo Visual Studio Code

Visual Studio Code

Environnement de développement

Logo prism

Prism (anciennement Crixet)

Rédaction collaborative du rapport LaTeX

Projet réalisé pour

logo Cy Tech

École d’ingénieur informatique CY Tech

Notre article scientifique

Pour découvrir ce projet en profondeur, avec la formulation mathématique complète, les choix méthodologiques, les résultats expérimentaux détaillés, les graphiques des fronts de Pareto et l’analyse comparative des algorithmes… consultez notre rapport scientifique complet.

Toutes les données, figures et explications techniques y sont présentées avec rigueur et précision.

Image rapport workflow scheduling
Accéder au rapport complet

Naissance du projet

Dans le cadre du module d’Optimisation Métaheuristique en ING3 (spécialité IA), nous avons travaillé en groupe de quatre sur un problème complexe : l’optimisation du workflow scheduling dans une architecture IoT / Edge / Fog / Cloud.

L’objectif était de minimiser simultanément trois critères :

    • le makespan (temps total d’exécution)

    • la consommation énergétique

    • la latence de communication

Un vrai problème multi-objectif, combinatoire, et surtout NP-difficile. C’est un réel défi que l’on va surmonter avec chaque membre de l’équipe.

Comprendre le problème

Le contexte étudié est inspiré d’un article scientifique sur l’optimisation de workflows agricoles en environnement Fog-Cloud.

Un workflow est composé de tâches interdépendantes (DAG) qui doivent être réparties sur différentes machines hétérogènes.

Chaque décision d’affectation influence :

    • le temps d’exécution

    • l’énergie consommée

    • les délais de transmission des données

Optimiser un critère dégrade souvent un autre. Le but n’est donc pas de trouver une solution parfaite, mais un front de Pareto proposant plusieurs compromis pertinents.

Création de notre propre simulateur

Plutôt que d’utiliser un outil existant comme FogWorkflowSim (en Java), nous avons fait un choix ambitieux : développer notre propre simulateur en Python.

Pourquoi ?

    • meilleure maîtrise du modèle

    • reproductibilité des expériences

    • compréhension fine des métriques

    • flexibilité dans les modifications

Le simulateur est structuré en modules :

    • modélisation des tâches et machines

    • moteur d’évaluation (makespan, énergie, latence)

    • implémentation des métaheuristiques

    • visualisation des fronts de Pareto

Nous avons utilisé les workflows Montage (jusqu’à 100 tâches) comme base expérimentale.

Les algorithmes testés

Nous avons comparé trois approches :

    1. Random Search (baseline)

    2. Dragonfly Algorithm

    3. FA-RL : une hybridation originale entre Firefly Algorithm et Q-Learning

L’idée derrière FA-RL était d’ajuster dynamiquement l’équilibre exploration/exploitation grâce à l’apprentissage par renforcement.

Concrètement, l’algorithme apprend quand :

    • explorer davantage

    • exploiter une bonne région

    • maintenir un équilibre

Une approche hybride que nous avons adaptée au problème discret du scheduling.

Protocole expérimental

Pour garantir une comparaison équitable, chaque algorithme effectue environ 10 000 évaluations.

Les métriques analysées :

    • meilleur makespan

    • meilleure énergie

    • meilleure latence

    • taille du front de Pareto

    • hypervolume

    • spacing

Résultats obtenus

Les résultats montrent clairement que les métaheuristiques surpassent largement la recherche aléatoire.

    • FA-RL obtient le meilleur makespan : 574.1 s

    • Dragonfly domine sur l’énergie (113.5 J) et la latence (5518.6 s)

    • Dragonfly génère également le front de Pareto le plus large (120 solutions)

En termes d’hypervolume et de diversité, Dragonfly se montre globalement supérieur.

FA-RL, en revanche, excelle lorsqu’on priorise la réduction du temps d’exécution.

Conclusion

Ce projet nous a permis de :

    • formuler mathématiquement un problème multi-objectif

    • développer un simulateur complet

    • adapter des métaheuristiques continues à un problème discret

    • analyser la qualité d’un front de Pareto

Au-delà des résultats, ce travail nous a plongés dans une vraie démarche de recherche :

    • lecture et reproduction d’un article scientifique

    • validation expérimentale

    • analyse critique des performances

    • identification des limites et perspectives

Un projet exigeant, technique, mais particulièrement formateur, qui nous a confrontés aux réalités de l’optimisation multi-objectif en environnement distribué.