RCPSP (Ordonnancement de Projet sous Contraintes de Ressources)

Le problème d'ordonnancement de projet sous contraintes de ressources (RCPSP) ordonnance les activités d'un projet en respectant à la fois les contraintes de précedence et des ressources renouvelables limitées comme la main-d'œuvre, les machines ou le budget par période. Contrairement à la CPM, qui suppose des ressources illimitées, le RCPSP est fortement NP-difficile.

Fonctionnement

Les heuristiques par règles de priorité construisent des ordonnancements avec le schéma de génération série ou parallèle : les activités sont insérées au plus tôt où précédence et disponibilité des ressources sont toutes deux satisfaites, ordonnées par des règles comme le plus de successeurs totaux ou la marge minimale. Les approches exactes utilisent la séparation et évaluation avec des bornes inférieures fondées sur les ressources, et les métaheuristiques, notamment les algorithmes génétiques à codage en liste d'activités, dominent les benchmarks standard PSPLIB.

Applications

Le RCPSP pilote l'ordonnancement des équipes et équipements de chantier, la planification des sprints d'équipes logicielles sous limites d'effectifs, la programmation des arrêts de maintenance en raffinerie et la planification de production en fabrication à la commande. C'est le pont canonique entre les algorithmes de graphes et la recherche opérationnelle industrielle.