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. Illustration of the notion of compulsory part

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 πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽΒ [AggounBeldiceanu93], the πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ_πšπš›πšŠπš™πšŽπš£πšŽΒ [Poder02], [PoderBeldiceanuSanlaville04] and the πšπš’πšπšπš—Β [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Β [BeldiceanuGuoThiel01].

  • This is the case of the πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraint where a task is positioned to its earliest and latest starts s π‘šπ‘–π‘› and s π‘šπ‘Žπ‘₯ (see the first row and second column of FigureΒ 3.7.13).

  • This is also the case of the πšπš’πšπšπš— 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 (s x π‘šπ‘–π‘› ,s y π‘šπ‘–π‘› ), (s x π‘šπ‘Žπ‘₯ ,s y π‘šπ‘–π‘› ), (s x π‘šπ‘–π‘› ,s y π‘šπ‘Žπ‘₯ ), and (s x π‘šπ‘Žπ‘₯ ,s y π‘šπ‘Žπ‘₯ )).

  • But this is not the case of the πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ_πšπš›πšŠπš™πšŽπš£πšŽ 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 I min and I max of a task, we must also consider the valleys to further reduce I min ∩I max as explained nowΒ [PoderBeldiceanuSanlaville04]. The end of a valley is the lowest rightmost point of a valley. We must remove from I min ∩I 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.

Figure 3.7.14. Illustrating the computation of the compulsory part of a task with a valley: (A) the task shape and its valley end in red, (B) in cyan the intersection between the task positioned at its earliest start (in dashed) and its latest start (in dotted); in pink the part located (1) between the earliest and latest positions of the valley end, and (2) on top of the valley, (C) the compulsory part of the task, i.e., I min ∩I max from which we remove the pink part on top of the valley.