3.7.47. 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.12. Illustration of the notion of compulsory part
ctrs/compulsory_part

FigureΒ 3.7.12 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.