Outils d'aide à la décision pour des problèmes d'ordonnancement dynamiques

Scheduling problems represent an important class of combinatorial optimization problems. Most work in this area focus on static problems in which all data (activities, resources, constraints) are known in advance. In practice, however, schedules are subject to unexpected events (late arrival of raw materials, new orders, machine breakdowns, etc.). Therefore, a computed schedule rarely follows the original plan. It is important to deal with dynamic scheduling problems. In this thesis, we consider a general scheduling problem: the Resource Constrained Project Scheduling Problem (RCPSP for short), and we propose a system that is able to solve dynamic instances of this problem. Although numerous work exist on the static case of the RCPSP, research on the dynamic case is not that abundant. In addition, existing methods were not really developed for dynamic instances. We propose here to solve the dynamic RCPSP using a technique developed for solving dynamic constraint satisfaction problems: explanations. An explanation is a set of constraints (a subset of the current constraints system) that justifies an action made during the search process (deduction of new constraints, contradiction leading to a failure, etc.). An explanation can be considered as an explicit trace of constraint propagation. Explanations allow to efficiently undo past effects of a constraint and thus to dynamically add and remove constraints. We have also developed a branch and bound algorithm (inspired from the literature) that consist, in each node, in propagating the temporal and resources constraints (using core-times, tasks-intervals and resource-histogram techniques) while recording explanations. Moreover, we use a notion of distance (gap between the end of an activity and the beginning of another) which allows the modeling of temporal constraints within a unique concept. Our system is thus able to solve efficiently (i.e. without re-computing from scratch and in a short computation time) dynamic instances of the RCPSP (i.e. adding/removing precedence constraints, adding/removing activities and resources). Furthermore, our system, being very generic, allows the handling of several extensions of dynamic RCPSP (such as generalized precedence/disjunction/overlapping constraints, and variation of resource availability).Les problèmes d'ordonnancement constituent une classe importante des problèmes d'optimisation combinatoire. La plupart des travaux dans ce domaine considèrent des problèmes statiques pour lesquels toutes les données (activités, ressources, contraintes) sont connues à l'avance. En réalité, ce type de problèmes est très souvent soumis aux aléas (matières premières livrées en retard, arrivées de nouvelles commandes, pannes de machines, etc.). Aussi, l'ordonnancement se déroule rarement comme prévu. On a alors affaire à un problème d'ordonnancement dit dynamique. Dans cette thèse, nous considérons un problème d'ordonnancement très général, appelé RCPSP (Resource Constrained Project Scheduling Problem), et proposons un système permettant de résoudre le cas dynamique. Bien que beaucoup de travaux concernent le RCPSP statique, seules quelques méthodes sont proposées pour le cas dynamique. De plus ces méthodes ne sont pas satisfaisantes. La méthode que nous proposons applique au RCPSP une des techniques utilisées pour résoudre les problèmes de satisfaction de contraintes dynamiques : les explications. Une explication est un ensemble de contraintes (un sous-ensemble du système de contraintes courant) qui justifie le résultat de la recherche (déduction de nouvelles contraintes, contradiction aboutissant à un échec, etc.). Ces explications sont une trace explicite du comportement de la propagation. Elles permettent de défaire efficacement les effets passés d'une contrainte et ainsi d'ajouter et retirer dynamiquement des contraintes. Nous avons ainsi développé une recherche arborescente (inspirée d'une recherche arborescente de la littérature) qui en chaque noeud propage les contraintes temporelles et de ressources (en utilisant les techniques de core-times, task-interval et resource-histogram) tout en conservant des explications. Nous utilisons de plus une notion de distance (écart entre la fin d'une activité et le début d'une autre) permettant d'exprimer toutes les contraintes temporelles dans un cadre unique. Notre système est ainsi capable de résoudre de manière efficace (i.e. sans repartir à zéro et dans un temps raisonnable) des instances de RCPSP dynamiques (i.e. ajouts/retraits de contraintes de précédence, ajouts/retraits d'activités et de ressources). De plus, notre système étant très générique, il permet de traiter des extensions du RCPSP dynamique (précédences/disjonctions/chevauchements généralises, et variation des disponibilités des ressources)