E. Néron* et J. Carlier**
* Laboratoire d'Informatique de l'Université de Tours
** Heudiasyc Université de Technologie de Compiègne
Notre exposé portera sur la définition de nouvelles bornes pour le problème de gestion de projet à contraintes de ressources (Resource Constrained Project Scheduling Problem). A partir de la relaxation Multiple Elastique et Préemptive [Carlier & Néron, 2000], nous avons établi que certaines combinaisons linéaires de la durée des opérations pouvaient aboutir à des évaluations par défaut intéressantes. De plus ces combinaisons linéaires peuvent être calculées à priori, c'est-à-dire indépendamment de la durée des tâches. Cette démarche a été étendue à d'autres combinaisons linéaires faisant intervenir les durées opératoires des tâches. Cette généralisation permet de retrouver certaines bornes classiques de la littérature [Baptiste et al. 2000, Mingozzi et al. 1998], et d'intégrer des notions issues du problème de Bin Packing. Ces contraintes linéaires nous permettent de définir un schéma général de programmation linéaire, ainsi que des « ressources redondantes ». Nous avons testé cette approche sur les instances classiques de la littérature ainsi que sur des instances générées aléatoirement [Carlier & Néron, 2001].