______________________________________________________________________________ ORDONNANCEMENT, SATISFACTION, OPTIMISATION (auteur : Pierre LOPEZ) (texte créé le : 15/11/2006 ) (mis à jour le : 06/08/2013 ) ______________________________________________________________________________ Contenu : - DES PROBLEMES DIFFICILES - PROBLEMES d’ORDONNANCEMENT - PLANIFICATION ou ORDONNANCEMENT ? - NOTATION - JOB SHOP - METHODES de RESOLUTION - METHODES EXACTES - METHODES d’APPROXIMATION - PROPAGATION et RECHERCHE de SOLUTIONS ______________________________________________________________________________ DES PROBLEMES DIFFICILES Les problèmes traités ici (ordonnancement, satisfaction, optimisation) relèvent de problèmes combinatoires. Il s'agit de problèmes difficiles à résoudre de par le très grand nombre de combinaisons envisageables pour la preuve d'existence voire la construction d'une solution. La complexité de calcul permet de mesurer la difficulté de résolution (en temps ou en espace mémoire) d'un problème de décision ou d'optimisation. Les problèmes combinatoires sont caractérisés par une complexité qualifiée d'exponentielle, c'est-à-dire non-polynomiale en la taille des données. Formellement, pour la classe de problèmes NP (respectivement co-NP), il est facile, en un temps polynomial sur une machine de Turing non-déterministe, de vérifier qu'une instance est (resp. n'est pas) solution d'un problème. NP signifie "Non-deterministic Polynomial time". De manière plus pragmatique, pour un problème de décision NP-complet ou un problème d'optimisation NP-difficile, le temps de calcul croît de manière exponentielle avec l'augmentation linéaire de la taille du problème. PROBLEMES d’ORDONNANCEMENT Inexorablement, les marchés vont vers les variétés des demandes-clients, la réduction des temps de cycle et une compétitivité accrue pour la réduction des coûts. Ces tendances incitent au 0-stock alors qu'une forte réactivité nécessite la maintenance de stocks plus importants. Ces objectifs contradictoires entraînent la nécessité de produire des solutions d'ordonnancement efficaces et adéquates, ce qui s'avère un problème complexe dans le cas général. PLANIFICATION ou ORDONNANCEMENT ? Dans le sens commun, les deux termes sont fréquemment employés pour désigner la même chose : construire des "plannings" d'exécution d'activités sur des moyens. Souvent néanmoins, une différence est à faire. De manière générale, la planification et l'ordonnancement sont des moyens par lesquels une organisation, une entité, choisit une suite d'actions pour atteindre un objectif donné. Dans les termes de l'Intelligence Artificielle, la planification se concentre sur la sélection d'actions parmi différentes alternatives ; il s'agit de décider de la nature des tâches à entreprendre et de les ordonner pour satisfaire l'(les) objectif(s). On parle aussi de génération ou de synthèse de plans. L'ordonnancement s'attache, lui, au positionnement temporel (date de début) et spatial (affectation aux ressources) des tâches qui permettent de réaliser ces actions, compte tenu de moyens de production (ressources) ayant été affectés pour la réalisation de chacune de ces tâches. Notons ici que, du point de vue de différentes communautés scientifiques, il n'y a guère de différences entre la planification rencontrée en IA et celle provenant plutôt de la gestion de production. En revanche, en IA les méthodes abordant la planification sont telles qu'elles tentent également de répondre (au moins en partie) au problème de l'ordonnancement. En d'autres termes, le terme de planification insiste sur l'aspect conception d'un plan (ensemble de tâches totalement ou partiellement organisées dans le temps), compte tenu d'une description du monde, de tâches pouvant être réalisées et d'objectifs à atteindre. Compte tenu du plan précédent et d'informations détaillées sur les disponibilités des moyens, l'ordonnancement consiste à renforcer le plan en déterminant QUI doit exécuter QUELLES actions et QUAND (il répond ainsi au problème d'affectation, en temps et en ressource, de chaque activité). Généralement, les deux problématiques sont traitées en profondeur de manière indépendante. Les processus s'exécutant de façon successive. Ceci n'empêche pas que des systèmes de planification fasse aussi de l'ordonnancement (ou le contraire). Il existe bien entendu des interactions entre la planification et l'ordonnancement. En effet, plusieurs plans sont possibles pour satisfaire un objectif. Certains proposent l'incorporation de notions précises sur les ressources au sein d'un planificateur. D'autres pencheront pour le contraire, c'est-à-dire incorporer des raisonnements sur la génération de plans au sein d'un ordonnanceur. D'autres enfin proposeront une approche itérative permettant d'intégrer les niveaux de planification et d'ordonnancement afin de coordonner les décisions de chacun d'eux. NOTATION La notation désormais adoptée pour représenter les problèmes d'ordonnancement est celle à 3 champs, ALPHA | BETA | GAMMA, proposée initialement par Graham et al. 79, étendue par Lawler 79, reprise par Lageweg, Lawler, Lenstra, Rinnooy Kan, "Computer-Aided Complexity Classification of Deterministic Scheduling Problems, Report No. BW138, Matematisch Centrum, Amsterdam, 1981. ALPHA = Alpha1 Alpha2 Alpha1 = ensemble vide => 1 machine ensemble non vide => machines parallèles P identiques Q uniformes R non reliées Alpha2 = m BETA = restrictions GAMMA = critère JOB SHOP En ordonnancement de production (job shop, pour prendre un exemple assez général), le problème consiste à trouver une affectation séquentielle des ressources en compétition afin d'optimiser un critère particulier. On a : - un ensemble J de n jobs Ji est à exécuter sur un ensemble M de m machines Mk - chaque job doit être exécuté sur chaque machine et est composé de mi opérations Oi×mi ordonnées suivant une gamme opératoire. - N opérations au total (sum_{i=1..n} mi) - pas de préemption - une gamme propre à chaque job - une machine ne traite qu'un job à la fois Parmi les critères retenus, le "Makespan" tient une place historique importante ; facile a modéliser mathématiquement, permettant de cerner la difficulté computationnelle au calcul d'une solution optimale. METHODES de RESOLUTION Parmi les premiers travaux sur le job-shop, on peut citer ceux de Johnson 1954, Jackson 1956, Akers & Friedman 1955, Giffler & Thompson 1960, Muth & Thompson 1963. Roy & Sussman proposent, en 1964, la représentation par graphe disjonctif. En 1969, Balas est le premier à appliquer une méthode énumérative basée sur le graphe disjonctif. Comme pour tout problème d'optimisation, les principales méthodes de résolution des problèmes d'ordonnancement se divisent suivant qu'il s'agisse de méthodes exactes ou de méthodes d'approximation. METHODES EXACTES Parmi les plus célèbres des méthodes exactes, on trouve : - La programmation dynamique : une approche basée sur relations de récurrence et recherche rétrograde de parcours dans un graphe ; absente de retour arrière (Backtracking-free approach, +), mais exponentielle en temps et en espace (-). - Les méthodes arborescentes du type séparation/évaluation (Branch-and-Bound) : premier Branch and Bound proposé par A. H. Land and A. G. Doig, "An automatic method of solving discrete programming problems," Econometrica, p. 28, 1960. - La programmation mathématique du type linéaire en variables mixtes : décomposée en 2 phases itératives : (1) relaxation des contraintes d'intégrité et résolution par une méthode de Simplexe ou de points intérieurs ; (2) réintégration des contraintes d'intégrité et résolution par des méthodes arborescentes ou des méthodes de coupe. Sur ces dernières, citons : . les coupes polyédriques issues de la structure particulière du problème (Gomory, Kelley) ; . "lift & project" (Balas, Lovász, Cornuéjols, Schrijver) : gonflage du problème par introduction de nouvelles variables (provenant par exemple de produits de variables binaires originales) (lift), puis déduction d'inégalités valides pour le problème de départ par projection (de polyèdres convexes) sur le problème original (en éliminant les variables rajoutées) (project). METHODES d’APPROXIMATION Elles sont aussi appelées méthodes heuristiques ou tout simplement heuristiques. Le mot vient du Grec "heuriskien" : "qui sert à la découverte des faits". Il s'agit de méthodes rapides mais n'offrant pas de garantie d'optimalité. Dans ce registre, on peut citer des : - méthodes spécifiques au job shop comme la procédure de la machine goulet, les algorithmes d'insertion - méthodes générales : . les algorithmes gloutons (ou myopes ou aveugles), interdisant, à chaque étape de la résolution, une remise en cause des décisions déjà prises . les algorithmes de liste (ou méthodes sérielles) . les méthodes arborescentes tronquées (Beam Search, Limited Discrepancy Search, Branch-and-Greed) . la recherche locale . les métaheuristiques En ce qui concerne les méthodes arborescentes tronquées et plus particulièrement la recherche à divergences limitées (LDS), la divergence ("discrepancy") représente l'écart entre deux solutions d'instanciation. On mesure par exemple l'écart d'une solution X par rapport à une solution de référence Xi par : delta(X,Xi) = sum_{j=1}^n dj avec dj = 1 si X(j) \ne Xi(j), 0 sinon. Dans les méthodes de recherche locale, on part d'une solution (trouvée par exemple par une heuristique) et on lui fait subir un petit changement afin de voir si la solution s'améliore. Une implémentation simple d'une recherche locale produit une heuristique d'amélioration suivant une stratégie gloutonne ; son inconvénient majeur est de s'enfermer dans des minima locaux. Les métaheuristiques concernent un cadre général de résolution. Elles décrivent un processus complexe qui guide une heuristique en mémorisant le parcours de recherche. Leur force est leur faculté à s'échapper de minima locaux. Ceci est effectué au prix de mouvements (qui définissent des voisinages) qui peuvent dégrader la solution courante. Les métaheuristiques sont composées de deux grandes parties : l'exploration, qui permet de visiter des régions différentes dans l'espace des solutions, et l'exploitation, qui permet de savoir où se trouvent les meilleures solutions. On distingue les métaheuristiques à solution unique (Tabou, recuit, algorithme à seuil) et celles à population de solutions (algorithme de la fourmi, algorithmes génétiques, recherche dispersée [scatter search]...). Dans les algorithmes génétiques, l'exploration est réalisée par les opérateurs de mutation et assure la diversification du voisinage ; l'exploitation est assurée par les opérateurs de croisement et recherche les meilleurs enfants possibles (intensification). Un algorithme à seuil est une méthode de descente (minimisation d'un critère) déterministe. Le recuit simulé est une méthode de descente probabiliste. L'algorithme choisit aléatoirement une solution initiale S. Un voisin Sc de cette solution est généré. On calcule l'écart des fonctions coût Delta = f(Sc)-f(S). Si on obtient une réduction de la fonction coût, la solution courante est remplacée par le voisin. Sinon, si on a une augmentation de la fonction coût, le voisin remplace la solution courante avec une probabilité d'acceptation donnée par : EXP(-Delta/T) où T est un paramètre, appelé température, qui contrôle le processus de recuit. Dans la méthode Tabou, la dégradation d'une solution est autorisée afin de sortir d'un minimum local. Cependant, pour ne pas retomber dans ce minimum local, on enraye ce phénomène cyclique en créant une liste Tabou qui répertorie les derniers mouvements et interdit de revenir sur eux. PROPAGATION Au coeur de la programmation par contraintes se trouvent les techniques de propagation de contraintes. Le rôle de la propagation de contraintes est l'exploitation des effets réducteurs des contraintes sur le domaine de recherche initial, grâce à des techniques de retrait de valeurs inconsistantes (algorithmes de filtrage). Une règle de propagation suit la syntaxe 'cond => exp' où 'cond' est une assertion logique, 'exp' une expression. Dès que 'cond' devient vrai, 'exp' est évaluée. La condition est par exemple une formule logique du 1er ordre (quantificateurs universels et existentiels) portant sur les variables du problème, la conclusion une actualisation de ces variables. ALGORITHME de RECHERCHE de SOLUTION Le schéma général d'une procédure de recherche d'une solution peut être le suivant : tant que toutes les tâches ne sont pas ordonnancées et qu'une inconsistance globale n'est pas détectée appliquer les règles de propagation si une inconsistance est détectée alors retour arrière sinon sélection d'une tâche sélection d'un placement pour cette tâche Si l'on considère un problème d'optimisation du type minimisation de la durée totale (min Makespan), on procède souvent à l'exploration d'une arborescence sur un horizon H situé au milieu d'un intervalle limité par une valeur inférieure - trouvée par propagation - et une valeur supérieure - déduite par une (méta-)heuristique - de cette durée. Si la recherche arborescente ne détecte pas d'inconsistance, H est alors pris comme borne supérieure ; si une inconsistance est détectée, la borne inférieure devient H+1. On reprend alors la recherche en déterminant par dichotomie un nouvel horizon ; on évolue jusqu'à ce que bornes inférieure et supérieure soient égales, qui indique que l'optimum est atteint. BRANCHEMENT (ou SEPARATION) dans un ARBRE DE RECHERCHE Dans l'optique de la résolution d'un problème d'ordonnancement, les règles de propagation permettent d'élaguer l'espace de recherche en éliminant des inconsistances locales qui ne pourront pas être considérées dans les solutions globales. Pour décider de l'affectation des variables laissées libres (tâches non ordonnancées) on a alors recours à des méthodes d'instanciation qui permettent de sélectionner ces variables et de leur affecter une valeur ; ces méthodes sont d'un impact important sur l'efficacité dans la recherche d'une solution. De manière générale pour un programme linéaire en nombres entiers (MIP), on fait intervenir le pseudo-coût d'une variable en estimant la modification de la valeur de l'objectif pour le problème relaxé, compte tenu des deux branches de l'encadrement par valeurs entières inférieure et supérieure d'une variable. Pour un problème de satisfaction de contraintes (CSP) ou de satisfaisabilité (SAT), l'impact d'une séparation est mesuré par le nombre de réductions induites des domaines des variables (valeurs d'inférence d'une variable). Ces mesures peuvent être regroupées en un seul score par multiplication ([Tobias Achterberg, "Hybrid Branching", CPAIOR 2009]) REGLES de SELECTION Pour le problème de job-shop, on peut par exemple définir des heuristiques basées sur la flexibilité temporelle associée à différentes décisions de séquencement. Ce sont des heuristiques de choix de tâches basées sur la mesure de marges temporelles ; elles sont associées aux règles d'élimination du type paires de disjonction. Pour la sélection de la tâche, la décision la plus contrainte est choisie ; elle est identifiée par la paire de tâches dont un des ordres donne le minimum de marge : min[slack(i