3.7.16. Assignment dimension

A constraint for handlingΒ placement problems in the broad sense involving an assignment dimension (i.e.,Β one of the attribute of a collection passed as argument indicates the assignment dimension β€” the attribute is shown in parenthesis for each constraint). In order to illustrate the notion of assignment dimension let us first introduce three typical examples described in FigureΒ 3.7.2:

  • PartΒ (A) of FigureΒ 3.7.2 considers aΒ scheduling problem where we have both to assign a task to a machine and to fix its start to a time -point, in such a way that two tasks that overlap in time are not assigned to the same machine. In this context the different potential machines where tasks can be assigned is called an assignment dimension. This problem can be directly modelled by a πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽπšœ or a 𝚐𝚎𝚘𝚜𝚝 constraint.

  • PartΒ (B) of FigureΒ 3.7.2 considers aΒ placement problem where we have both to assign a rectangle to a rectangular piece and to locate it within the selected rectangular piece. In this context the different potential rectangular pieces where rectangles can be placed is also called an assignment dimension. Note that in suchΒ placement problems the size of an object in an assignment dimension is always equal to one. This problem can be directly modelled by a πšπš’πšπšπš— or a 𝚐𝚎𝚘𝚜𝚝 constraint.

  • PartΒ (C) of FigureΒ 3.7.2 considers aΒ placement problem where we have both to assign a box to a Β container and to place it within the selected Β container. In this context the different potential Β containers where boxes can be packed is also called an assignment dimension. Note that in suchΒ placement problems the size of an object in an assignment dimension is always equal to one. This problem can be directly modelled by a πšπš’πšπšπš— or a 𝚐𝚎𝚘𝚜𝚝 constraint.

Figure 3.7.2. Three illustrations of the notion of assignment dimension where the assignment dimension is stressed in bold
ctrs/assignment_dimension

Using constraints like πšŒπš˜πš•πš˜πšžπš›πšŽπš_πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽπšœ, πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽπšœ, πšπš’πšπšπš—, 𝚐𝚎𝚘𝚜𝚝 or 𝚐𝚎𝚘𝚜𝚝_πšπš’πš–πšŽ allows to model directly with one single global constraint such problems without knowing in advance to which machine, to which rectangular piece, to which Β container, a task, a rectangle, a box will be assigned. For each object the potential values of its assignment variable provide the machines, the rectangular pieces, the Β containers to which the object can possibly be assigned. Note that this allows to avoid 0-1 variables for modelling such problems.

Within constraints like πš’πš—πšπšŽπš›πšŸπšŠπš•_πšŠπš—πš_πšŒπš˜πšžπš—πš or πš’πš—πšπšŽπš›πšŸπšŠπš•_πšŠπš—πš_πšœπšžπš– the concept of assignment dimension is extended from the fact that a variable is assigned a value to the fact that a variable is assigned an interval (i.e.,Β a value in an interval).