Solveur RCPSP

Pseudocode

Le RCPSP, c'est CPM plus des ressources limitées, et ce seul ajout le fait passer de linéaire à NP-difficile. L'approche pratique est une heuristique d'ordonnancement en série guidée par une règle de priorité.

RCPSP(activites, dependances, capacites):
    ordre = triTopologique(activites)
    trier ordre selon une regle de priorite
    // p. ex. marge minimale, ou plus longue duree d abord

    pour chaque activite a dans l ordre priorise:
        t = max(fin[p] pour p predecesseur de a)
        tant qu une ressource r est saturee sur
              [t, t + duree[a]):
            t = t + 1        // repousser jusqu a ce que ca tienne
        debut[a] = t; fin[a] = t + duree[a]
        reserver les ressources de a sur cet intervalle

    duree du projet = max(fin[a])

La différence avec CPM est que le début d'une activité n'est plus fixé par ses seuls prédécesseurs: il peut être repoussé parce qu'une activité sans aucun lien occupe la machine. Cela détruit précisément la propriété qui rendait CPM linéaire, puisque la décision sur une activité affecte désormais des activités avec lesquelles elle n'a aucune dépendance. Aucune quantité de programmation dynamique sur l'ordre topologique ne suffit donc.

Exemple détaillé, étape par étape

Ordonnance quatre activités qui se disputent une unique ressource de capacité 1, et compare le résultat à ce que prédirait CPM.

Graphe d'exemple: Activités A (3 jours), B (2 jours), C (4 jours) et D (2 jours), A et B précédant C, et C précédant D. Toutes requièrent la même machine, dont il n'existe qu'un exemplaire.

1. Ce que dirait CPM. Sans limite de ressource, A et B s'exécutent en parallèle dès l'instant 0, C démarre à 3 et D finit à 9. Durée du projet: 9 jours.
2. Appliquer la limite de ressource. A et B ont toutes deux besoin de la machine et il n'y en a qu'une. Elles ne peuvent plus se chevaucher, l'une doit donc attendre. La priorisation décide laquelle.
3. Règle de priorité: plus longue durée d abord. A dure 3 et B dure 2, A passe donc en premier et occupe la machine de 0 à 3. B doit attendre et s'exécute de 3 à 5.
4. Ordonnancer C. C exige que A et B soient terminées, soit l'instant 5, et la machine est alors libre. C s'exécute de 5 à 9.
5. Ordonnancer D. D suit C et s'exécute de 9 à 11. La durée du projet est de 11 jours.

Avec des ressources illimitées le projet dure 9 jours; avec une seule machine il en dure 11. Les deux jours supplémentaires ne proviennent d'aucune dépendance mais purement de la contention de ressource. Note en outre que la notion de chemin critique devient glissante ici: la chaîne qui gouverne la date de fin inclut désormais l'attente de B pour la machine, ce qui n'est nullement une relation de précédence. C'est pourquoi les calendriers CPM sur des projets à ressources rares se révèlent systématiquement optimistes.

Complexité et son origine

Temps: NP-difficile; heuristique en série O(V^2 · R) · Espace: O(V · R)

L'heuristique d'ordonnancement en série traite chacune des V activités une fois et peut devoir, pour chacune, repousser l'instant de début en vérifiant la disponibilité des R ressources, ce qui donne de l'ordre de O(V au carré fois R) au pire avec une implémentation directe. C'est rapide et cela passe à l'échelle sur des milliers d'activités. Ce que cela ne fournit pas, c'est une garantie d'optimalité. Le RCPSP exact est NP-difficile et compte parmi les problèmes d'ordonnancement les plus coriaces de la recherche opérationnelle: des instances de référence de 60 activités seulement sont restées non résolues pendant des années. La séparation et évaluation exacte reste viable autour de 30 à 60 activités selon la structure, et au-delà on se tourne vers des métaheuristiques comme les algorithmes génétiques ou la recherche tabou.

Quand utiliser RCPSP (Ordonnancement de Projet sous Contraintes de Ressources), et quand l'éviter

Choisis selon que les ressources sont réellement limitantes et selon que tu exiges une garantie d'optimalité.

Pièges fréquents

• Planifier avec CPM puis ajouter les ressources ensuite. Un calendrier CPM suppose un parallélisme illimité. Y faire entrer après coup des limites de ressources allonge presque toujours le projet, comme dans l'exemple où 9 jours deviennent 11. Les ressources doivent figurer dans le modèle dès le départ, pas en correctif.
• Supposer que le chemin critique garde le même sens. Avec des ressources limitées, la séquence qui gouverne la date de fin peut inclure des attentes dues à la contention, qui ne sont pas des relations de précédence. La notion correspondante est la chaîne critique, qui intègre à la fois dépendances et conflits de ressources.
• Utiliser une seule règle de priorité et s en tenir là. Des règles différentes, marge minimale, plus longue durée d'abord, plus grand nombre de successeurs, produisent des calendriers différents et aucune ne domine les autres. Lances-en plusieurs et garde le meilleur; c'est peu coûteux et cela améliore souvent sensiblement le résultat.
• Oublier que les ressources peuvent être non renouvelables. Les ressources renouvelables, machines ou personnes, se libèrent à la fin de l'activité. Les non renouvelables, budget ou matière, sont consommées définitivement. Modéliser les secondes comme les premières produit des calendriers qui dépensent le budget plusieurs fois.
• Espérer résoudre exactement de grandes instances. Le RCPSP est l'un des problèmes difficiles classiques. Des instances de référence de 60 activités ont résisté des années aux méthodes exactes. Si ton projet compte des centaines de tâches, planifie par heuristiques et valide par simulation plutôt que de courir après l'optimum.

Questions fréquentes

Qu'est-ce que le RCPSP?

Le problème d'ordonnancement de projet sous contraintes de ressources cherche un calendrier respectant à la fois les relations de précédence entre activités et la disponibilité limitée de ressources renouvelables, en minimisant généralement la durée totale du projet. C'est CPM débarrassé de l'hypothèse de ressources illimitées.

Pourquoi le RCPSP est-il NP-difficile alors que CPM est linéaire?

Parce que les limites de ressources couplent des activités qui n'ont aucune dépendance entre elles. Dans CPM le début d'une activité ne dépend que de ses prédécesseurs, ce qui permet deux balayages en ordre topologique. Avec des ressources, retarder une activité peut en contraindre une autre totalement étrangère, et cette interaction globale fait exploser l'espace de recherche.

Quelle est la différence entre CPM et RCPSP?

CPM suppose que toutes les activités sans dépendance mutuelle peuvent s'exécuter simultanément. Le RCPSP ajoute des capacités de ressources qui empêchent ce parallélisme. Dans l'exemple ci-dessus, le même projet dure 9 jours sous CPM et 11 sous RCPSP avec une seule machine, et les deux jours d'écart sont purement de la contention.

Qu'est-ce qu'une règle de priorité dans le RCPSP?

C'est l'heuristique qui décide quelle activité ordonnancer en premier lorsque plusieurs sont prêtes et se disputent la même ressource. Les règles courantes sont la marge minimale, la plus longue durée d'abord, le plus grand nombre de successeurs ou la date de fin au plus tard la plus précoce. Aucune n'est toujours meilleure, en pratique on en lance donc plusieurs et on garde le meilleur calendrier.

À quoi sert le RCPSP?

À ordonnancer des lignes de production où les machines sont limitées, à affecter équipes et matériels dans la construction, à planifier des portefeuilles de projets partageant du personnel spécialisé, et plus généralement dans toute planification où les tâches se disputent une capacité finie au lieu de pouvoir s'exécuter librement en parallèle.