### 3.7.49. Compulsory part

A constraint for which the filtering algorithm may use the notion of compulsory part. The notion of compulsory part was introduced by A.Β Lahrichi within the context of cumulativeΒ scheduling problemsΒ [Lahrichi79],Β [Lahrichi82],Β [Lahrichi82a] as well as within the context of rectanglesΒ placement problemsΒ [LahrichiGondran84]. Within these two contexts, the compulsory part respectively corresponds to the intersection of all feasible instances of a task or to the intersection of all feasible instances of a rectangle.

FigureΒ 3.7.13 illustrates the notion of compulsory part in the context ofΒ scheduling andΒ placement problems. The first, second and third rows respectively corresponds to the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$Β [AggounBeldiceanu93], the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi £\pi }$Β [Poder02], [PoderBeldiceanuSanlaville04] and the $\mathrm{\pi \pi \pi \pi \pi }$Β [BeldiceanuGuoThiel01] constraints. The first, second and third columns respectively correspond to the shape of the object for which we compute the compulsory part, to the extreme positions of the object and to the corresponding compulsory part. When both, the shape of an object is convex and the domain of its origin is also convex, we do not need to consider all feasible instances of the object to compute its compulsory part. We only need to position the object to the extreme positions of its domain and to compute the intersection to get its compulsory part

• This is the case of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint where a task is positioned to its earliest and latest starts ${s}_{\mathrm{\pi \pi \pi }}$ and ${s}_{\mathrm{\pi \pi \pi ₯}}$ (see the first row and second column of FigureΒ 3.7.13).

• This is also the case of the $\mathrm{\pi \pi \pi \pi \pi }$ constraint where an orthotope is positioned to its $2Β·n$ extreme positions, where $n$ is the number of dimensions of the placement space (see the third row and second column of FigureΒ 3.7.13, where the origin of the rectangle is fixed to the extreme positions $\left({s}_{{x}_{\mathrm{\pi \pi \pi }}},{s}_{{y}_{\mathrm{\pi \pi \pi }}}\right)$, $\left({s}_{{x}_{\mathrm{\pi \pi \pi ₯}}},{s}_{{y}_{\mathrm{\pi \pi \pi }}}\right)$, $\left({s}_{{x}_{\mathrm{\pi \pi \pi }}},{s}_{{y}_{\mathrm{\pi \pi \pi ₯}}}\right)$, and $\left({s}_{{x}_{\mathrm{\pi \pi \pi ₯}}},{s}_{{y}_{\mathrm{\pi \pi \pi ₯}}}\right)$).

• But this is not the case of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi £\pi }$ constraint with a task that has a valley, i.e.Β a task for which a resource consumption decrease is followed by a resource consumption increase. In addition of computing the intersection between the two extreme positions ${\mathrm{I}}^{\mathrm{min}}$ and ${\mathrm{I}}^{\mathrm{max}}$ of a task, we must also consider the valleys to further reduce ${\mathrm{I}}^{\mathrm{min}}\beta ©{\mathrm{I}}^{\mathrm{max}}$ as explained nowΒ [PoderBeldiceanuSanlaville04]. The end of a valley is the lowest rightmost point of a valley. We must remove from ${\mathrm{I}}^{\mathrm{min}}\beta ©{\mathrm{I}}^{\mathrm{max}}$ all parts that are located both (1)Β between the earliest start and latest end of the valley end, (2)Β and on top of the valley. FigureΒ 3.7.14 illustrates this point for the task used in the second row and first column of FigureΒ 3.7.13.