3.7.212. Relaxation dimension

modelling: relaxation dimension A constraint that allows the modelling of 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 into the background. As a concrete example, consider a slight modification of 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 are 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 surgery 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., for each surgery 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 is set to 1 correspond to surgery tasks that are effectively scheduled, while all other parallelepipeds represent surgery tasks that are discarded. On the one hand, this model allows the direct expression of relaxation right from the beginning without introducing any extra soft constraint and without dynamically adding any constraint during search. On the other hand, a disadvantage is that the model does not directly consider an optimisation criterion like, for instance, the maximum number of tasks effectively scheduled, or the sum of the durations of the tasks effectively done; this can be modelled using extra constraints but this does not provide sharp bounds on the optimisation criterion. Nevertheless, this gives a compact model, especially in the context where additional constraints complicate 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:


FigureΒ 3.7.56 depicts a solution to the problem corresponding to the assignment πšπšŠπšœπš”πšœπš˜πš›πš’πšπš’πš—πš›πšŽπš•πšŠπš‘πšŠπšπš’πš˜πš—πšŠπš—πšŠπšŽπšœπšπš‘πšŽπšπš’πšœπšπšœπšžπš›πšπšŽπš˜πš—πš—πšžπš›πšœπšŽ t 1 o 1 =9 r 1 =1 a 1 =1s 1 =4n 11 =5,n 12 =6 t 2 o 2 =0 r 2 =2 a 2 =2s 2 =4n 2 =8 t 3 o 3 =2 r 3 =1 a 3 =1s 31 =3,s 32 =4n 31 =5,n 32 =6 t 4 o 4 =17 r 4 =1 a 4 =1s 4 =4n 41 =5,n 42 =6,n 43 =7 t 5 o 5 =16 r 5 =1 a 5 =2s 5 =3n 5 =8

During search, the 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., there is no backtrack on the values that are greater than one since we just want to reject an operation into the background).

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