5.45. calendar

DESCRIPTIONLINKS
Origin

[BeldiceanuR00]

Constraint

πšŒπšŠπš•πšŽπš—πšπšŠπš›(π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚,π™Όπ™°π™²π™·π™Έπ™½π™΄πš‚)

Type
πš„π™½π™°πš…π™°π™Έπ™»π™°π™±π™Έπ™»π™Έπšƒπ™Έπ™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš•πš˜πš -πš’πš—πš,πšžπš™-πš’πš—πš)
Arguments
π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—πš–πšŠπšŒπš‘πš’πš—πšŽ-πšπšŸπšŠπš›,πšŸπš’πš›πšπšžπšŠπš•-πšπšŸπšŠπš›,πš’πš›πšŽπšŠπš•-πšπšŸπšŠπš›,πšπš•πšŠπšπšŽπš—πš-πš’πš—πš
π™Όπ™°π™²π™·π™Έπ™½π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš-πš’πš—πš,πšŒπšŠπš•-πš„π™½π™°πš…π™°π™Έπ™»π™°π™±π™Έπ™»π™Έπšƒπ™Έπ™΄πš‚)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš„π™½π™°πš…π™°π™Έπ™»π™°π™±π™Έπ™»π™Έπšƒπ™Έπ™΄πš‚,[πš•πš˜πš ,πšžπš™])
πš›πšŽπššπšžπš’πš›πšŽπš(π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚,[πš–πšŠπšŒπš‘πš’πš—πšŽ,πšŸπš’πš›πšπšžπšŠπš•,πš’πš›πšŽπšŠπš•,πšπš•πšŠπšπšŽπš—πš])
πš’πš—_πšŠπšπšπš›(π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚,πš–πšŠπšŒπš‘πš’πš—πšŽ,π™Όπ™°π™²π™·π™Έπ™½π™΄πš‚,πš’πš)
π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚.πšπš•πšŠπšπšŽπš—πšβ‰₯0
π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚.πšπš•πšŠπšπšŽπš—πšβ‰€1
πš›πšŽπššπšžπš’πš›πšŽπš(π™Όπ™°π™²π™·π™Έπ™½π™΄πš‚,[πš’πš,πšŒπšŠπš•])
πšπš’πšœπšπš’πš—πšŒπš(π™Όπ™°π™²π™·π™Έπ™½π™΄πš‚,πš’πš)
Purpose

Makes the link between an universal calendar and resource dependent calendars. Given a collection of machines π™Όπ™°π™²π™·π™Έπ™½π™΄πš‚ where each machine is defined by its identifier and its unavailability periods the πšŒπšŠπš•πšŽπš—πšπšŠπš› constraint maps items of real and virtual dates depending on the machine assignment as well as of the fact that we consider start (πšπš•πšŠπšπšŽπš—πš=0) or end (πšπš•πšŠπšπšŽπš—πš=1) times. Virtual dates on a given machine m do not consider the unavailability periods on m, while real dates consider all time points.

Example
πš–πšŠπšŒπš‘πš’πš—πšŽ-1πšŸπš’πš›πšπšžπšŠπš•-2πš’πš›πšŽπšŠπš•-3πšπš•πšŠπšπšŽπš—πš-0,πš–πšŠπšŒπš‘πš’πš—πšŽ-1πšŸπš’πš›πšπšžπšŠπš•-5πš’πš›πšŽπšŠπš•-6πšπš•πšŠπšπšŽπš—πš-1,πš–πšŠπšŒπš‘πš’πš—πšŽ-2πšŸπš’πš›πšπšžπšŠπš•-4πš’πš›πšŽπšŠπš•-5πšπš•πšŠπšπšŽπš—πš-0,πš–πšŠπšŒπš‘πš’πš—πšŽ-2πšŸπš’πš›πšπšžπšŠπš•-6πš’πš›πšŽπšŠπš•-9πšπš•πšŠπšπšŽπš—πš-1,πš–πšŠπšŒπš‘πš’πš—πšŽ-3πšŸπš’πš›πšπšžπšŠπš•-2πš’πš›πšŽπšŠπš•-2πšπš•πšŠπšπšŽπš—πš-0,πš–πšŠπšŒπš‘πš’πš—πšŽ-3πšŸπš’πš›πšπšžπšŠπš•-5πš’πš›πšŽπšŠπš•-5πšπš•πšŠπšπšŽπš—πš-1,πš–πšŠπšŒπš‘πš’πš—πšŽ-4πšŸπš’πš›πšπšžπšŠπš•-2πš’πš›πšŽπšŠπš•-2πšπš•πšŠπšπšŽπš—πš-0,πš–πšŠπšŒπš‘πš’πš—πšŽ-4πšŸπš’πš›πšπšžπšŠπš•-7πš’πš›πšŽπšŠπš•-9πšπš•πšŠπšπšŽπš—πš-1,πš’πš-1πšŒπšŠπš•-πš•πš˜πš -2 πšžπš™-2,πš•πš˜πš -6 πšžπš™-7,πš’πš-2πšŒπšŠπš•-πš•πš˜πš -2 πšžπš™-2,πš•πš˜πš -6 πšžπš™-7,πš’πš-3πšŒπšŠπš•-[],πš’πš-4πšŒπšŠπš•-πš•πš˜πš -3 πšžπš™-4

FigureΒ 5.45.1 illustrates the example. It present four machines with their respective unavailability periods (in grey) as well as four tasks (in blue and pink). Each item of the π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚ collection corresponds to the start or to the end of one of the previous four tasks. The πšŒπšŠπš•πšŽπš—πšπšŠπš› constraint holds since:

  • The real date 3 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[1].πš’πš›πšŽπšŠπš•=3) associated with the start (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[1].πšπš•πšŠπšπšŽπš—πš=0) of task (a) in the universal time corresponds to the virtual date 2 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[1].πšŸπš’πš›πšπšžπšŠπš•=2) on machine 1 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[1].πš–πšŠπšŒπš‘πš’πš—πšŽ=1).

  • The real date 6 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[2].πš’πš›πšŽπšŠπš•=6) associated with the end (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[2].πšπš•πšŠπšπšŽπš—πš=1) of task (a) in the universal time corresponds to the virtual date 5 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[2].πšŸπš’πš›πšπšžπšŠπš•=5) on machine 1 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[2].πš–πšŠπšŒπš‘πš’πš—πšŽ=1).

  • The real date 5 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[3].πš’πš›πšŽπšŠπš•=5) associated with the start (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[3].πšπš•πšŠπšπšŽπš—πš=0) of task (b) in the universal time corresponds to the virtual date 4 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[3].πšŸπš’πš›πšπšžπšŠπš•=4) on machine 2 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[3].πš–πšŠπšŒπš‘πš’πš—πšŽ=2).

  • The real date 9 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[4].πš’πš›πšŽπšŠπš•=9) associated with the end (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[4].πšπš•πšŠπšπšŽπš—πš=1) of task (b) in the universal time corresponds to the virtual date 6 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[4].πšŸπš’πš›πšπšžπšŠπš•=6) on machine 2 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[4].πš–πšŠπšŒπš‘πš’πš—πšŽ=2).

  • The real date 2 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[5].πš’πš›πšŽπšŠπš•=2) associated with the start (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[5].πšπš•πšŠπšπšŽπš—πš=0) of task (c) in the universal time corresponds to the virtual date 2 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[5].πšŸπš’πš›πšπšžπšŠπš•=2) on machine 3 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[5].πš–πšŠπšŒπš‘πš’πš—πšŽ=3).

  • The real date 5 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[6].πš’πš›πšŽπšŠπš•=5) associated with the end (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[6].πšπš•πšŠπšπšŽπš—πš=1) of task (c) in the universal time corresponds to the virtual date 5 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[6].πšŸπš’πš›πšπšžπšŠπš•=5) on machine 3 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[6].πš–πšŠπšŒπš‘πš’πš—πšŽ=3).

  • The real date 2 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[7].πš’πš›πšŽπšŠπš•=2) associated with the start (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[7].πšπš•πšŠπšπšŽπš—πš=0) of task (d) in the universal time corresponds to the virtual date 2 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[7].πšŸπš’πš›πšπšžπšŠπš•=2) on machine 4 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[7].πš–πšŠπšŒπš‘πš’πš—πšŽ=4).

  • The real date 9 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[8].πš’πš›πšŽπšŠπš•=9) associated with the end (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[8].πšπš•πšŠπšπšŽπš—πš=1) of task (d) in the universal time corresponds to the virtual date 7 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[8].πšŸπš’πš›πšπšžπšŠπš•=7) on machine 4 (π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚[8].πš–πšŠπšŒπš‘πš’πš—πšŽ=4).

Figure 5.45.1. Four machines with their unavailability periods as well as four tasks assigned to these machines (virtual dates mentioned in the Example slot use a bold font)
ctrs/calendar1
Typical
|π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚|>1
|π™Όπ™°π™²π™·π™Έπ™½π™΄πš‚|>1
Symmetries
  • Items of π™Έπ™½πš‚πšƒπ™°π™½πšƒπš‚ are permutable.

  • Items of π™Όπ™°π™²π™·π™Έπ™½π™΄πš‚ are permutable.

Usage

The πšŒπšŠπš•πšŽπš—πšπšŠπš› constraint is used as a channelling constraint in resource scheduling problems where resources have unavailability periods that can preempt the execution of a task. In this context two time coordinates systems are used:

  • A first coordinate system, so called the virtual coordinate system, ignores all unavailability periods on the different resources. All resource constraints are stated within this virtual coordinate system.

  • A second coordinate system, so called the real coordinate system, corresponds to the real time. All temporal constraints (e.g.,Β precedence constraints) are stated within this real coordinate system.

In this context, each task has a virtual origin, a virtual duration, a virtual end, a real origin, a real duration, a real end and the πšŒπšŠπš•πšŽπš—πšπšŠπš› constraint links together the virtual origin and the real origin as well as the virtual end and the real end. The virtual duration (i.e.,Β the real duration plus the sum of the unavailability periods crossed by the task) is linked to the virtual end and the virtual origin through an equality constraint on the difference between the virtual end and the virtual origin. The real duration is linked in a similar way to the real end and the real origin. The keyword scheduling with machine choice, calendars and preemption provides a concrete example of resource scheduling problem using the πšŒπšŠπš•πšŽπš—πšπšŠπš› constraint.

Reformulation

The πšŒπšŠπš•πšŽπš—πšπšŠπš› constraint can be reformulated into two generalised 𝚌𝚊𝚜𝚎 constraints (i.e.,Β two 𝚌𝚊𝚜𝚎 constraints augmented with linear constraints). PartΒ (A) (respectively PartΒ (B)) of FigureΒ 5.45.2 provides the dag that allows mapping the virtual start and real start (respectively the virtual end and real end) of a task. This dag can be computed directly from the arguments of the πšŒπšŠπš•πšŽπš—πšπšŠπš› constraint:

  1. We create an initial root node labelled by m and we partition the set of machines into classes of consecutive machines that all share exactly the same unavailability periods. For each such class we create an arc from the root node to a new node 𝑣𝑠 labelled by the corresponding interval of consecutive machines identifiers. In PartΒ (A) this corresponds to node m and its three outgoing arcs respectively labelled by intervals [1,2], [3,3] and [4,4].

  2. For each class of consecutive machines found previously, we label in increasing order each timepoint that is not part of an unavailability period. We create an arc from the corresponding node 𝑣𝑠 for each maximum interval of available timepoints to a new node labelled by π‘Ÿπ‘ . In PartΒ (A) this translate to:

    • For the class corresponding to machines 1 and 2 we create three outgoing arcs labelled by the time intervals [1,1], [2,4] and [5,6].

    • For the class corresponding to machine 3 we create the outgoing arc labelled by time interval [1,9].

    • For the class corresponding to machine 4 we create the two outgoing arcs labelled by the time intervals [1,2] and [3,7].

  3. For each class of consecutive machines and for each maximum interval [i,j] of available timepoints previously computed, we find out the number of unavailable timepoints b i on the same class of machines that are located before the virtual coordinate i. We create an outgoing arc from the corresponding node π‘Ÿπ‘  to a new node labelled by true (there is one single true node for the full dag). This arc is labelled by the interval [i+b i ,j+b i ] and by the linear constraint r s =v s +b i . In PartΒ (A) this translate to:

    • For the class corresponding to machines 1 and 2 and for each r s node associated with the time intervals [1,1], [2,4] and [5,6] we respectively create an outgoing arc labelled by intervals [1,1], [3,5] and [8,9]. To each of these arcs we also respectively associate the linear constraints r s =v s +0 (+0 since on machines 1 and 2 there is no unavailability period before the virtual coordinate 1), r s =v s +1 (+1 since on machines 1 and 2 there is one single unavailable timepoint before the virtual coordinate 2) and r s =v s +3 (+3 since on machines 1 and 2 there is three unavailable timepoints before the virtual coordinate 5).

    • For the class corresponding to machine 3 and for the r s node associated with the time interval [1,9] we create the outgoing arc labelled by time interval [1,9] and by r s =v s +0 (i.e.,Β since their is no unavailability period at all on machine 3).

    • For the class corresponding to machine 4 and for each r s node associated with the time intervals [1,2] and [3,7] we respectively create an outgoing arc labelled by [1,2] and [5,9]. To each of these arcs we also respectively associate the linear constraints r s =v s +0 (+0 since on machine 4 there is no unavailability period before the virtual coordinate 1) and r s =v s +2 (+2 since on machine 4 there is two unavailable timepoints before the virtual coordinate 3).

Figure 5.45.2. The two generalised 𝚌𝚊𝚜𝚎 constraints for respectively mapping (1) the virtual start and real start of a task corresponding to the Example slot as well as (2) the virtual end and real end
ctrs/calendar2
See also

common keyword: πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽΒ (scheduling constraint), πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽπšœ, πšπš’πšπšπš—Β (scheduling with machine choice, calendars and preemption), πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽΒ (scheduling constraint),

𝚐𝚎𝚘𝚜𝚝 (scheduling with machine choice, calendars and preemption).

Keywords

constraint type: predefined constraint, temporal constraint, scheduling constraint.

modelling: channelling constraint, scheduling with machine choice, calendars and preemption, assignment dimension.

modelling exercises: scheduling with machine choice, calendars and preemption.