

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

then we can determine that activity i cannot be scheduled to run during time t. If the earliest start time of activity i, minD s[i] means that the activity cannot be scheduled completely before time t, i.e. minD s[i] + d[i] > t, we can update the earliest start time to be t + 1, similarly if the lastest start time of the activity means that the activity cannot be scheduled completely after t , i.e. maxD s[i] ≤ t then we can update the latest start time to be t − d[i]. For a full description of timetable propagation for cumulative see e.g. [27].

Example 3. Consider the cumulative constraint of Example 2 where the domains of the start times are now D(sa) = [ 1 .. 2 ], D(sb) = [ 0 .. 3 ], D(sc) = [ 3 .. 5 ], D(sd) = [ 0 .. 2 ],
D(se) = [ 0 .. 4 ]. Then there is compulsory parts of activities a and b in the ranges
[2..2] and [3..4] respectively shown in Figure 2(b) in red. No other activities have a compulsory part. Hence the red contour illustrates the resource usage profile. Since activity b cannot be scheduled in parallel with activity a, and the earliest start time of activity b, 0, means that the activity cannot be scheduled before activity a we can reduce the domain of the start time for activity b to the singleton [ 3 .. 3 ]. This is illustrated in Figure 2(b). The opposite holds for activity a that cannot be run after activity b, hence the domain of its start time shrinks to the singleton range [ 1 .. 1 ]. Once we make these changes the compulsory parts of the activities a and b increase to the ranges [ 1 .. 2 ] and