offres d'emploi formations actualités contact accès annuaire intranet
Séminaires >

Le Resource-Constrained Project Scheduling Project (RCPSP)

Virginie André

jeudi 13 mars 2014 à 13h30

salle B014


Le Resource-Constrained Project Scheduling Project, ou RCPSP est un problème très étudié dans la littérature. Ce problème consiste à ordonnancer des activités tout en minimisant le makespan (par exemple). Toutefois, il faut tout de même ajouter quelques contraintes : les activités peuvent être reliées par des précédences à respecter et les ressources sont disponibles mais dans un nombre limité.

Décrit ainsi, ce problème semble relativement simple à résoudre, et pourtant nous retrouvons très rapidement des limites à sa résolution. Selon (Valls et al., 2005), ce type de problème ne peut être résolu avec des méthodes exactes uniquement si le nombre d’activités est inférieur à 60.

Étant donnée sa description, ce type de problème peut permettre de modéliser énormément de cas pratiques : dans l’industrie (aéronautique, fabriquant de métaux, bio-technologie ou encore dans un projet de recherche pharmaceutique), dans les hôpitaux (l’organisation des blocs opératoires ou le transports des produits), pour le transport ferroviaire, etc... De même, nous pouvons modéliser des problèmes de type : Flow Shop, Open-Shop, Job-Shop ou des problèmes d’équilibrage à l’aide du RCPSP (Sprecher A.,1994). Pour conclure, ce problème est adaptatif, et est très largement utilisé pour résoudre de très nombreuses études applicatives.

Maintenant, que se passe-t-il si on ajoute d’autres contraintes, d’autres spécificités à ce type de problème ? En effet, on peut rencontrer des contraintes d’incompatibilité entre une activité et une ressource, une ressource disponible selon un planning, une activité décomposée en étapes... En ce qui concerne les spécificités, nous pouvons parler de durée de déplacement des ressources à prendre en compte entre chaque activité ou étape ou encore de contexte stochastique.

Lors de cette présentation, après avoir succinctement présenté le problème, je décrirai les différentes extensions que l’on peut trouver dans la littérature. Un cas pratique sera alors présenté en m’appuyant sur mes travaux. Pour conclure, je présenterai les perspectives de travail en relation avec les travaux en cours.