3.7.213. Scheduling with machine choice, calendars and preemption

A set of constraints that can be used for modelling aΒ scheduling problem where:

  • We have tasks that have both to be assigned to machine and time.

  • Each task has a fixed duration.

  • Machines can run at most one task at a given instant.

  • Each machine has its own fixed unavailability periods (i.e.,Β a calendar of unavailability periods).

  • AnΒ unavailability period that allows (respectively forbids) a task to be interrupted and resumed just after is calledΒ crossable (respectivelyΒ non -crossable). A task that can be (respectively cannot be) interrupted by a crossable unavailability period is calledΒ resumable (respectively non -resumable).

  • We have a precedence constraint between specific pairs of tasks. Each precedence enforces the fact that a given task ends before the start of another given task.

This model illustrates the use of two time coordinates systems:

  • The first coordinate system, so called the virtual coordinate system, does not consider at all the crossable unavailability periods associated with the different machines. Since resumable tasks can be preempted by machine crossable unavailability, all resource scheduling constraints (i.e.,Β πšπš’πšπšπš—, 𝚐𝚎𝚘𝚜𝚝) are expressed within this first coordinate system. This stands from the fact that resource scheduling constraints like πšπš’πšπšπš— or 𝚐𝚎𝚘𝚜𝚝 do not support preemption.

  • The second coordinate system, so called the real coordinate system, considers all timepoints whether they correspond or not to crossable unavailability periods. All temporal constraints (i.e.,Β precedence constraints represented by πš•πšŽπšš constraints in this model) are expressed with respect to this second coordinate system.

Consequently, each task has a start and an end that are expressed within the virtual coordinate system as well as within the real coordinate system.

  • Each task, whether it is resumable or not, is passed to the resource scheduling constraints as well as to the precedence constraints. In addition, we represent each non -crossable unavailability period as a fixed task that is also passed to the resource scheduling constraints.

  • The πšŒπšŠπš•πšŽπš—πšπšŠπš› constraint ensures the link between variables (i.e.,Β the start and the end of the tasks no matter whether they are resumable or not) expressed in these two coordinate systems with respect to the crossable unavailability periods.

We now provide the corresponding detailed model. Given:

  1. A set of machines β„³={m 1 ,m 2 ,...,m p }, where each machine has a list of fixed unavailability periods. An unavailability u i is defined by the following attributes:

    1. The crossable flag c i tells whether unavailability u i is crossable (c i =1) or not (c i =0).

    2. The machine r i indicates the machine (i.e.,Β a value in [1,p]) to which unavailability u i corresponds (i.e.,Β since different machines may have different unavailability periods).

    3. The start s i of the unavailability u i which indicates the first unavailable timepoint of the unavailability.

    4. The end e i of the unavailability u i which gives the last unavailable timepoint of the unavailability.

  2. A set of tasks 𝒯={t 1 ,t 2 ,...,t n }, where each task t i (with i∈[1,n]) has the following attributes which are all domain variables except the resumable flag and the virtual duration:

    1. The resumable flag r i tells whether task t i is resumable (r i =1) or not (r i =0).

    2. The machine m i indicates the machine (i.e.,Β a value in [1,p]) to which task t i will be assigned.

    3. The virtual start 𝑣𝑠 i gives the start of task t i in the virtual coordinate system.

    4. The virtual duration 𝑣𝑑 i corresponds to the duration of task t i without counting the eventual unavailability periods crossed by task t i .

    5. The virtual end 𝑣𝑒 i provides the end of task t i in the virtual coordinate system. We have that 𝑣𝑠 i +𝑣𝑑 i =𝑣𝑒 i .

    6. The real start π‘Ÿπ‘  i gives the start of task t i in the real coordinate system.

    7. The real duration π‘Ÿπ‘‘ i corresponds to the duration of task t i including the eventual unavailability periods crossed by task t i . When task t i is non -resumable (i.e.,Β r i =0) its real duration is equal to its virtual duration (i.e.,Β π‘Ÿπ‘‘ i =𝑣𝑑 i ).

    8. The real end π‘Ÿπ‘’ i indicates the end of task t i in the real coordinate system. We have that π‘Ÿπ‘  i +π‘Ÿπ‘‘ i =π‘Ÿπ‘’ i .

The link between the virtual starts (respectively virtual ends) and the real starts (respectively real ends) of the different tasks of 𝒯 is ensured by a πšŒπšŠπš•πšŽπš—πšπšŠπš›(π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚,π™Όπ™°π™²π™·π™Έπ™½π™΄πš‚) constraint. More precisely, for each task t i (with i∈[1,n]), no matter whether it is resumable or not, we create the following items for the collection π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚:

πš–πšŠπšŒπš‘πš’πš—πšŽ-m i πšŸπš’πš›πšπšžπšŠπš•-𝑣𝑠 i πš’πš›πšŽπšŠπš•-π‘Ÿπ‘  i πšπš•πšŠπšπšŽπš—πš-0,πš–πšŠπšŒπš‘πš’πš—πšŽ-m i πšŸπš’πš›πšπšžπšŠπš•-𝑣𝑒 i πš’πš›πšŽπšŠπš•-π‘Ÿπ‘’ i πšπš•πšŠπšπšŽπš—πš-1.

The first item links the virtual and the real start of task t i , while the second item relates the virtual and real ends. For each machine m i (with i∈[1,p]) and its corresponding list of crossable unavailability periods, denoted π‘π‘Ÿπ‘œπ‘ π‘ π‘Žπ‘π‘™π‘’_π‘’π‘›π‘Žπ‘£π‘Žπ‘–π‘™π‘Žπ‘π‘–π‘™π‘–π‘‘π‘¦ i , we create the following item of the collection π™Όπ™°π™²π™·π™Έπ™½π™΄πš‚:

πš’πš-iπšŒπšŠπš•-π‘π‘Ÿπ‘œπ‘ π‘ π‘Žπ‘π‘™π‘’_π‘’π‘›π‘Žπ‘£π‘Žπ‘–π‘™π‘Žπ‘π‘–π‘™π‘–π‘‘π‘¦ i .

To express the resource constraint, i.e.,Β the fact that two tasks assigned to the same machine should not overlap in time, we use a 𝚐𝚎𝚘𝚜𝚝(2,π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚,πš‚π™±π™Ύπš‡π™΄πš‚) constraint. For each task t i (with i∈[1,n]) we create one item for the π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚ collection as well as one item for the πš‚π™±π™Ύπš‡π™΄πš‚ collection:

πš˜πš’πš-iπšœπš’πš-i𝚑-〈m i ,𝑣𝑠 i βŒͺ,πšœπš’πš-i𝚝-〈0,0βŒͺπš•-〈1,𝑣𝑑 i βŒͺ.

The first item corresponds to an object with i as unique identifier, with a rectangular shape identifier i and with m i ,𝑣𝑠 i as the coordinates of its leftmost lower corner. The second item corresponds to a rectangular shape with i as unique identifier, 〈0,0βŒͺ as shift offset with respect to its leftmost lower corner, and 〈1,𝑣𝑑 i βŒͺ as the sizes of the rectangular shape.

Similarly, to express the fact that each task does not overlap a non -crossable unavailability period, we create for each non -crossable unavailability period i one item for the π™Ύπ™±π™Ήπ™΄π™²πšƒπš‚ collection as well as one item for the πš‚π™±π™Ύπš‡π™΄πš‚ collection:

πš˜πš’πš-n+iπšœπš’πš-n+i𝚑-〈r i ,s i βŒͺ,πšœπš’πš-n+i𝚝-〈0,0βŒͺπš•-〈1,e i -s i +1βŒͺ.

Finally, a precedence constraint between two distinct tasks t i and t j (with i,j∈[1,n]) is modelled by an inequality constraint between the real end of task t i and the real start of task t j , namely π‘Ÿπ‘’ i β‰€π‘Ÿπ‘  j . FigureΒ 3.7.48 provides a toy example of such problem with:

  • Four machines, numbered from 1 to 4, where:

    • Machine m 1 has two crossable unavailability periods respectively corresponding to intervals [2,2] and [6,7].

    • Machine m 2 has two crossable unavailability periods respectively corresponding to intervals [2,2] and [6,7], as well as one non -crossable unavailability period corresponding to interval [3,3].

    • Machine m 3 has one single non -crossable unavailability corresponding to interval [6,8].

    • Machine m 4 has one single crossable unavailability period corresponding to interval [3,4].

  • Five tasks, numbered from 1 to 5, where:

    • Task t 1 is a non -resumable task that has a virtual duration of 3.

    • Task t 2 is a resumable task that has a virtual duration of 2.

    • Task t 3 is a non -resumable task that has a virtual duration of 3.

    • Task t 4 is a resumable task that has a virtual duration of 5.

    • Task t 5 is a resumable task that has a virtual duration of 2.

  • Finally, (1)Β all five tasks should not overlap, (2)Β task t 3 should precedes task t 2 and (3)Β task t 1 should precedes task t 5 .

Figure 3.7.48. Illustration of the scheduling problem with crossable and non-crossable unavailability periods as well as with resumable and non-resumable tasks: part (A) gives the real time coordinate system where all precedence constraints are stated, while part (B) provides the virtual time coordinate system – from which all crossable unavailability periods are removed – where the non-overlapping constraint is stated
ctrs/scheduling_with_calendars

A survey on machine scheduling problems with unavailability constraints both in the deterministic and stochastic cases can be found inΒ [SaidyTaghaviFard08]. Unavailability can have multiple causes such as:

  • In the context of production scheduling, machine unavailability corresponds to accepted orders that were already scheduled for a given date. This can typically corresponds to unavailability periods at the beginning of the planning horizon. Preemptive maintenance can also be another cause of machine unavailability.

  • In the context of timetabling, unavailability periods may come from work regulation which enforces not to work in a continuous way more than a given limit. Unavailability periods may also come from scheduled meetings during the working day.

  • In the context of distributed computing where cputime is donated for performing huge tasks, machines are typically partially availableΒ [DiedrichJansenSchwarzTrystram09].