3.7.14. Assigning and scheduling tasks that run in parallel

Given 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 requesting the subtask to finish no later than a given date.

  • A person indicating which person performs the subtask.

Both the start and the person correspond to discrete decision variables, while the duration and the deadline are integers. Since all subtasks of a same task must run in parallel, their start, duration and deadline 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 an 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 its own calendar defining its unavailability. On the one hand, let us assume we have two anaesthetists, two surgeons and four nurses that are 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 operation 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 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 (i.e., 1 since it requires one person). The coordinates of the leftmost lower 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,

𝚐𝚎𝚘𝚜𝚝(2,

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

Figure 3.7.1. A solution for the operation scheduling problem using four nurses (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/assigning_tasks_in_parallel

A deadline constraint for an operation 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 o 1 =10, a 1 =1, s 1 =3, n 11 =5, n 12 =6, o 2 =8, a 2 =2, s 2 =4, n 2 =7, o 3 =2, a 3 =1, s 31 =3, s 32 =4, n 31 =5, n 32 =6, o 4 =17, a 4 =1, s 4 =4, n 41 =5, n 42 =6, n 43 =7, o 5 =16, a 5 =2, s 5 =3, n 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 operations to schedule with respect to the number of anaesthetists, surgeons and nurses and to their unavailability periods.