3.7.15. Assigning and scheduling tasks that run in parallel

modelling: assigning and scheduling tasks that run in parallel Consider a set of tasks defined by a set of subtasks, where each subtask has the following attributes:

  • A start telling when the subtask starts.

  • A duration giving the duration of the subtask.

  • A deadline indicating the date by which the subtask must be finished.

  • A person indicating which person performs the subtask.

Both the start and the person correspond to decision variables, while the duration and the deadline are integers. Since all subtasks of a same task must run in parallel, their starts, durations and deadlines are identical. Since a person can perform at most one task at each timepoint, persons assigned to the subtasks of a same task must all be distinct. We also assume that a subtask cannot be preempted.

As an instance of this pattern, consider the problem of scheduling surgical operations in a hospital. Each surgery corresponds to a task that requires a number of persons with specific skills; these persons will all work together during the operation (e.g.,Β typically an anaesthetist, a surgeon and one or several nurses). Moreover, each person has his own calendar defining his unavailability. On the one hand, let us assume we have two anaesthetists, two surgeons and four nurses, labelled from 1 to 8. Each of them has the following unavailability over the time horizon [0,24]:

  • The first anaesthetist is not available during the time periods [0,1], [5,6], and [12,16].

  • The second anaesthetist is not available during the time periods [0,2], [6,6], [15,15], and [22,22].

  • The first surgeon is not available during the time periods [0,1], [8,9], and [13,14].

  • The second surgeon is not available during the time periods [5,5], and [20,21].

  • The four nurses are all not available during the time periods [0,0], [7,7], [12,12], and [22,22].

On the other hand, let us suppose we have to schedule five surgery tasks, each of them requiring a specific team:

  • Task t 1 needs one anaesthetist, one surgeon and two nurses during two consecutive time slots.

  • Task t 2 needs one anaesthetist, one surgeon and one nurse during four consecutive time slots.

  • Task t 3 needs one anaesthetist, two surgeons and two nurses during three consecutive time slots.

  • Task t 4 needs one anaesthetist, one surgeon and three nurses during two consecutive time slots.

  • Task t 5 needs one anaesthetist, one surgeon and one nurse during six consecutive time slots.

Moreover, tasks t 1 , t 2 , t 3 , t 4 and t 5 must be respectively completed no later than timepoint 12, 15, 24, 24 and 24. The problem is modelled by using a two-dimensional 𝚐𝚎𝚘𝚜𝚝 constraint, where the first and second dimensions respectively correspond to the time and resource axes. For each person required by a task we create a rectangle of length corresponding to the necessary duration and of height 1 (since it requires one person). The coordinates of the lower left point of the rectangle correspond to the start of the corresponding task as well as to the person that will be assigned to the subtask (i.e., a value between 1 and 2 for an anaesthetist, a value between 3 and 4 for a surgeon, and a value between 5 and 8 for a nurse). Both the start and the person correspond to a domain variable. Each unavailability period of an anaesthetist, a surgeon and a nurse is modelled by introducing a fixed rectangle (i.e., its coordinates are set to the start of the unavailability period and to the person to which the unavailability belongs; its duration is set to the duration of the unavailability period) that prevent tasks overlapping the corresponding time period for a specific person. This leads to the following 𝚐𝚎𝚘𝚜𝚝 constraint,

ctrs/preface-140-tikz

Figure 3.7.1. A solution to the surgery scheduling problem using four nurses where the start and the latest completion time of each task are respectively shown in bold and in red; a solution using only 3 nurses can be obtained by starting task t 4 at instant 13 and by assigning it to the second anaesthetist rather than to the first one.
ctrs/preface-141-tikz

A deadline constraint for a surgery starting at o and of duration d is modelled by a precedence constraint of the form o+dβ‰€π‘‘π‘’π‘Žπ‘‘π‘™π‘–π‘›π‘’. This leads to the five constraints o 1 +2≀12, o 2 +4≀15, o 3 +3≀24, o 4 +2≀24, and o 5 +6≀24. Finally, we break symmetry on the assignment variables corresponding to a group of similar persons. In the example, the four nurses are similar since (1)Β they all have exactly the same unavailability periods, and since (2)Β no task requires a specific nurse. For each task using more than one nurse (i.e., tasks t 1 , t 3 , and t 4 ) this leads to a chain of strict inequalities, i.e., n 11 <n 12 , n 31 <n 32 , and n 41 <n 42 <n 43 . FigureΒ 3.7.1 depicts a solution to the problem corresponding to the assignment πšπšŠπšœπš”πšœπš˜πš›πš’πšπš’πš—πšŠπš—πšŠπšŽπšœπšπš‘πšŽπšπš’πšœπšπšœπšžπš›πšπšŽπš˜πš—πš—πšžπš›πšœπšŽ t 1 o 1 =10 a 1 =1s 1 =3n 11 =5,n 12 =6 t 2 o 2 =8 a 2 =2s 2 =4n 2 =7 t 3 o 3 =2 a 3 =1s 31 =3,s 32 =4n 31 =5,n 32 =6 t 4 o 4 =17 a 4 =1s 4 =4n 41 =5,n 42 =6,n 43 =7 t 5 o 5 =16 a 5 =2s 5 =3n 5 =8

The entry corresponding to the keyword relaxation dimension shows how to express relaxation in the context of over-constrained problems where we have too many surgeries to schedule with respect to the number of anaesthetists, surgeons and nurses and to their unavailability periods.