LA THÉORIE DE L’ORDONNANCEMENT

LA THÉORIE DE L’ORDONNANCEMENT

 La programmation par contraintes

Comme nous l’avons vu au chapitre précédent, peu de travaux dans le domaine de l’ordonnancement ont utilisé l’ordonnancement basé sur les contraintes, branche de la programmation par contraintes qui traite les problèmes d’ordonnancement. Ainsi, pour résoudre efficacement le problème traité dans ce travail de recherche, nous abordons les différents concepts utilisés en programmation par contraintes qui sont à la base de ceux utilisés en ordonnancement basé sur les contraintes. De plus, plusieurs de ces concepts peuvent s’avérer prometteurs pour les hybridations proposées dans cette thèse.
Chaque année, le nombre de sociétés exploitant et utilisant la programmation par contraintes augmente considérablement. En effet, des sociétés telles que British Airways,SAS, Swiss Air, SNCF, Michelin et Ericsson utilisent cette approche dans leur système d’information. De même, plusieurs solutions commerciales basées sur cette approche trouvent de plus en plus de clients [Yunes et ai, 2010]. Parmi ces solutions, nous citons à titre d’exemples PeopleSoft, i2 Technologies, InSol et Vine Solutions. Il existe également des entreprises, telles ILOG, IF Computer, Cosytec, SICS et ProloglA, qui fournissent des outils basés sur cette approche pour élaborer des systèmes d’information [Freuder et Wallace, 2000; Yunes et al, 2010].
Pendant de nombreuses années, les problèmes de satisfaction de contraintes {Constraint Satisfaction Problems {CSP)) ont été un sujet de recherche dans le domaine de l’intelligence artificielle {IA). Centrées sur des problèmes d’optimisation combinatoire difficiles, les recherches en IA remontent aux années cinquante et soixante et elles ont contribué aux progrès considérables réalisés dans le raisonnement par contraintes.
Plusieurs algorithmes ont été conçus à cette époque et sont devenus la base des algorithmes actuels de satisfaction de contraintes. Les premiers travaux sur ces problèmes, appelés au début réseaux de contraintes, ont été essentiellement motivés par des problèmes découlant du domaine du traitement de l’image [Montanari, 1974; Waltz,1975].
Un CSP consiste en un triplet P = {X,D,C} où X est un ensemble de variables {Xl,X2,…,XJ, D est un ensemble de domaines {D1}D2,…,Dn} et C un ensemble de contraintes. Chaque Xi peut prendre une valeur comprise dans le domaine Z), et doit respecter les contraintes de C. Les valeurs des variables peuvent ne pas être des entiers consécutifs ou des valeurs numériques [Van-Hentenryck, 1990; Baptiste, 1998]. La portée d’une contrainte C est le nombre de variables E e X tel que les valeurs v e D pouvant être prises par E sont restreintes par C [Dechter et Frost, 2002]. Une contrainte s’appliquant à seulement une variable est dite unaire. Une contrainte s’appliquant à deux
variables est dite, quant à elle, une contrainte binaire. Un CSP peut être vu sous la forme d’un graphe de contraintes où les sommets représentent les variables et où les arêtes représentent les contraintes du problème. Ainsi, pour un graphe de contraintes binaires, un ensemble de contraintes Cy e C est associé. Ces contraintes restreignent les valeurs pouvant être prises par les variables Xi et Xj simultanément [Cooper et al., 1994]. Une solution d’un CSP est une affectation d’une valeur de son domaine à chaque variable de manière à ce que toutes les contraintes soient satisfaites. Ainsi, nous pouvons rechercher une unique solution sans préférence, toutes les solutions, une solution optimale ou une bonne solution, étant donné une fonction objectif définie incluant toutes les variables.
Dans ce dernier cas, nous parlons de problèmes d’optimisation de contraintes (Constraint
Optimisation Problems (COP)).
Parmi les problèmes de CSP les plus connus figurent le problème des reines et le problème de coloration de graphe. Le problème des reines consiste à placer n reines sur n*n différentes cases d’un échiquier de n lignes par n colonnes, de manière à ce qu’aucune reine ne puisse en éliminer une autre (sur les trois axes : vertical, horizontal et diagonal) [Tsang, 1999]. Le problème de coloration de graphe est un problème où une couleur doit être affectée à chacune des zones d’une carte, de manière à ce qu’aucune zone adjacente de cette dernière ne soit de la même couleur. Il est ainsi possible de chercher à minimiser le nombre de couleurs utilisées pour colorier les différentes régions ou de minimiser le nombre de conflits avec un nombre limité de couleurs [Zhou et Nishizeki, 1999].
Plusieurs autres problèmes ont été traités comme étant des CSP, tels les problèmes d’ordonnancement [Baptiste et LePape, 1995; LePape et Nuijten, 1995; Nuitjen et Aarts,1996; Baptiste, 1998; Baptiste et al, 2001; Boivin, 2005; Burke et al, 2007], les problèmes de satisfaction (SAT) [Bennaceur, 1996], le problème de partitionnement [Brown, 1998], les problèmes d’affectation [Frisch et al, 2001] et les problèmes de séquençage d’ADN [Frutos et al, 1997] pour ne nommer que ceux-là.
Le choix de concevoir et de résoudre un problème en CSP plutôt qu’avec la programmation mathématique, par exemple, repose sur deux raisons. Premièrement, une représentation en CSP est souvent plus proche du problème : les variables du CSP correspondent aux entités du problème, et les contraintes n’ont pas à être traduites en inégalités linéaires. Cela rend la formulation plus simple, la solution plus facile à comprendre et rend le choix de bonnes heuristiques pour guider la stratégie de résolution plus simple. Deuxièmement, bien que les algorithmes de CSP soient simples, ils peuvent parfois trouver la solution plus rapidement que la programmation mathématique [Van Hentenryck, 1990; Baptiste, 1998].
Dans le but de résoudre des problèmes d’optimisation combinatoire, l’une des principales idées de la PC est d’utiliser les contraintes pour réduire l’espace de recherche de solutions afin de réduire les temps de calcul. Ce procédé est communément appelé la propagation de contraintes. Ainsi, des déductions sont effectuées afin de réduire les domaines des variables. Toutefois, cette technique demeure insuffisante pour résoudre les CSP qui sont généralement de la classe NP-difficile [Garey et Johnson, 1979 ]. En effet,la propagation de contraintes ne génère que quelques déductions. Il est alors nécessaire de réaliser une recherche dans l’espace de recherche, qui est généralement sous forme d’un arbre, pour trouver une solution ou déterminer s’il en existe une. Ainsi, deux composants sont introduits dans cette recherche : le premier consiste à aller vers l’avant pour faire le choix des variables et des valeurs, et le deuxième à revenir vers l’arrière pour corriger les
contradictions s’il en survient.
Dans la prochaine section, nous détaillons les différentes méthodes utilisées pour résoudre un CSP : la recherche systématique dans l’espace de recherche, la vérification de la consistance et la propagation de contraintes. Nous décrivons ensuite quelques méthodes d’amélioration de la recherche.

 La recherche systématique

Une solution au CSP peut être trouvée en cherchant systématiquement parmi toutes les affectations possibles des valeurs aux variables. Les méthodes de recherche utilisées pour cela se divisent en deux catégories. La première catégorie regroupe les méthodes qui parcourent l’espace de recherche composé des solutions complètes pour lesquelles une valeur est affectée à toutes les variables. La deuxième catégorie regroupe, quant à elle, les méthodes qui parcourent l’espace de recherche composé de solutions partielles pour lesquelles une partie des affectations est effectuée. Par la suite, ces méthodes étendent les solutions partielles pour obtenir des solutions complètes en prolongeant l’affectation partielle de valeurs. Il existe plusieurs algorithmes de résolution de CSP évoluant par le biais de recherche systématique d’affectation de valeurs aux variables. Certains de ces algorithmes garantissent de trouver une solution, si elle existe, ou prouvent que le problème étudié est insoluble. Ainsi, la recherche systématique est complète. Le principal désavantage de ces méthodes est qu’elles exigent énormément de temps de calcul. De même, ces méthodes utilisent généralement le composant de retour en arrière dans la recherche dans un arbre comme mécanisme de correction d’une décision prise antérieurement. Nous décrivons, dans la prochaine sous-section, quelques méthodes de  recherche systématique.

 Générer et Tester

La méthode Générer et Tester (GT) tient ses origines des approches mathématiques pour résoudre des problèmes combinatoires. C’est un algorithme typique de recherche complète dans l’espace de solutions. D’abord, l’algorithme génère quelques affectations complètes de variables et vérifie si celles-ci satisfont toutes les contraintes. Si ce test échoue, il existe alors des contraintes insatisfaites. L’algorithme essaie alors d’autres affectations et s’arrête dès qu’une affectation complète et satisfaisante pour toutes les contraintes est trouvée. Cette affectation représente une solution au problème. Dans le cas où toutes les affectations sont explorées et qu’aucune d’elles ne satisfait toutes les contraintes, le problème n’admet alors aucune solution. L’algorithme GT cherche
systématiquement dans l’ensemble de l’espace de solutions en explorant toutes les combinaisons possibles des affectations de variables. Le nombre de ces combinaisons est égal à la taille du produit cartésien de tous les domaines des variables.
Le principal inconvénient pour utiliser cette méthode est le fait de générer plusieurs affectations de valeurs aux variables qui sont rejetées lors de la phase de test. De plus, le générateur d’affectations de variables utilisé est aveugle. En effet, s’il existe déjà des instanciations conflictuelles, cela ne l’empêche pas d’en générer d’autres. Pour remédier à cela, il est possible de limiter la taille du générateur ou de fusionner la partie de génération avec celle du test.

 Le retour arrière

L’algorithme le plus connu et utilisé en programmation par contrainte pour faire une recherche systématique est sans doute le retour-arrière (BackTraking) (BT) [Gaschnig, 1978]. Le BT essaie d’étendre progressivement une solution partielle qui spécifie les valeurs consistantes ou encore cohérentes de certaines variables jusqu’à l’obtention d’une solution complète. Pour cela, le BT choisit des valeurs pour les variables non instanciées qui soient consistantes avec celles de la solution partielle. La consistance implique qu’aucune des contraintes n’est violée. Le BT peut être considéré comme la fusion des phases de génération et de test de GT. Dans le BT, les variables sont instanciées de façon séquentielle et, dès que toutes les variables pertinentes à une contrainte sont instanciées, la validité de la contrainte est vérifiée. Si une affectation partielle viole une contrainte, le retour arrière est effectué vers la dernière variable instanciée qui possède d’autres possibilités d’instanciation. Ainsi, à chaque retour arrière, un sous-espace du produit cartésien des domaines des variables est éliminé.
Conséquemment, le BT est de loin supérieur au GT. Cependant, la complexité de son fonctionnement non trivial est encore exponentielle pour la plupart des problèmes. Ces algorithmes sont également appelés, dans leur forme la plus simple, algorithmes à retour arrière chronologique du le fait qu’ils vont chercher la dernière variable instanciée.
Le BT, dans sa forme standard, comporte trois principaux inconvénients. En effet, le BT standard n’identifie pas la raison réelle du conflit créé. Ainsi, la recherche dans différentes régions de l’espace peut produire des échecs de test pour les mêmes raisons.
Le BackJumping (Bf), décrit plus loin, également appelé BT Intelligent, peut remédier à cet inconvénient. Le deuxième inconvénient du BT est d’avoir à effectuer des actions redondantes. En effet, même si les conflits sont détectés, ils ne sont pas sauvegardés pour des actions ultérieures. Les méthodes pour résoudre ce problème sont appelées BackChecking ou BackMarking. Le dernier inconvénient est la détection tardive des conflits auxquels il est possible de remédier avec les techniques de vérification de consistance abordées dans les prochaines sections.

 Le BackJumping

Le premier inconvénient du BackTracking cité plus haut peut être résolu par le BackJumping [Gaschnig, 1979] puisque leur fonctionnement est identique à l’exception dans la phase de retour en arrière. Les deux algorithmes traitent une variable à la fois et cherchent une valeur qui satisfait toutes les contraintes et ne génère aucun conflit.
Toutefois, si le BJ constate une incohérence, il analyse la situation afin d’identifier la source de cette incohérence. Il utilise les contraintes violées pour déterminer la variable conflictuelle. Si toutes les valeurs du domaine sont explorées, alors le BJ fait un retour en arrière vers la variable conflictuelle la plus récente. C’est la principale différence avec le BT qui, lui, fait un retour en arrière vers la dernière variable instanciée. Il existe des améliorations au 5J comme le Graph-Based BackJumping [Dechter, 1990] qui fait un retour en arrière vers la variable la plus récente qui contraint la variable courante.

 Le BackMarking

Le deuxième inconvénient du BT est d’effectuer des actions redondantes. Il est possible de résoudre ce problème par deux méthodes appelées respectivement BackCheking (BC) et BackMarking {BM). Le BC et son descendant le 5Msont tous deux des algorithmes utilisés pour réduire la compatibilité des tests de cohérence. Si le BC trouve, par exemple, qu’une étiquette Y/b (affectation de la valeur b à la variable Y) est incompatible avec une récente étiquette X/a, alors il se rappellera de cette incompatibilité.
Ainsi, tant que l’étiquette X/a est existante, Y/b ne sera plus considéré. Le BM [Elliot, 1980] est une amélioration du BC qui permet d’éviter certaines vérifications de contraintes redondantes telles que la découverte d’inconsistances redondantes. Il réduit le nombre de contrôles de compatibilité en se souvenant de chaque étiquette incompatible avec les dernières étiquettes. Il empêche également la répétition des vérifications fructueuses qui ont été effectuées auparavant.

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
3.5 CONCLUSION
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
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