Scribd
Importer
81 vues13 pages

TP Optimisation

Le document traite du problème d'ordonnancement d'atelier (JSSP), un problème d'optimisation combinatoire visant à minimiser le makespan lors de la planification de tâches sur des machines. Il présente les données, contraintes, objectifs d'optimisation et divers algorithmes métaheuristiques utilisés pour résoudre ce problème. Des expérimentations et des comparaisons d'algorithmes sont également discutées, illustrées par des diagrammes de Gantt.

Transféré par

TOGBE Mismadji sosthène
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
81 vues13 pages

TP Optimisation

Le document traite du problème d'ordonnancement d'atelier (JSSP), un problème d'optimisation combinatoire visant à minimiser le makespan lors de la planification de tâches sur des machines. Il présente les données, contraintes, objectifs d'optimisation et divers algorithmes métaheuristiques utilisés pour résoudre ce problème. Des expérimentations et des comparaisons d'algorithmes sont également discutées, illustrées par des diagrammes de Gantt.

Transféré par

TOGBE Mismadji sosthène
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Problème d’Ordonnancement d’Atelier (JSSP)

UE : Techniques d’optimisation

GROUPE 6

March 8, 2025

GROUPE 6 Problème d’Ordonnancement d’Atelier (JSSP) March 8, 2025 1 / 13


Plan

1 Introduction

2 Modélisation du Problème

3 Expérimentation

4 Conclusion

GROUPE 6 Problème d’Ordonnancement d’Atelier (JSSP) March 8, 2025 2 / 13


Définition et Importance

Job Shop Scheduling Problem (JSSP) : problème d’optimisation


combinatoire visant à planifier un ensemble de tâches sur des machines
pour minimiser le makespan.

Applications :
Industrie manufacturière
Logistique et transport
Allocation des ressources en informatique

GROUPE 6 Problème d’Ordonnancement d’Atelier (JSSP) March 8, 2025 3 / 13


Données et Contraintes

Données :
J : Ensemble des tâches
M : Ensemble des machines
Pij : Temps de traitement de la tâche i sur la machine j
Contraintes :
Ordre strict des opérations
Une machine ne peut traiter qu’une seule tâche à un instant donné
Pas d’interruption des tâches

GROUPE 6 Problème d’Ordonnancement d’Atelier (JSSP) March 8, 2025 4 / 13


Objectif d’Optimisation

Minimiser le makespan :

Cmax = max(Sij + Pij )

où :
Sij : Début de la tâche i sur la machine j
Pij : Durée de la tâche i sur la machine j

GROUPE 6 Problème d’Ordonnancement d’Atelier (JSSP) March 8, 2025 5 / 13


Algorithmes Métaheuristiques

Algorithme génétique (GA) : utilise la sélection, le croisement et la


mutation pour optimiser les itinéraires.
Recuit simulé (SA) : explore de meilleures solutions en acceptant des
solutions probabilistes pires pour échapper aux minima locaux.
Optimisation de la colonie de fourmis (ACO) : imite le comportement
de recherche de nourriture des fourmis pour trouver des itinéraires
efficaces.
Recherche taboue (TS) : utilise une approche basée sur la mémoire
pour éviter de revisiter les mêmes itinéraires.
Optimisation par essaim de particules (PSO) : utilise une approche
basée sur l’essaim pour rechercher les meilleures solutions de routage.

GROUPE 6 Problème d’Ordonnancement d’Atelier (JSSP) March 8, 2025 6 / 13


Présenation du Dataset

Figure: Dataset

GROUPE 6 Problème d’Ordonnancement d’Atelier (JSSP) March 8, 2025 7 / 13


Diagramme de Gantt

Figure: Diagramme non optimisé

GROUPE 6 Problème d’Ordonnancement d’Atelier (JSSP) March 8, 2025 8 / 13


Implementation

1 Initialiser un ensemble aléatoire de routes.


2 Évaluer la distance totale et les contraintes de capacité.
3 Appliquer un algorithme métaheuristique pour améliorer la solution de
manière itérative.
4 Arrêter lorsque la solution converge vers une valeur quasi-optimale

GROUPE 6 Problème d’Ordonnancement d’Atelier (JSSP) March 8, 2025 9 / 13


Diagramme de Gantt

Figure: Diagramme optimisé

GROUPE 6 Problème d’Ordonnancement d’Atelier (JSSP) March 8, 2025 10 / 13


Comparaison des Algorithmes

Figure: Comparaison

GROUPE 6 Problème d’Ordonnancement d’Atelier (JSSP) March 8, 2025 11 / 13


Synthèse

Figure: Makespan des Algorithmes

GROUPE 6 Problème d’Ordonnancement d’Atelier (JSSP) March 8, 2025 12 / 13


Merci pour votre attention !

GROUPE 6 Problème d’Ordonnancement d’Atelier (JSSP) March 8, 2025 13 / 13

Vous aimerez peut-être aussi