Nous proposons une méthode de renforcement des ressources cumulatives en ordonnancement. Une ressource cumulative est caractérisée par un nombre positif, appelé capacité, et les tâches à ordonnancer - non-interruptibles et chacune d'une longueur fixée - sont munies d'un nombre positif appélé consommation. La ressource cumulative impose qu'à tout moment, la somme des consommations des tâches en cours d'exécution soit inférieure à la capacité de la ressource. Cette ressource est fondamentale en ordonnancement à base de contraintes, et la propager efficacement est essentiel par la performance de tels systèmes.
Nous proposons une reformulation pour les ressources cumulatives qui permet, sans perdre de solutions faisables, d'augmenter la consommation de certaines tâches de façon à permettre aux algorithmes existants (notamment l'edge-finder) de trouver de meilleures propagations. Cette reformulation est d'excellente qualité, puisque nous montrons que la borne inférieure que nous obtenons par raisonnement énergétique sur la ressource reformulée est au moins ainsi élevée que la durée d'un ordonnancement préemptif des tâches sur la ressource d'origine.
Cette reformulation repose sur un programme linéaire dont la taille dépend de la capacité de la ressource mais pas du nombre de tâches, ce qui permet de précalculer les reformulations par énumération des sommets du polytope associé. Durant l'exécution, le calcul de la reformulation est donc très rapide.
Nous obtenons ainsi une amélioration significative de tous les algorithmes de propagation de la contrainte cumulative reposant sur les raisonnements énergétiques, en particulier les techniques d'edge-finding. Expérimentalement, nous améliorons les bornes pour plusieurs des instances RCPSP de la PSPLIB.
| Subject : | : | typdoc_1455 |
| Language of text | : | French |
| Topics | : | Scheduling, planning and production management |
| Keywords | : | cumulative ; ordonnancement ; RCPSP |
| PDF version | : |  PDF version |
