5.107. disjoint_tasks

DESCRIPTIONLINKSGRAPH
Origin

Derived from πšπš’πšœπš“πš˜πš’πš—πš.

Constraint

πšπš’πšœπš“πš˜πš’πš—πš_πšπšŠπšœπš”πšœ(πšƒπ™°πš‚π™Ίπš‚1,πšƒπ™°πš‚π™Ίπš‚2)

Arguments
πšƒπ™°πš‚π™Ίπš‚1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš˜πš›πš’πšπš’πš—-πšπšŸπšŠπš›,πšπšžπš›πšŠπšπš’πš˜πš—-πšπšŸπšŠπš›,πšŽπš—πš-πšπšŸπšŠπš›)
πšƒπ™°πš‚π™Ίπš‚2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš˜πš›πš’πšπš’πš—-πšπšŸπšŠπš›,πšπšžπš›πšŠπšπš’πš˜πš—-πšπšŸπšŠπš›,πšŽπš—πš-πšπšŸπšŠπš›)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽ_𝚊𝚝_πš•πšŽπšŠπšœπš(2,πšƒπ™°πš‚π™Ίπš‚1,[πš˜πš›πš’πšπš’πš—,πšπšžπš›πšŠπšπš’πš˜πš—,πšŽπš—πš])
πšƒπ™°πš‚π™Ίπš‚1.πšπšžπš›πšŠπšπš’πš˜πš—β‰₯0
πšƒπ™°πš‚π™Ίπš‚1.πš˜πš›πš’πšπš’πš—β‰€πšƒπ™°πš‚π™Ίπš‚1.πšŽπš—πš
πš›πšŽπššπšžπš’πš›πšŽ_𝚊𝚝_πš•πšŽπšŠπšœπš(2,πšƒπ™°πš‚π™Ίπš‚2,[πš˜πš›πš’πšπš’πš—,πšπšžπš›πšŠπšπš’πš˜πš—,πšŽπš—πš])
πšƒπ™°πš‚π™Ίπš‚2.πšπšžπš›πšŠπšπš’πš˜πš—β‰₯0
πšƒπ™°πš‚π™Ίπš‚2.πš˜πš›πš’πšπš’πš—β‰€πšƒπ™°πš‚π™Ίπš‚2.πšŽπš—πš
Purpose

Each task of the collection πšƒπ™°πš‚π™Ίπš‚1 should not overlap any task of the collection πšƒπ™°πš‚π™Ίπš‚2. Two tasks overlap if they have an intersection that is strictly greater than zero.

Example
πš˜πš›πš’πšπš’πš—-6πšπšžπš›πšŠπšπš’πš˜πš—-5πšŽπš—πš-11,πš˜πš›πš’πšπš’πš—-8πšπšžπš›πšŠπšπš’πš˜πš—-2πšŽπš—πš-10,πš˜πš›πš’πšπš’πš—-2πšπšžπš›πšŠπšπš’πš˜πš—-2πšŽπš—πš-4,πš˜πš›πš’πšπš’πš—-3πšπšžπš›πšŠπšπš’πš˜πš—-3πšŽπš—πš-6,πš˜πš›πš’πšπš’πš—-12πšπšžπš›πšŠπšπš’πš˜πš—-1πšŽπš—πš-13

FigureΒ 5.107.1 displays the two groups of tasks (i.e.,Β the tasks of πšƒπ™°πš‚π™Ίπš‚1 and the tasks of πšƒπ™°πš‚π™Ίπš‚2). Since no task of the first group overlaps any task of the second group, the πšπš’πšœπš“πš˜πš’πš—πš_πšπšŠπšœπš”πšœ constraint holds.

Figure 5.107.1. Fixed tasks of the πšπš’πšœπš“πš˜πš’πš—πš_πšπšŠπšœπš”πšœ constraint
ctrs/disjoint_tasks1
Typical
|πšƒπ™°πš‚π™Ίπš‚1|>1
πšƒπ™°πš‚π™Ίπš‚1.πšπšžπš›πšŠπšπš’πš˜πš—>0
|πšƒπ™°πš‚π™Ίπš‚2|>1
πšƒπ™°πš‚π™Ίπš‚2.πšπšžπš›πšŠπšπš’πš˜πš—>0
Symmetries
  • Arguments are permutable w.r.t. permutation (πšƒπ™°πš‚π™Ίπš‚1,πšƒπ™°πš‚π™Ίπš‚2).

  • Items of πšƒπ™°πš‚π™Ίπš‚1 are permutable.

  • Items of πšƒπ™°πš‚π™Ίπš‚2 are permutable.

  • One and the same constant can be added to the πš˜πš›πš’πšπš’πš— and πšŽπš—πš attributes of all items of πšƒπ™°πš‚π™Ίπš‚1 and πšƒπ™°πš‚π™Ίπš‚2.

Remark

Despite the fact that this is not an uncommon constraint, it cannot be modelled in a compact way with one single πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraint. But it can be expressed by using the πšŒπš˜πš•πš˜πšžπš›πšŽπš_πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraint: We assign a first colour to the tasks of πšƒπ™°πš‚π™Ίπš‚1 as well as a second distinct colour to the tasks of πšƒπ™°πš‚π™Ίπš‚2. Finally we set up a limit of 1 for the maximum number of distinct colours allowed at each time point.

Reformulation

The πšπš’πšœπš“πš˜πš’πš—πš_πšπšŠπšœπš”πšœ constraint can be expressed in term of |πšƒπ™°πš‚π™Ίπš‚1|Β·|πšƒπ™°πš‚π™Ίπš‚2| reified constraints. For each task πšƒπ™°πš‚π™Ίπš‚1[i] (i∈[1,|πšƒπ™°πš‚π™Ίπš‚1|]) and for each task πšƒπ™°πš‚π™Ίπš‚2[j] (j∈[1,|πšƒπ™°πš‚π™Ίπš‚2|]) we generate a reified constraint of the form πšƒπ™°πš‚π™Ίπš‚1[i].πšŽπš—πšβ‰€πšƒπ™°πš‚π™Ίπš‚2[j].πš˜πš›πš’πšπš’πš—βˆ¨πšƒπ™°πš‚π™Ίπš‚2[j].πšŽπš—πšβ‰€πšƒπ™°πš‚π™Ίπš‚1[i].πš˜πš›πš’πšπš’πš—. In addition we also state for each task an arithmetic constraint that states that the end of a task is equal to the sum of its origin and its duration.

Systems

disjoint in Choco.

See also

generalisation: πšŒπš˜πš•πš˜πšžπš›πšŽπš_πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽΒ (tasks colours and limit on maximum number of colours in parallel are explicitly given).

specialisation: πšπš’πšœπš“πš˜πš’πš—πšΒ (πšπšŠπšœπš” replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ).

Keywords

constraint type: scheduling constraint, temporal constraint.

geometry: non-overlapping.

Arc input(s)

πšƒπ™°πš‚π™Ίπš‚1

Arc generator
π‘†πΈπΏπΉβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπšŠπšœπš”πšœ1)

Arc arity
Arc constraint(s)
πšπšŠπšœπš”πšœ1.πš˜πš›πš’πšπš’πš—+πšπšŠπšœπš”πšœ1.πšπšžπš›πšŠπšπš’πš˜πš—=πšπšŠπšœπš”πšœ1.πšŽπš—πš
Graph property(ies)
𝐍𝐀𝐑𝐂=|πšƒπ™°πš‚π™Ίπš‚1|

Arc input(s)

πšƒπ™°πš‚π™Ίπš‚2

Arc generator
π‘†πΈπΏπΉβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπšŠπšœπš”πšœ2)

Arc arity
Arc constraint(s)
πšπšŠπšœπš”πšœ2.πš˜πš›πš’πšπš’πš—+πšπšŠπšœπš”πšœ2.πšπšžπš›πšŠπšπš’πš˜πš—=πšπšŠπšœπš”πšœ2.πšŽπš—πš
Graph property(ies)
𝐍𝐀𝐑𝐂=|πšƒπ™°πš‚π™Ίπš‚2|

Arc input(s)

πšƒπ™°πš‚π™Ίπš‚1 πšƒπ™°πš‚π™Ίπš‚2

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπšŠπšœπš”πšœ1,πšπšŠπšœπš”πšœ2)

Arc arity
Arc constraint(s)
β€’ πšπšŠπšœπš”πšœ1.πšπšžπš›πšŠπšπš’πš˜πš—>0
β€’ πšπšŠπšœπš”πšœ2.πšπšžπš›πšŠπšπš’πš˜πš—>0
β€’ πšπšŠπšœπš”πšœ1.πš˜πš›πš’πšπš’πš—<πšπšŠπšœπš”πšœ2.πšŽπš—πš
β€’ πšπšŠπšœπš”πšœ2.πš˜πš›πš’πšπš’πš—<πšπšŠπšœπš”πšœ1.πšŽπš—πš
Graph property(ies)
𝐍𝐀𝐑𝐂=0

Graph model

π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡ is used in order to generate the arcs of the graph between all the tasks of the collection πšƒπ™°πš‚π™Ίπš‚1 and all tasks of the collection πšƒπ™°πš‚π™Ίπš‚2. The first two graph constraints respectively enforce for each task of πšƒπ™°πš‚π™Ίπš‚1 and πšƒπ™°πš‚π™Ίπš‚2 the fact that the end of a task is equal to the sum of its origin and its duration. The arc constraint of the third graph constraint depicts the fact that two tasks overlap. Therefore, since we use the graph property 𝐍𝐀𝐑𝐂 = 0 the final graph associated with the third graph constraint will be empty and no task of πšƒπ™°πš‚π™Ίπš‚1 will overlap any task of πšƒπ™°πš‚π™Ίπš‚2. FigureΒ 5.107.2 shows the initial graph of the third graph constraint associated with the Example slot. Because of the graph property 𝐍𝐀𝐑𝐂 = 0 the corresponding final graph is empty.

Figure 5.107.2. Initial graph of the πšπš’πšœπš“πš˜πš’πš—πš_πšπšŠπšœπš”πšœ constraint (the final graph is empty)
ctrs/disjoint_tasksA
Signature

Since πšƒπ™°πš‚π™Ίπš‚1 is the maximum number of arcs of the final graph associated with the first graph constraint we can rewrite 𝐍𝐀𝐑𝐂 = |πšƒπ™°πš‚π™Ίπš‚1|. This leads to simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.

We can apply a similar remark for the second graph constraint.

Finally, since 0 is the smallest number of arcs of the final graph we can rewrite 𝐍𝐀𝐑𝐂 = 0 to 𝐍𝐀𝐑𝐂 ≀ 0. This leads to simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Μ².