PFIA 2024
Une approche par programme linéaire pour réparer de manière optimale un plan temporel non contrôlable lorsque les incertitudes sont ajustables
Les réseaux temporels simples avec incertitude (STNU) sont un modèle basé sur des contraintes conçu pour vérifier la « contrôlabilité » temporelle d’un plan sous incertitude (lorsque certaines durées ne peuvent pas être décidées par l’agent de planification). Quoi qu’il en soit, dans des cas tels que la planification multi-agents ou dépendante de ressources, il peut être possible de négocier ou de reconsidérer la flexibilité exogène et donc d’ajuster les limites des durées incontrôlables. Nous proposons une telle méthode de « réparation » pour les trois formes de contrôlabilité (faible, dynamique et forte), qui trouve la réduction minimale des limites pour restaurer la contrôlabilité. Plus spécifiquement, nous fournissons (1) un programme linéaire pour la contrôlabilité faible/dynamique qui prend en entrée et répare les cycles négatifs incontrôlables d’un STNU fournis par un algorithme de vérification ; et (2) un programme linéaire capable de vérifier la contrôlabilité forte, de la réparer et de fournir une stratégie d’exécution. Nous montrons que ces techniques améliorent considérablement la complexité temporelle des algorithmes existants.