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).
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00008377 |
| Date | 27 November 2003 |
| Creators | Elkhyari, Abdallah |
| Publisher | Université de Nantes |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.002 seconds