C++ Algorithme Problème Population Générations
Implémentation d'un algorithme génétique (GA) en C++ pour résoudre le problème d'ordonnancement Flow Shop Scheduling — minimisation du makespan (Cmax) sur instances Taillard.
Réalisé dans le cadre du cours 8INF309 — Stage-projet I — UQAC, Automne 2025.
Le problème Flow Shop consiste à ordonnancer n tâches sur m machines avec les contraintes suivantes :
- Chaque tâche doit passer par toutes les machines dans le même ordre
- Une machine ne peut traiter qu'une seule tâche à la fois
- L'objectif est de minimiser le makespan (Cmax) — temps total de complétion
Tâches : T0 T1 T2 T3 T4
↓ ↓ ↓ ↓ ↓
M1 : [████][ ][███][ ][████]
M2 : [███][ ][██][ ][███]
M3 : [████][ ][███][ ]
↑ Cmax (makespan)
Chaque individu est une permutation des tâches :
Exemple : [ 3, 1, 4, 0, 2 ]
→ Exécuter d'abord T3, puis T1, puis T4, etc.
Population initiale (aléatoire)
↓
Évaluation fitness (1 / makespan)
↓
Tri par fitness décroissante
↓
Sélection des 50% meilleurs
↓
Croisement (crossover)
↓
Réparation des permutations invalides
↓
Nouvelle population
↓
Répéter sur N générations
Croisement — échange de gènes à partir d'un point de coupure aléatoire entre deux parents, suivi d'une réparation pour garantir une permutation valide.
Réparation — détection et remplacement des tâches dupliquées par les tâches manquantes, assurant la validité de chaque individu.
Mutation — échange de deux tâches aléatoires dans la séquence (taux configurable, désactivée par défaut).
| Classe / Fonction | Rôle |
|---|---|
Individual |
Représente une solution — permutation + calcul de fitness |
GeneticAlgorithm |
Gère la population, la sélection, le croisement et l'évolution |
readInstance() |
Lecture du fichier d'instance Taillard |
crossover() |
Croisement à point unique entre deux parents |
repair() |
Correction des permutations invalides après croisement |
mutate() |
Mutation par échange de deux gènes |
flowshop_GA/
├── Source.cpp # Code source complet
├── tai1.txt # Instance Taillard (500 tâches ×ばつ 20 machines)
├── README.md
└── documents/
└── rapport.pdf # Rapport complet du projet
Instance : tai1.txt — 500 tâches ×ばつ 20 machines (benchmark Taillard)
Paramètres :
| Paramètre | Valeur |
|---|---|
| Taille de population | 10 000 individus |
| Nombre de générations | 100 |
| Taux de mutation | 0.1 (désactivée) |
| Sélection | Top 50% |
Le programme affiche à chaque génération :
- Le meilleur makespan trouvé
- La meilleure permutation de tâches
- Le temps d'exécution total en millisecondes
# Linux / macOS g++ -O2 -std=c++17 -o flowshop Source.cpp # Windows (MinGW) g++ -O2 -std=c++17 -o flowshop.exe Source.cpp
# Placez tai1.txt dans le même dossier que l'exécutable
./flowshopGeneration 0: Best fitness = 32450
Best permutation: 3 1 4 0 2 ...
Generation 1: Best fitness = 31980
Best permutation: 1 3 0 4 2 ...
...
Generation 99: Best fitness = 28710
Best permutation: 0 2 4 1 3 ...
Temps d'exécution : 4521.32 ms
Les instances suivent le format Taillard :
n m
t[0][0] t[1][0] ... t[n-1][0] ← Machine 0
t[0][1] t[1][1] ... t[n-1][1] ← Machine 1
...
Où n = nombre de tâches et m = nombre de machines.
Le rapport détaillé du projet (analyse, résultats, comparaisons) est disponible ici :
Salifou Diallo
Étudiant en informatique — UQAC
Superviseur : Jimmy Girard-Nault
LinkedIn
GitHub