Ordonnancement cumulatif avec dépassements de capacité

 Mises à jour des bornes inférieures des coûts et de l’objectif

La mise à jour des bornes inférieures des domaines des variables de coût peut s’avérer importante pour la résolution. Nous montrons comment réaliser ces mises à jours dans les algorithmes de Sweep et d’Edge-Finding, ainsi que les bornes inférieures de la variable obj qui en découlent. 

Mises à jour dans l’algorithme de Sweep

Les variables Cost peuvent ˆetre directement filtrées dans l’algorithme de Sweep, pendant que le profil cumulatif est calculé, sans modifier la complexité temporelle. La r`egle de filtrage est la suivante, et l’exemple 34 illustre ensuite cette r`egle 5.1. Algorithmes de filtrage 89 R`egle de filtrage 6 Considérons le rectangle courant h[δ, δ′ [, sumhi dans l’algorithme de Sweep : – si costC = max, alors si sumh − lcj(δ) > costj (δ), l’intervalle [costj (δ), sumh − lcj(δ)[ peut ˆetre retiré de D(costj (δ)), – si costC = sum, alors si (δ ′−δ)×(sumh−lcj(δ)) > costj (δ), l’intervalle [costj (δ),(sumh−lcj(δ))× (δ ′ − δ)[ peut ˆetre retiré de D(costj (δ)). Preuve. L’algorithme de Sweep maintient la donnée sumh, qui correspond à la hauteur courante du profil cumulatif des parties obligatoires (Définition 21). Par construction, sachant que l’algorithme de Sweep pour SoftCumulative int`egre les dates de début d’intervalles utilisateur dans la liste courante des événements, dans l’intervalle [δ, δ′ [, sumh est constant et lcj est unique. On peut donc considérer de fa¸con équivalente n’importe quel point de temps dans [δ, δ′ [, par exemple δ. D’apr`es la Définition 36, lorsque le param`etre costC est max alors la variable de coût costj de l’intervalle courant mesure la dépassement maximal au delà de la capacité locale lcj. Donc si sumh − lcj (δ) > costj (δ) alors costj = costj (δ) peut ˆetre mis à jour à la valeur sumh−lcj(δ). De fa¸con similaire, lorsqu’on consid`ere l’aire excédant la capacité locale lcj dans [δ, δ′ [, si celle-ci est strictement supérieure à costj alors on peut mettre à jour costj à la valeur (δ ′ − δ) × (sumh − lcj(δ)).  Exemple 34 La Figure 5.10 donne un exemple de filtrage selon cette r`egle. Sur celle-ci, un profil cumulatif des parties obligatoires est représenté. Celui-ci induit un dépassement de 2 (quel que soit costC ). Alors la variable de coût associée peut ˆetre mise à jour, et l’intervalle [0, 2[ peut ˆetre retiré de son domaine. 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 Consommation Temps D(cost1) = [0, 2] coût imposé par les parties obligatoires D(cost1) = D(cost1)\[0, 2[ Figure 5.10 – Le polygone plein représente le profil cumulatif des parties obligatoires d’un probl`eme softcumulative. Dans cet exemple, pour costC= max, ou costC= sum, avant le filtrage, D(cost1) = [0, 2]. En t = 3, sumh = 5, lc1 = 3 : sumh − lc1 > cost1, alors nous filtrons D(cost1) tel que D(cost1) = D(cost1)\[0, 2[. Les bornes inférieures pour la variable objectif sont : – si objC = sum, LB = P j∈[0,k−1] costj , – si objC = max, LB = maxj∈[0,k−1](costj ). 90 5. Résolution de probl`emes d’ordonnancement cumulatif sur-contraint Ces bornes peuvent ˆetre calculées incrémentalement sans augmenter la complexité temporelle, et la variable obj est mise à jour.

Mises à jour dans l’algorithme d’Edge-Finding de Vil´ım

Le calcul d’une borne inférieure de la variable objectif peut également ˆetre intégré dans l’algorithme d’Edge-Finding de Vil´ım. Dans cet algorithme, pour chaque intervalle considéré, l’énergie totale des activités nécessairement enti`erement comprises dans cet intervalle est calculée. Cette énergie peut ˆetre utilisée pour calculer une borne inférieure de la variable objectif. Nous montrons comment réaliser un tel filtrage. Pour chaque activité ai ∈ A, l’énergie e(LCut(A, ai)) est calculée par l’algorithme d’Edge-Finding. Elle correspond à l’énergie nécessairement contenue dans l’intervalle [sp0, cai [. Nous raisonnons sur cette énergie : – nous comparons cette énergie à l’aire libre dans l’intervalle [sp0, cai [, – si elle est strictement supérieure à cette aire libre, cela signifie qu’elle y engendre nécessairement un dépassement de capacité, – ce dépassement peut alors également modifier la valeur de la variable objectif. En suivant ce raisonnement, pour chaque activité ai ∈ A, nous calculons une borne inférieure spécifique, notée LBV (ai), de l’objectif. Pour garder un calcul simple de chaque LBV (ai), la proposition suivante consid`ere qu’il n’y a pas de limite maximale sur le coût de chaque intervalle. Considérer les limites supérieures ne peut qu’augmenter la valeur de la borne. Notre calcul est moins fin mais nous ne faisons pas de sur-estimation de cette borne. Nous notons P V un ensemble contenant tous les intervalles utilisateurs pj ∈ P tels que spj ≤ cai . La proposition suivante donne le calcul de cette borne inférieure selon les différents param`etres costC et objC . L’exemple 35 illustre ce calcul. Proposition 5 Soit une activité ai ∈ A, et LCut(A, ai) la coupe à gauche de A par ai. Si e(LCut(A, ai)) > F reeArea(sp0, cai) alors : – si costC = max et objC = sum alors LBV (ai) =  e(LCut(A,ai))−F reeArea(sp0,cai) maxpj ∈PV (min(cai,spj+1)−spj )  , – si costC = max et objC = max alors LBV (ai) = l e(LCut(A,ai))−F reeArea(sp0,cai) cai−sp0 m , – si costC = sum et objC = sum alors LBV (ai) = e(LCut(A, ai)) − F reeArea(sp0, cai), – si costC = sum et objC = max alors LBV (ai) = l e(LCut(A,ai))−F reeArea(sp0,cai) |PV | m . Preuve. Selon la Définition 25, e(LCut(A, ai)) est l’énergie minimale nécessairement consommée avant cai . L’énergie maximale pouvant ˆetre placée dans l’intervalle [sp0, cai [ sans engendrer de dépassement est F reeArea(sp0, cai), selon la Définition 41. Ainsi, si e(LCut(A, ai)) > F reeArea(sp0, cai) alors cela implique un dépassement de capacité dont le surplus d’énergie est égal à e(LCut(A, ai))−F reeArea(sp0, cai). Cela induit une nouvelle borne inférieure sur obj. Considérons costC = max et objC = sum. Sans perte de généralité, nous considérons que toute l’énergie engendrant le dépassement (c’est à dire le surplus d’énergie) peut ˆetre placée dans l’intervalle de longueur maximale I = maxpj∈PV (min(cai , spj+1)−spj ) commen¸cant en spj . Nous nous pla¸cons alors dans l’intervalle [spj , min(cai , spj+1)[. Le surplus d’énergie est alors réparti dans cet intervalle. En effet, considérer un ou plusieurs intervalles supplémentaires ayant, par définition, une longueur inférieure ou égale à la longueur de I, m`enerait nécessairement à une somme des dépassements plus grande ou égale (nous rappelons que nous ne prenons pas en compte les limites maximales sur les coûts). Cette répartition dans 5.1. Algorithmes de filtrage 91 cet intervalle implique une hauteur de dépassement minimale égale à l e(LCut(A,ai))−F reeArea(sp0,cai) min(cai,spj+1)−spj m . Alors LBV (ai) est égal à  e(LCut(A,ai))−F reeArea(sp0,cai) maxpj ∈PV (min(cai,spj+1)−spj )  . Si costC = max et objC = max alors le surplus d’énergie provoquant le plus petit dépassement est nécessairement réparti sur le plus grand intervalle possible, c’est à dire : [sp0, cai [. Alors LBV (ai) = l e(LCut(A,ai))−F reeArea(sp0,cai) cai−sp0 m . Si costC = sum et objC = sum, la borne inférieure est la mˆeme, quelle que soit la répartition des dépassements sur les intervalles utilisateurs. Elle est alors LBV (ai) = e(LCut(A, ai))−F reeArea(sp0, cai). Enfin, si costC = sum et objC = max, en répartissant le surplus d’énergie e(LCut(A, ai)) − F reeArea(sp0, cai) sur les intervalles de P V on obtient une borne inférieure du coût maximal possible. On obtient donc LBV (ai) = l e(LCut(A,ai))−F reeArea(sp0,cai) |PV | m .  Exemple 35 Les Figures 5.11 et 5.12 donnent un exemple de ce calcul de borne inférieure. Elles représentent un probl`eme à 3 activités : a2 et a4, introduites sur la Figure 5.2, et une activité a5 que nous introduisons pour les besoins de cet exemple. On a : LCut(A, a5) = {a2, a4, a5}, et e(LCut(A, a5)) = 14. Comme e(LCut(A, a5)) > F reeArea(0, ca5) = 11, une borne inférieure LBV (a5) peut ˆetre calculée selon chacun des param`etres costC et objC tel que décrit précédemment. Dans le cas costC= max, le dépassement maximal de la capacité locale est considéré : – si objC= max nous répartissons le surplus d’énergie sur l’intervalle [sp0, ca5[, et obtenons LBV (a5) = l e(LCut(A,a5))−F reeArea(sp0,ca5) ca5−sp0 m = 1, – si objC= sum, nous le répartissons sur le plus grand intervalle utilisateur et obtenons LBV (a5) = l e(LCut(A,a5))−F reeArea(sp0,ca5) maxpj∈P (min(ca5,spj+1)−spj ) m = 1, avec P = {p0, p1} l’ensemble des intervalles utilisateur intersectés par [sp0, ca5[. Dans le cas costC= sum, le surplus d’énergie est considéré : – si objC= max, nous répartissons ce surplus entre tous les intervalles, et obtenons LBV (a5) = ⌈ e(LCut(A,a5))−F reeArea(sp0,ca5) |P | ⌉ = 2, – si objC = sum, la répartition entre les intervalles n’importe pas et nous obtenons LBV (a5) = e(LCut(A, a5)) − F reeArea(sp0, ca5) = 3. 92 5. Résolution de probl`emes d’ordonnancement cumulatif sur-contraint Algorithme 8: Algorithme de Sweep pour SoftCumulative Data : Un ensemble d’activités A, une séquence d’intervalles utilisateur P, une séquence de capacités locales Loc, une séquence de variables de coût Cost, une liste d’événements Evt. List ActT oP rune ; int sumh = 0 ; int δ ; int δ ′ ; int k ; //L’index de l’intervalle utilisateur courant evt = Evt.f irst() ; // Extraction du premier événement δ = evt.date ; // Enregistrement de sa date Evt.sortByDate() ; On ordonne les événements par date croissante, pour une date égale, on place d’abord les événements de type PROFILE, puis PRUNING, puis INTERVAL while evt 6= NULL do ai = evt.activity ;// L’activité correspondant à l’événement courant δ ′ = evt.date ; //La date de l’événement courant k = interval(δ ′ )//Chaque date est associée statiquement à l’intervalle utilisateur dans lequel elle se trouve if evt.type == P ROF ILE then if δ 6= δ ′ then if sumh > lck + costk then return fail ; foreach aj ∈ ActT oP rune do if (sumh + raj > lck + costk)&(saj ≥ caj ||((saj < caj )&[saj, caj [∩[δ, δ′ [= ∅)) then D(saj ) = D(saj )\]δ − daj , δ′ [ ;//Mise à jour de la date de début d’une activité n’ayant pas de partie obligatoire dans [δ, δ′ [ if caj < δ′ then ActT oP rune.remove(aj ) ; δ = δ ′ ; sumh+ = evt.increment; else if evt.type == INT ERV AL then if δ 6= δ ′ then if sumh > lck + costk then return fail ; foreach aj ∈ ActT oP rune do if (sumh + raj > lck + costk)&(saj ≥ caj ||((saj < caj )&[saj, caj [∩[δ, δ′ [= ∅)) then D(saj ) = D(saj )\]δ − daj , δ′ [ ;//Mise à jour de la date de début d’une activité n’ayant pas de partie obligatoire dans [δ, δ′ [ if caj < δ′ then ActT oP rune.remove(aj ) ; δ = δ ′ ; else if evt.type == P RUN ING then ActT oP rune.add(ai) ; evt = evt.next() if sumh > lck + costk then return fail ; foreach aj ∈ ActT oP rune do if (sumh + raj > lck + costk)&(saj ≥ caj ||((saj < caj )&[saj , caj[∩[δ, δ′ [= ∅)) then D(saj ) = D(saj )\]δ − daj , δ′ [ ; 5.1. Algorithmes de filtrage 93 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 Consommation Temps a5 a2 a4 ca5 D(sa5) = [0, 2] D(sa2) = [1, 2] D(sa4) = [1, 3] LCut(A, a5) D(cost0) = [0, 2] D(cost1) = [0, 2] D(cost2) = [0, 1] F reeArea(0, ca5) = 11 < e(LCut(A, a5)) = 14 LBV (a5) = 1 Figure 5.11 – Un probl`eme cumulatif relaxé avec trois activités a2, a4 et a5 telles que D(sa2) = [1, 2], D(sa4) = [1, 3], D(sa5) = [0, 2], D(ca2) = [3, 4], D(ca4) = [2, 4], D(ca5) = [2, 4], da2 = 2, da4 = 1, da5 = 2, ra2 = 2, ra4 = 4, ra5 = 3, trois intervalles utilisateur et costC = max. Comme e(LCut(A, a5)) = 14 > F reeArea(0, ca5) = 11, a5 définit une borne inférieure sur la variable objectif. Ici, P = {p0, p1}. Si objC = sum, LBV (a5) = l e(LCut(A,a5))−F reeArea(sp0,ca5) maxpj∈P (min(ca5,spj+1)−spj ) m = 1 et si objC = max, LBV (a5) = l e(LCut(A,a5))−F reeArea(sp0,ca5) ca5−sp0 m = 1 Le surplus d’énergie dans un des intervalles considérés dans l’Edge Finding de Vil´ım peut ˆetre réparti sur l’ensemble des intervalles utilisateurs intersectés par l’intervalle [sp0, cai [ courant, c’est à dire l’intervalle entre le point de temps 0 et la borne supérieure de la date de fin de l’activité ai . Des déductions sur les variables de coût peuvent ˆetre effectuées dans deux cas particuliers : – si, pour une activité ai ∈ A l’intervalle [sp0, cai [ est enti`erement contenu dans un seul intervalle utilisateur, l’intervalle p0, et que l’énergie e(LCut(A, ai)) est strictement supérieure à l’aire libre dans l’intervalle [sp0, cai [, alors cela engendre nécessairement un dépassement de capacité dans l’intervalle p0. Une borne inférieure de cost0 peut alors ˆetre déduite. Nous détaillerons son calcul plus loin, – considérons les bornes supérieures des coûts locaux. Considérons également que l’intervalle [sp0, cai [ intersecte plusieurs intervalles utilisateurs. Notons SPV l’ensemble des dates de début d’intervalle utilisateur que l’intervalle [sp0, cai [ intersecte. S’il existe un intervalle [spj , min(spj+1, cai)[ tel que spj ∈ SPV et que l’énergie e(LCut(A, ai)) soit supérieure à la somme des aires disponibles dans tous les autres intervalles [spk, min(spk+1, cai)[ tels que spk ∈ SPV et spk 6= spj , alors cela induit nécessairement un dépassement de capacité dans l’intervalle [spj , min(spj+1, cai)[. Une borne inférieure de costj peut alors ˆetre déduite. Nous donnons ci-apr`es les r`egles de filtrage dans ces deux cas. Les exemples 36 et 37 illustrent ces r`egles. R`egle de filtrage 7 Soit une activité ai ∈ A, et LBV (ai) la borne inférieure de la variable objectif calculée par la proposition 5. Si cai ∈ p0 et e(LCut(A, ai)) > F reeArea(sp0, cai), alors [cost0, LBV (ai)[ 94 5. Résolution de probl`emes d’ordonnancement cumulatif sur-contraint 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 Consommation Temps a5 a2 a4 ca5 D(sa5) = [0, 2] D(sa2) = [1, 2] D(sa4) = [1, 3] LCut(A, a5) D(cost0) = [0, 2] D(cost1) = [0, 2] D(cost2) = [0, 1] F reeArea(0, ca5) = 11 < e(LCut(A, a5)) = 14 objC = max : LBV (a5) = 2 objC = sum : LBV (a5) = 3 Figure 5.12 – Un probl`eme cumulatif relaxé de la Figure 5.11 avec costC = sum. On a e(LCut(A, a5)) = 14 > F reeArea(0, ca5) = 11, alors a5 définit une borne inférieure sur la variable objectif. Ici, P = {p0, p1}. Si objC = max, LBV (a5) = l e(LCut(A,a5))−F reeArea(sp0,ca5) |P | m = 2 et si objC = sum, LBV (a5) = e(LCut(A, a5)) − F reeArea(sp0, ca5) = 3 peut ˆetre retiré de D(cost0). Preuve. Pour une activité ai ∈ A, LBV (ai) est une borne inférieure du coût total engendré par l’énergie obligatoirement comprise dans l’intervalle [sp0, cai [. Si [sp0, cai [⊆ p0, alors ce coût est nécessairement engendré dans l’intervalle utilisateur p0. Ainsi, LBV (ai) est une borne inférieure de cost0