3.7.200. Relaxation dimension

A constraint that allows to model constraint relaxation in the context ofΒ placement problems. This is achieved by adding an extra dimension to the placement space where objects that are really considered are in the foreground, while objects that are discarded are rejected in the background. As a concrete example, consider a slight modification on the data of the task assignment and scheduling problem that is described at the keyword entry assigning and scheduling tasks that run in parallel. In this problem the four nurses were all not available during the time periods [0,0], [7,7], [12,12] and [22,22]. We now rather consider the following unavailability periods [0,0], [8,8], [12,12] and [22,22]. Under this new hypothesis we cannot anymore schedule all the five operations tasks t 1 , t 2 , t 3 , t 4 and t 5 , i.e.,Β we get a no solution answer if we use the model described in assigning and scheduling tasks that run in parallel. In this model we are using a two -dimensional 𝚐𝚎𝚘𝚜𝚝 constraint, where the first and second dimensions respectively correspond to the time and resource axes. Now, in order to permit relaxation, we introduce a third dimension, a relaxation dimension. The idea is to map each task to a parallelepiped for which the size in the relaxation dimension is equal to one. In addition, the coordinate of a parallelepiped in the relaxation dimension is a variable taking its value in the interval [1,n], where n represents the number of operations to schedule (i.e.,Β to each operation task t i (1≀i≀n=5) we create a coordinate variable r i where r stands for relaxation. Then, all parallelepipeds for which the coordinate in the relaxation dimension if set to 1 correspond to operations that are effectively scheduled, while all other parallelepipeds represent operations that are discarded. On the one hand, this model allows to directly express relaxation right from the beginning without introducing any extra soft constraint and without dynamically adding any constraint during search. On the other hand, one disadvantage is that the model does not directly consider an optimisation criteria like, for instance, the maximum number of tasks effectively scheduled, or the sum of the duration of the tasks effectively done; this can be modelled using extra constraints but this does not provide sharp bounds on the optimisation criteria. Nevertheless, this gives a compact model, specially in the context where additional constraints make more difficult the computation of a sharp bound. Going back to the example described at the keyword entry assigning and scheduling tasks that run in parallel, we get the following three -dimensional 𝚐𝚎𝚘𝚜𝚝 constraint.


Β Β Β Β Β  βŒ©πš˜πš’πš-1πšœπš’πš-2𝚑-〈o 1 ,a 1 ,r 1 βŒͺ,πš˜πš’πš-2πšœπš’πš-2𝚑-〈o 1 ,s 1 ,r 1 βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-3πšœπš’πš-2𝚑-〈o 1 ,n 11 ,r 1 βŒͺ,πš˜πš’πš-4πšœπš’πš-2𝚑-〈o 1 ,n 12 ,r 1 βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-5πšœπš’πš-4𝚑-〈o 2 ,a 2 ,r 2 βŒͺ,πš˜πš’πš-6πšœπš’πš-4𝚑-〈o 2 ,s 2 ,r 2 βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-7πšœπš’πš-4𝚑-〈o 2 ,n 2 ,r 2 βŒͺ,πš˜πš’πš-8πšœπš’πš-3𝚑-〈o 3 ,a 3 ,r 3 βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-9πšœπš’πš-3𝚑-〈o 3 ,s 31 ,r 3 βŒͺ,πš˜πš’πš-10πšœπš’πš-3𝚑-〈o 3 ,s 32 ,r 3 βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-11πšœπš’πš-3𝚑-〈o 3 ,n 31 ,r 3 βŒͺ,πš˜πš’πš-12πšœπš’πš-3𝚑-〈o 3 ,n 32 ,r 3 βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-13πšœπš’πš-2𝚑-〈o 4 ,a 4 ,r 4 βŒͺ,πš˜πš’πš-14πšœπš’πš-2𝚑-〈o 4 ,s 4 ,r 4 βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-15πšœπš’πš-2𝚑-〈o 4 ,n 41 ,r 4 βŒͺ,πš˜πš’πš-16πšœπš’πš-2𝚑-〈o 4 ,n 42 ,r 4 βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-17πšœπš’πš-2𝚑-〈o 4 ,n 43 ,r 4 βŒͺ,πš˜πš’πš-18πšœπš’πš-6𝚑-〈o 5 ,a 5 ,r 5 βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-19πšœπš’πš-6𝚑-〈o 5 ,s 5 ,r 5 βŒͺ,πš˜πš’πš-20πšœπš’πš-6𝚑-〈o 5 ,n 5 ,r 5 βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-21πšœπš’πš-2𝚑-〈0,1,1βŒͺ,πš˜πš’πš-22πšœπš’πš-2𝚑-〈5,1,1βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-23πšœπš’πš-5𝚑-〈12,1,1βŒͺ,πš˜πš’πš-24πšœπš’πš-3𝚑-〈0,2,1βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-25πšœπš’πš-1𝚑-〈6,2,1βŒͺ,πš˜πš’πš-26πšœπš’πš-1𝚑-〈15,2,1βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-27πšœπš’πš-1𝚑-〈22,2,1βŒͺ,πš˜πš’πš-28πšœπš’πš-2𝚑-〈0,3,1βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-29πšœπš’πš-2𝚑-〈8,3,1βŒͺ,πš˜πš’πš-30πšœπš’πš-2𝚑-〈13,3,1βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-31πšœπš’πš-1𝚑-〈5,4,1βŒͺ,πš˜πš’πš-32πšœπš’πš-2𝚑-〈20,4,1βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-33πšœπš’πš-1𝚑-〈0,5,1βŒͺ,πš˜πš’πš-34πšœπš’πš-1𝚑-〈7,5,1βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-35πšœπš’πš-1𝚑-〈12,5,1βŒͺ,πš˜πš’πš-36πšœπš’πš-1𝚑-〈22,5,1βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-37πšœπš’πš-1𝚑-〈0,6,1βŒͺ,πš˜πš’πš-38πšœπš’πš-1𝚑-〈7,6,1βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-39πšœπš’πš-1𝚑-〈12,6,1βŒͺ,πš˜πš’πš-40πšœπš’πš-1𝚑-〈22,6,1βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-41πšœπš’πš-1𝚑-〈0,7,1βŒͺ,πš˜πš’πš-42πšœπš’πš-1𝚑-〈7,7,1βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-43πšœπš’πš-1𝚑-〈12,7,1βŒͺ,πš˜πš’πš-44πšœπš’πš-1𝚑-〈22,7,1βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-45πšœπš’πš-1𝚑-〈0,8,1βŒͺ,πš˜πš’πš-46πšœπš’πš-1𝚑-〈7,8,1βŒͺ,
Β Β Β Β Β Β  πš˜πš’πš-47πšœπš’πš-1𝚑-〈12,8,1βŒͺ,πš˜πš’πš-48πšœπš’πš-1𝚑-〈22,8,1βŒͺβŒͺ,
Β Β Β Β Β  βŒ©πšœπš’πš-1𝚝-〈0,0,0βŒͺπš•-〈1,1,1βŒͺ,πšœπš’πš-2𝚝-〈0,0,0βŒͺπš•-〈2,1,1βŒͺ,
Β Β Β Β Β Β  πšœπš’πš-3𝚝-〈0,0,0βŒͺπš•-〈3,1,1βŒͺ,πšœπš’πš-4𝚝-〈0,0,0βŒͺπš•-〈4,1,1βŒͺ,
Β Β Β Β Β Β  πšœπš’πš-5𝚝-〈0,0,0βŒͺπš•-〈5,1,1βŒͺ,πšœπš’πš-6𝚝-〈0,0,0βŒͺπš•-〈6,1,1βŒͺβŒͺ).

FigureΒ 3.7.46 depicts a solution to the problem corresponding to the assignment o 1 =9, r 1 =1, a 1 =1, s 1 =4, n 11 =5, n 12 =6, o 2 =1, r 2 =2, a 2 =2, s 2 =4, n 2 =8, o 3 =2, r 3 =1, a 3 =1, s 31 =3, s 32 =4, n 31 =5, n 32 =6, o 4 =17, r 4 =1, a 4 =1, s 4 =4, n 41 =5, n 42 =6, n 43 =7, o 5 =16, r 5 =1, a 5 =2, s 5 =3, n 5 =8. During search, relaxation variables r 1 , r 2 , r 3 , r 4 , r 5 are first set to value one (i.e.,Β the corresponding operations are scheduled) and then, upon backtracking, assigned to any value greater than one (i.e.,Β their is no backtrack on the values that are greater than one since we just want to reject an operation in the background).

Figure 3.7.46. A partial solution for the operation scheduling problem that maximises the number of operations actually performed where only operation t 2 is not scheduled