Algorithmes génétiques et programmation par contraintes

LES PROBLÈMES D’ORDONNANCEMENT

La théorie de l’ordonnancement

Classification des problèmes d’ordonnancement

L’ordonnancement présente des spécificités importantes en fonction des caractéristiques des usines et des produits considérés. Nous recensons tout d’abord les principaux types de systèmes de production, puis nous listons les types de problèmes présents dans ces systèmes. Une classification très classique des systèmes de production est basée sur la nature et le mode d’implantation des ressources nécessaires à la fabrication des produits. Il existe, à ce titre, trois principaux modèles d’ordonnancement dans l’industrie. En effet, tous les modèles existants peuvent se ramener à ces trois modèles : modèle à machine unique, modèle à machines parallèles et modèle à machines en série.
La Figure 2-1 [Zandieh et Fatemi, 2003] illustre la relation entre les différents modèles d’ordonnancement, et ce suivant l’environnement des machines et où « E » représente le nombre d’étages et «M (E) » le nombre de machines par étage. Un étage identifie un ensemble de machines parallèles et identiques.
La configuration de base est celle où l’ensemble des travaux à réaliser est exécuté par une seule machine et où les travaux sont composés d’une seule opération. Il s’agit alors du modèle à machine unique. Il est possible de retrouver cette situation dans les industries de fonderie, d’aluminium, d’agroalimentaire et de pâtes à papier. Dans ce genre de situation, le système de production est généralement confronté à une machine goulot qui influence l’ensemble du processus. L’analyse peut se faire alors par l’étude de cette machine [Pinedo, 2002]. Nous pouvons remarquer, d’après la Figure 2-1, que ce modèle est à la base de tous les autres modèles. Le modèle à machines parallèles est une façon de remédier au problème lié aux machines goulots. Dans ce cas, plusieurs machines identiques peuvent jouer le même rôle. Ce modèle est surtout rencontré, entre autres, dans les secteurs industriels tels que l’industrie alimentaire, les industries plastiques, les fonderies et l’industrie textile.
En plus des systèmes de production à machine unique et à machines parallèles, il existe ceux composés de machines organisées en séries. Ces dernières exécutent un certain nombre de travaux successifs, où chaque travail suit une séquence sur les machines. Ce modèle peut être rencontré dans les industries de montage, tels l’assemblage de voitures, le montage de composants électroniques, ou encore dans l’industrie des télécommunications. Il existe trois modèles de traitement des travaux pour les machines en séries : modèle à cheminement unique (flow-shop), modèle à cheminement libre (open-shop) et modèle à cheminement multiple (job-shop). Un modèle de machine en séries est également appelé atelier [Carlier et Chrétienne, 1988].
Dans le modèle à cheminement unique, tous les travaux visitent les machines dans le même ordre, dont les durées opératoires pouvant être différentes. Le problème le plus simple est ainsi, en présence d’un ensemble de travaux à traiter, de déterminer la séquence de lancement des travaux permettant de minimiser le délai d’achèvement. Les ateliers à cheminement libre sont des ateliers dans lesquels les opérations à réaliser sur les produits sont permutables. En d’autres termes, il n’existe pas de séquence fixée.
Concernant le modèle à cheminement multiple, chaque travail possède un cheminement dans l’atelier et chacun d’eux peut s’exécuter plusieurs fois sur la même machine, ce quin n’est pas le cas du flow-shop. Il s’agit dans ce cas de déterminer les dates de passage surnles différentes machines de travaux ayant des cheminements différents dans l’atelier. Cesntravaux partageant des ressources communes, des conflits sont susceptibles de survenir,nrésultant des croisements de flux.nAvec l’évolution des besoins des entreprises manufacturières pour l’application denméthodes plus efficaces afin de répondre aux besoins de la production, plusieurs autresbmodèles ont vu le jour au fil du temps. Les ateliers flexibles, populaires dans les années 1980, en particulier pour la fabrication de pièces mécaniques, tentent également de procurer un meilleur compromis entre productivité et flexibilité par un degré d’automatisation poussé. Il s’agit à la base d’ateliers de type job-shop dans lesquels les stockages, les manipulations et les traitements des pièces sont automatisés. Les ateliers de type hybride représentent des ateliers dans lesquels un « étage » donné de la fabrication peut être assuré par plusieurs machines en parallèle.

 Évaluation d’un problème d’ordonnancement

Un ou plusieurs objectifs sont généralement associés à un problème d’ordonnancement. Les objectifs sont nombreux et Mellor [1966] en distingue 27 différents. Dans la résolution d’un problème d’ordonnancement, un ou plusieurs objectifs construits sur la base d’indicateurs de performance sont pris en considération. Nous cherchons donc à minimiser ou à maximiser de tels objectifs qui peuvent être liés au temps, aux ressources ou à des coûts, tels ceux de lancement, de production, de stockage, etc. Ces objectifs font intervenir, par exemple, la durée totale, le temps de
présence des travaux dans le système de production (en-cours) et les retards. Ainsi, nous pouvons, par exemple, chercher :
à minimiser le temps total d’exécution des travaux noté Cmax (Makespan) qui est égal au temps de fin du dernier travail. Cmax = max{CJoù (^représente le temps de fin du travail i et n le nombre de travaux.

 Notation des problèmes d’ordonnancement

Pour faciliter la classification des problèmes d’ordonnancement, nous utilisons la notation a \ ft\ y proposée initialement par Graham et al. [1979], étendue par Lawle [1979] et reprise par Lawler et al. [1981] où ce représente la configuration des machines,/? les contraintes et les restrictions sur les travaux et y l’objectif à optimiser. Par exemple,l\sij\Cmax représente le problème à machine unique avec temps de réglages dépendants avec l’objectif de minimiser le Makespan et 11 s:j | ]Try représente le problème à machine unique avec temps de réglages dépendants avec l’objectif de minimiser le retard total.

Complexité des problèmes d’ordonnancement

Théoriques ou réels, les problèmes d’ordonnancement sont des problèmes d’optimisation combinatoire (POC) dont la complexité est établie pour la plupart d’entre eux. L’étude de la complexité d’un problème est en rapport avec les algorithmes mis en œuvre pour le résoudre. La théorie de la complexité offre un cadre d’étude formel dans lequel les problèmes peuvent être classés selon leur degré de complexité. Pour plus d’informations sur la théorie de la complexité, le lecteur consultera Cook [1971] et Garey et Johnson [1979]. Le but de la théorie de la complexité est la classification des problèmes de décision [Cook, 1971] suivant leur degré de difficulté de résolution. Dans la littérature, il existe plusieurs classes de complexité, mais les plus connues sont les problèmes de la classe P et les problèmes de la classe NP. En effet, si un problème de décision donnant la réponse correcte (« oui » ou « non ») est associé à un problème appartenant à la classe P, alors cette réponse se fait en un temps polynomial, c’est-à-dire en un temps O(nk) avec n la taille du problème traité, k un entier naturel et une constante indépendante de n. Les problèmes de la classe NP sont ceux dont le résultat « oui » de leur problème de décision selon un algorithme non déterministe en un temps polynomial peut être obtenu. Les algorithmes non déterministes sont capables d’effectuer un choix judicieux dans un ensemble d’éléments. Ils ne peuvent pas être implantés sur ordinateur et sont plutôt d’intérêt théorique. La majorité des problèmes d’ordonnancement se classe dans la catégorie des problèmes dits NP-difficiles [Garey et Johnson, 1979 ]. Pour ces problèmes, il n’existe pas d’algorithmes de complexité optimale pour les résoudre à l’optimalité. Dans un problème à machine unique, par exemple, comportant n travaux, il ya/i! solutions possibles. Plus récemment, dans son ouvrage, Pinedo [2002] donne la complexité de plusieurs problèmes d’ordonnancement industriel. Pour résoudre de tels problèmes, Blazewicz et al. [1994] suggèrent trois avenues : i) utiliser des méthodes exactes pour de petites instances, ii) utiliser des heuristiques et iii) utiliser des méthodes hybrides.

Table des matières

RÉSUMÉ
ABSTRACT
REMERCIEMENTS
TABLE DES MATIÈRES
LISTE DES FIGURES
LISTE DES TABLEAUX
CHAPITRE 1 INTRODUCTION GÉNÉRALE
1.1 OBJECTIFS DE LA RECHERCHE
1.2 MÉTHODOLOGIE
1.3 ORGANISATION DU DOCUMENT
CHAPITRE 2 LES PROBLÈMES D’ORDONNANCEMENT
2.1 INTRODUCTION
2.2 LA THÉORIE DE L’ORDONNANCEMENT
2.2.1 Classification des problèmes d’ordonnancement
2.2.2 Évaluation d’un problème d’ordonnancement
2.2.3 Notation des problèmes d’ordonnancement
2.2.4 Complexité des problèmes d’ordonnancement
2.3 PROBLÈMES D’ORDONNANCEMENT AVEC RÉGLAGES DÉPENDANTS DE LA SÉQUENCE
2.4 PROBLÈME D’UNE MACHINE UNIQUE AVEC RDS MINIMISANT LE RETARD TOTAL
2.4.1 Description du problème traité
2.4.2 Jeux d’essai et approches de résolution pour le problème MURDS
2.5 CONCLUSION
CHAPITRE 3 ALGORITHMES GÉNÉTIQUES ET PROGRAMMATION PAR CONTRAINTES
3.1 INTRODUCTION
3.2 LES ALGORITHMES GÉNÉTIQUES
3.2.1 La représentation
3.2.2 La fitness
3.2.3 Population initiale
3.2.4 L’opérateur de sélection
3.2.4.1 La sélection par la fitness
3.2.4.2 La sélection par tournoi
3.2.5 L’opérateur de croisement
3.2.6 L’opérateur de mutation
3.2.7 L’opérateur de remplacement
3.2.8 Critères d’arrêt
3.3 LA PROGRAMMATION PAR CONTRAINTES
3.3.1 La recherche systématique
3.3.1.1 Générer et Tester
3.3.1.2 Le retour arrière
3.3.1.3 Le BackJumping
3.3.1.4 Le BackMarking
3.3.1.5 Autres techniques de recherche
3.3.2 Techniques de vérification de consistance
3.3.2.1 Consistance de nœuds
3.3.2.2 Consistance d’arcs
3.3.2.3 Directionnal Arc Consistency
3.3.2.4 Path Consistency
3.3.3 Propagation des contraintes
3.3.3.1 BackTracking
3.3.3.2 Forward Checking
3.3.3.3 Partial Look Ahead
3.3.4 Amélioration de la recherche
3.4 L’ORDONNANCEMENT BASÉ SUR LES CONTRAINTES
3.4.1 Optimisation versus programmation par contraintes
3.4.2 Modélisation des problèmes d’ordonnancement
3.4.2.1 Les activités
3.4.2.2 Contraintes temporelles
3.4.2.3 Contraintes sur les ressources
3.4.2.4 Extensions de la modélisation
3.4.2.5 Fonction objectif
3.4.2.6 Techniques de propagation spécifiques 84
3.5 CONCLUSION 85
CHAPITRE 4 RÉSOLUTION DU PROBLÈME MURDS AVEC UN ALGORITHME GÉNÉTIQUE
4.1 INTRODUCTION
4.2 ALGORITHME GÉNÉTIQUE POUR LE PROBLÈME MURDS
4.2.1 Représentation pour le problème MURDS
4.2.2 Fonction d’évaluation pour le problème MURDS
4.2.3 Population initiale pour le problème MURDS
4.2.4 Opérateur de sélection pour le problème MURDS
4.2.5 Opérateur de croisement pour le problème MURDS
4.2.6 Opérateur de mutation pour le problème MURDS
4.2.7 Opérateur de remplacement pour le problème MURDS
4.2.8 Gestion des doublons
4.2.9 Critère d’arrêt
4.3 RÉSULTATS EXPÉRIMENTAUX
4.4 CONCLUSION
CHAPITRE 5 RÉSOLUTION DU PROBLÈME MURDS AVEC LA PROGRAMMATION PAR CONTRAINTES
5.1 INTRODUCTION
5.2 IMPLEMENTATION AVEC ILOGCP™
5.2.1 SCHEDULER
5.2.2 SOLVER
5.3 FORMULATION DU PROBLÈME MURDS AVEC ILOG CP™
5.3.1 Modélisation de la machine unique
5.3.2 Modélisation des activités
5.3.3 Modélisation des temps de réglage
5.3.4 Modélisation de la fonction objectif
5.4 RÉSOLUTION DU PROBLÈME MURDS AVEC ILOG CP™
5.4.1 Algorithme de recherche
5.4.2 Parcours de l’arbre de recherche
5.5 CONCLUSION
CHAPITRE 6 ALGORITHMES HYBRIDES POUR RÉSOUDRE LE PROBLÈME MURDS
6.1 INTRODUCTION
6.2 CLASSIFICATION DES STRATÉGIES D’HYBRIDATION DE MÉTAHEURISTIQUES ET DE MÉTHODES EXACTES 1
6.3 ALGORITHME GÉNÉTIQUE HYBRIDE COLLABORATIF
6.3.1 Opérateur de croisement hybride
6.3.2 Processus d’intensification
6.3.2.1 Processus d’intensification optimisant le retard total
6.3.2.2 Processus d’intensification optimisant le Makespan
6.3.3 Résultats et discussions sur la performance de l’approche collaborative
6.4 ALGORITHME GÉNÉTIQUE HYBRIDE INTÉGRATIF
6.4.1 Domaine de positions associé à un travail
6.4.2 Règle de transition
6.4.2.1 Trace de phéromone SUCC,
6.4.2.2 Heuristique de regard vers l’avant
6.4.3 Croisement hybride intégratif CHmT
6.4.3.1 Fixation des positions
6.4.3.2 Placement de la section de croisement
6.4.3.3 Règle de transition pour la section de remplissage
6.4.4 Résultats et discussions de l’approche intégrative
6.5 CONCLUSION
CHAPITRE 7 CONCLUSION ET PERSPECTIVES
7.1 CONCLUSION
7.2 PERSPECTIVES DE RECHERCHE
RÉFÉRENCES

Télécharger le rapport complet