La complexité algorithmique

Table des matières

I Ordonnancement de la production, optimisation et état de l’art
1 Ordonnancement de production 
1.1 La gestion de production
1.1.1 Décisions stratégiques
1.1.2 Décisions tactiques
1.1.3 Décisions opérationnelles
1.2 L’ordonnancement de la production
1.2.1 Formulation d’un problème d’ordonnancement
1.2.1.1 Les tâches
1.2.1.2 Les ressources
1.2.1.3 Les contraintes
1.2.1.4 Les objectifs
1.2.2 Typologie des problèmes d’ordonnancements
1.2.2.1 Problèmes à une opération
1.2.2.2 Problèmes à plus d’une opération
1.2.3 Formalisation des problèmes d’ordonnancements
1.2.3.1 Classification et notation
1.2.3.2 Modélisation
1.2.3.3 Représentation des solutions
1.3 La théorie de la complexité
1.3.1 Complexité algorithmique
1.3.2 Complexité problématique
1.3.3 Hiérarchie de complexité pour les problèmes d’ordonnancement
1.4 Conclusion
2 Techniques d’optimisation
2.1 Méthodes exactes
2.1.1 Méthode de séparation et évaluation
2.1.2 Programmation dynamique
2.1.3 Programmation linéaire
2.2 Méthodes approchées
2.2.1 Heuristiques
2.2.2 Metaheuristiques
2.2.2.1 Métaheuristiques à solution unique
2.2.2.2 Métaheuristiques à base de population
2.3 Méthodes hybrides
2.4 Conclusion
3 Revue de la littérature 
3.1 État de l’art sur les problèmes d’ordonnancement sous contraintes de ressources non-renouvelables
3.2 Identification de problème et objectif de la thèse
3.3 Conclusion
II Le Flow-Shop sous contraintes de resources non-renouvelables : Modélisation mathématique et méthodes de résolution 
4 Méthode de résolution exacte 
4.1 Le Flow-Shop sous contraintes de ressources non-renouvelables
4.1.1 Description du problème
4.1.2 Une instance de problème
4.1.3 Complexité de problème
4.2 Modèle mathématique
4.2.1 Paramètres et indices
4.2.2 Variables
4.2.3 Modèle
4.2.4 Signification des équations
4.3 Benchmarks
4.4 Résultats numériques
4.5 Conclusion
5 Algorithme génétique pour le problème Flow-Shop sous contraintes de ressources non-renouvelables
5.1 Introduction
5.2 Algorithme Génétique (AG)
5.2.1 Codage utilisé
5.2.2 Génération de la population initiale
5.2.2.1 Les heuristiques constructives utilisées
5.2.3 Évaluation de la solution
5.2.4 Opérateur de sélection
5.2.5 Opérateur de croisement
5.2.6 Opérateur de mutation
5.2.7 La stratégie de remplacement
5.2.8 Mécanisme d’arrêt
5.3 Recherche locale
5.4 Paramétrage de l’algorithme génétique proposé
5.4.1 Taille de population
5.4.2 Probabilité de croisement
5.4.3 Probabilité de mutation
5.4.4 Application de la méthode de Taguchi
5.5 Résultats expérimentaux
5.5.1 Résultats de calcul pour les problèmes de petites tailles
5.5.2 Résultats de calcul pour les problèmes de moyennes à grandes tailles
5.6 Conclusion
6 Algorithme d’optimisation par essaims particulaires pour le Flow-Shop sous contraintes de ressources non-renouvelables
6.1 Introduction
6.2 Conception d’un algorithme d’OEP discrèt pour le Flow-Shop sous contraintes de ressources
6.2.1 Représentation de particule
6.2.2 Initialisation de l’essaim
6.2.3 Mise à jour de la vitesse et de la position
6.2.4 Stratégie de diversification
6.2.5 Opérateurs génétiques empruntés
6.2.5.1 Opérateur de croisement
6.2.5.2 Opérateur de mutation
6.2.6 Stratégie d’intensification
6.3 Paramétrage de l’algorithme
6.3.1 Taille de l’essaim
6.3.2 Critère d’arrêt
6.4 Résultats expérimentaux
6.4.1 Résultats de calcul pour les problèmes de petites tailles
6.4.2 Résultats de calcul pour les problèmes de moyennes à grandes tailles
6.5 Conclusion
Conclusions et perspectives
Bibliography