We propose a relaxed version where for each rectangle we consider the maximum **costV ar**
upper bound. This entails less pruning but the complexity is amortized: the number of time points checked to obtain maximum costV ar upper bounds for the whole profile is m**, by** exploiting the sort on events into the sweep procedure.

Pruning rule 2 reduce domains of start variables from the current maximum allowed over-load in a rectangle.2 Pruning Rule 2 Let a ∈ **ActT oP rune***, which has no compulsory part recorded within the* current rectangle. If sumh+min(D(res[a])) > ideal capa+maxt∈[δ,δ′[(max(D(costV ar[t**])))**
then ]δ − min(D(dur[a])), δ′[ *can be removed from* D(**start**[a]).

Proof: For any activity which overlaps the rectangle, the maximum capacity is upper-bounded by ideal capa + max(D(costV ar[t]), t ∈ [**δ, δ**′[).

Time complexity is O(n ∗ log(n) + m), where m **is the maximum due date.** Revised task Intervals energy reasoning. **This paragraph describes the extension of**
the principle of section 2.1.2 to the SoftCumulative **global constraint.**
Feasibility Rule 2 Area(ai,aj) =
X
t∈[min(D(start[ai])),max(D(end[aj**]))[**
ideal capa + max(D(costV ar[t]))
If Pa∈S(ai
,aj
)
W(ai,aj)(a) > Area(ai,aj )*then fail.*
Proof: At each time point t there is ideal capa + max(D(**costV ar**[t])) available units.

Efficiency of rule 1 can be improved by this new computation of Area(ai,aj ) (the previous value was an over-estimation). Since activities ai **are considered by decreasing release**
date, it is possible to compute incrementally Area(ai,aj )**. Each upper bound of a variable**
in costV ar are considered once for each aj **. Time complexity is** O(n 2 + n ∗ m**), where** m is the maximum due date.

Next paragraph explains how minimum values of domains of variables in costV ar are updated during the search process.

Update costVar lower-bounds. Update of costV ar **lower bounds can be directly performed within the sweep algorithm, while the profile is computed.**
Pruning Rule 3 *Consider the current rectangle in the profile,* [**δ, δ**′[*. For each* t ∈ [**δ, δ**′[,
if sumh − ideal capa > min(D(costV ar[t])) *then* [min(D(costV ar[t])), sumh − ideal **capa**[
can be removed from D(**costV ar**[t]).

Proof: From Definitions 3 and 4.