Next figure shows an example of a cumulative profile CumP **where at each point in time**
t the height of CumP at t does not exceed max **capa**.

![0_image_0.png](0_image_0.png)

Figure 2: Cumulated profile.

Algorithm **The sweep algorithm moves a vertical line ∆ on the time axis from one event** to the next event. In one sweep, it builds the cumulated profile incrementally and prunes activities according to this profile, in order not to exceed max capa**. An** *event* **corresponds** either to the start or the end of a compulsory part, or to the release date of an activity. All events are initially computed and sorted in increasing order according to their date. Position of ∆ is δ. At each step of the algorithm, a list ActT oP rune **contains the activities to prune.**

- Compulsory part events are used for building CumP. All events at date δ **are used**
to update the height sumh of the current rectangle in CumP**, by adding the height if**
it is the start of a compulsory part or removing the height otherwise. The first event with a date strictly greater than δ **gives the end** δ
′ of the current rectangle in **CumP**,
finally denoted by h[δ, δ′[**, sum**hi.

- Events corresponding to release dates d such that δ ≤ d < δ′ **add some new activities**
to prune, according to h[δ, δ′[, sumhi and max capa **(those activities which overlap** h[δ, δ′[, sumhi). They are added to the list **ActT oP rune**.
For each a ∈ ActT oP rune **that has no compulsory part registered in the rectangle**
h[δ, δ′[, sumhi, if its height is greater than max capa − sumh **then the algorithm prunes its**
start times so this activity doesn't overlap the current rectangle of CumP**. Then, if the due**
date of a **is less than or equal to** δ
′then a is removed from ActT oP rune**. After pruning**
activities, δ **is updated to** δ
′.

Pruning Rule 1 Let a ∈ **ActT oP rune**, which has no compulsory part recorded within the rectangle h[δ, δ′[**, sum**hi*. If* sumh+min(D(res[a])) > max **capa** *then* ]δ−min(D(dur[a])), δ′[
can be removed from D(**start**[a]).

Time complexity of the sweep technique is O(n ∗ log(n**)). Please refer to the paper for**
more details w.r.t. this algorithm [4].

## 2.1.2 Energy Reasoning On Task Intervals [8, 2, 9]

The principle of the energy reasoning is to compare the resource necessarily required by a set of activities within a given interval of points in time with the available resource within this interval. Relevant intervals are obtained from starts and ends of activities ("task intervals").

This section presents the rules implemented in Choco.

Notation 1 Given ai and aj *two activities (possibly the same) s.t.* min(D(start[ai])) < max(D(end[aj ]))*, we denote by:*