5.336. track

DESCRIPTIONLINKSGRAPH
Origin

[Marte01]

Constraint

πšπš›πšŠπšŒπš”(π™½πšƒπšπ™°π™Έπ™»,πšƒπ™°πš‚π™Ίπš‚)

Arguments
π™½πšƒπšπ™°π™Έπ™»πš’πš—πš
πšƒπ™°πš‚π™Ίπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπš›πšŠπš’πš•-πš’πš—πš,πš˜πš›πš’πšπš’πš—-πšπšŸπšŠπš›,πšŽπš—πš-πšπšŸπšŠπš›)
Restrictions
π™½πšƒπšπ™°π™Έπ™»>0
π™½πšƒπšπ™°π™Έπ™»β‰€|πšƒπ™°πš‚π™Ίπš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπ™°πš‚π™Ίπš‚,[πšπš›πšŠπš’πš•,πš˜πš›πš’πšπš’πš—,πšŽπš—πš])
πšƒπ™°πš‚π™Ίπš‚.πš˜πš›πš’πšπš’πš—β‰€πšƒπ™°πš‚π™Ίπš‚.πšŽπš—πš
Purpose

The πšπš›πšŠπšŒπš” constraint enforces that, at each point in time overlapped by at least one task, the number of distinct values of the πšπš›πšŠπš’πš• attribute of the set of tasks that overlap that point, is equal to π™½πšƒπšπ™°π™Έπ™».

Example
2,πšπš›πšŠπš’πš•-1πš˜πš›πš’πšπš’πš—-1πšŽπš—πš-2,πšπš›πšŠπš’πš•-2πš˜πš›πš’πšπš’πš—-1πšŽπš—πš-2,πšπš›πšŠπš’πš•-1πš˜πš›πš’πšπš’πš—-2πšŽπš—πš-4,πšπš›πšŠπš’πš•-2πš˜πš›πš’πšπš’πš—-2πšŽπš—πš-3,πšπš›πšŠπš’πš•-2πš˜πš›πš’πšπš’πš—-3πšŽπš—πš-4

FigureΒ 5.336.1 represents the tasks of the example: to the i th task of the πšƒπ™°πš‚π™Ίπš‚ collection corresponds a rectangle labelled by i. The πšπš›πšŠπšŒπš” constraint holds since:

  • The first and second tasks both overlap instant 1 and have a respective trail of 1 and 2. This makes two distinct values for the trail attribute at instant 1.

  • The third and fourth tasks both overlap instant 2 and have a respective trail of 1 and 2. This makes two distinct values for the trail attribute at instant 2.

  • The third and fifth tasks both overlap instant 3 and have a respective trail of 1 and 2. This makes two distinct values for the trail attribute at instant 3.

Figure 5.336.1. Tasks associated with the example of the Example slot
ctrs/track1
Symmetries
  • Items of πšƒπ™°πš‚π™Ίπš‚ are permutable.

  • All occurrences of two distinct values of πšƒπ™°πš‚π™Ίπš‚.πšπš›πšŠπš’πš• can be swapped; all occurrences of a value of πšƒπ™°πš‚π™Ίπš‚.πšπš›πšŠπš’πš• can be renamed to any unused value.

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

Reformulation

The πšπš›πšŠπšŒπš” constraint can be expressed in term of a set of reified constraints and of 2Β·|πšƒπ™°πš‚π™Ίπš‚| πš—πšŸπšŠπš•πšžπšŽ constraints:

  1. For each pair of tasks πšƒπ™°πš‚π™Ίπš‚[i],πšƒπ™°πš‚π™Ίπš‚[j] (i,j∈[1,|πšƒπ™°πš‚π™Ίπš‚|]) of the πšƒπ™°πš‚π™Ίπš‚ collection we create a variable T ij πš˜πš›πš’πšπš’πš— which is set to the πšπš›πšŠπš’πš• attribute of task πšƒπ™°πš‚π™Ίπš‚[j] if task πšƒπ™°πš‚π™Ίπš‚[j] overlaps the origin attribute of task πšƒπ™°πš‚π™Ίπš‚[i], and to the πšπš›πšŠπš’πš• attribute of task πšƒπ™°πš‚π™Ίπš‚[i] otherwise:

    • If i=j:

      • T ij πš˜πš›πš’πšπš’πš— =πšƒπ™°πš‚π™Ίπš‚[i].πšπš›πšŠπš’πš•.

    • If iβ‰ j:

      • T ij πš˜πš›πš’πšπš’πš— =πšƒπ™°πš‚π™Ίπš‚[i].πšπš›πšŠπš’πš•βˆ¨T ij πš˜πš›πš’πšπš’πš— =πšƒπ™°πš‚π™Ίπš‚[j].πšπš›πšŠπš’πš•.

      • ((πšƒπ™°πš‚π™Ίπš‚[j].πš˜πš›πš’πšπš’πš—β‰€πšƒπ™°πš‚π™Ίπš‚[i].πš˜πš›πš’πšπš’πš— ∧

        Β Β Β πšƒπ™°πš‚π™Ίπš‚[j].πšŽπš—πš>πšƒπ™°πš‚π™Ίπš‚[i].πš˜πš›πš’πšπš’πš—)∧(T ij πš˜πš›πš’πšπš’πš— =πšƒπ™°πš‚π™Ίπš‚[j].πšπš›πšŠπš’πš•)) ∨

        ((πšƒπ™°πš‚π™Ίπš‚[j].πš˜πš›πš’πšπš’πš—>πšƒπ™°πš‚π™Ίπš‚[i].πš˜πš›πš’πšπš’πš— ∨

        Β Β Β πšƒπ™°πš‚π™Ίπš‚[j].πšŽπš—πšβ‰€πšƒπ™°πš‚π™Ίπš‚[i].πš˜πš›πš’πšπš’πš—)∧(T ij πš˜πš›πš’πšπš’πš— =πšƒπ™°πš‚π™Ίπš‚[i].πšπš›πšŠπš’πš•))

  2. For each task πšƒπ™°πš‚π™Ίπš‚[i] (i∈[1,|πšƒπ™°πš‚π™Ίπš‚|]) we impose the number of distinct trails associated with the tasks that overlap the origin of task πšƒπ™°πš‚π™Ίπš‚[i] (πšƒπ™°πš‚π™Ίπš‚[i] overlaps its own origin) to be equal to π™½πšƒπšπ™°π™Έπ™»:

    πš—πšŸπšŠπš•πšžπšŽ(π™½πšƒπšπ™°π™Έπ™»,〈T i1 πš˜πš›πš’πšπš’πš— ,T i2 πš˜πš›πš’πšπš’πš— ,...,T i|πšƒπ™°πš‚π™Ίπš‚| πš˜πš›πš’πšπš’πš— βŒͺ).

  3. For each pair of tasks πšƒπ™°πš‚π™Ίπš‚[i],πšƒπ™°πš‚π™Ίπš‚[j] (i,j∈[1,|πšƒπ™°πš‚π™Ίπš‚|]) of the πšƒπ™°πš‚π™Ίπš‚ collection we create a variable T ij πšŽπš—πš which is set to the πšπš›πšŠπš’πš• attribute of task πšƒπ™°πš‚π™Ίπš‚[j] if task πšƒπ™°πš‚π™Ίπš‚[j] overlaps the end attribute of task πšƒπ™°πš‚π™Ίπš‚[i], and to the πšπš›πšŠπš’πš• attribute of task πšƒπ™°πš‚π™Ίπš‚[i] otherwise:

    • If i=j:

      • T ij πšŽπš—πš =πšƒπ™°πš‚π™Ίπš‚[i].πšπš›πšŠπš’πš•.

    • If iβ‰ j:

      • T ij πšŽπš—πš =πšƒπ™°πš‚π™Ίπš‚[i].πšπš›πšŠπš’πš•βˆ¨T ij πšŽπš—πš =πšƒπ™°πš‚π™Ίπš‚[j].πšπš›πšŠπš’πš•.

      • ((πšƒπ™°πš‚π™Ίπš‚[j].πš˜πš›πš’πšπš’πš—β‰€πšƒπ™°πš‚π™Ίπš‚[i].πšŽπš—πš-1 ∧

        Β Β Β πšƒπ™°πš‚π™Ίπš‚[j].πšŽπš—πš>πšƒπ™°πš‚π™Ίπš‚[i].πšŽπš—πš-1)∧(T ij πšŽπš—πš =πšƒπ™°πš‚π™Ίπš‚[j].πšπš›πšŠπš’πš•)) ∨

        ((πšƒπ™°πš‚π™Ίπš‚[j].πš˜πš›πš’πšπš’πš—>πšƒπ™°πš‚π™Ίπš‚[i].πšŽπš—πš-1 ∨

        Β Β Β πšƒπ™°πš‚π™Ίπš‚[j].πšŽπš—πšβ‰€πšƒπ™°πš‚π™Ίπš‚[i].πšŽπš—πš-1)∧(T ij πšŽπš—πš =πšƒπ™°πš‚π™Ίπš‚[i].πšπš›πšŠπš’πš•))

  4. For each task πšƒπ™°πš‚π™Ίπš‚[i] (i∈[1,|πšƒπ™°πš‚π™Ίπš‚|]) we impose the number of distinct trails associated with the tasks that overlap the end of task πšƒπ™°πš‚π™Ίπš‚[i] (πšƒπ™°πš‚π™Ίπš‚[i] overlaps its own end) to be equal to π™½πšƒπšπ™°π™Έπ™»:

    πš—πšŸπšŠπš•πšžπšŽ(π™½πšƒπšπ™°π™Έπ™»,〈T i1 πšŽπš—πš ,T i2 πšŽπš—πš ,...,T i|πšƒπ™°πš‚π™Ίπš‚| πšŽπš—πš βŒͺ).

With respect to the Example slot we get the following conjunction of πš—πšŸπšŠπš•πšžπšŽ constraints:

  • The πš—πšŸπšŠπš•πšžπšŽ(2,〈1,2,1,1,1βŒͺ) constraint corresponding to the πšπš›πšŠπš’πš• attributes of the tasks that overlap the origin of the first task (i.e.,Β instant 1) that has a trail of 1.

  • The πš—πšŸπšŠπš•πšžπšŽ(2,〈1,2,2,2,2βŒͺ) constraint corresponding to the πšπš›πšŠπš’πš• attributes of the tasks that overlap the origin of the second task (i.e.,Β instant 1) that has a trail of 2.

  • The πš—πšŸπšŠπš•πšžπšŽ(2,〈1,1,1,2,1βŒͺ) constraint corresponding to the πšπš›πšŠπš’πš• attributes of the tasks that overlap the origin of the third task (i.e.,Β instant 2) that has a trail of 1.

  • The πš—πšŸπšŠπš•πšžπšŽ(2,〈2,2,1,2,2βŒͺ) constraint corresponding to the πšπš›πšŠπš’πš• attributes of the tasks that overlap the origin of the fourth task (i.e.,Β instant 2) that has a trail of 2.

  • The πš—πšŸπšŠπš•πšžπšŽ(2,〈2,2,1,2,2βŒͺ) constraint corresponding to the πšπš›πšŠπš’πš• attributes of the tasks that overlap the origin of the fifth task (i.e.,Β instant 3) that has a trail of 2.

  • The πš—πšŸπšŠπš•πšžπšŽ(2,〈1,2,1,1,1βŒͺ) constraint corresponding to the πšπš›πšŠπš’πš• attributes of the tasks that overlap the last instant of the first task (i.e.,Β instant 1) that has a trail of 1.

  • The πš—πšŸπšŠπš•πšžπšŽ(2,〈1,2,2,2,2βŒͺ) constraint corresponding to the πšπš›πšŠπš’πš• attributes of the tasks that overlap the last instant of the second task (i.e.,Β instant 1) that has a trail of 2.

  • The πš—πšŸπšŠπš•πšžπšŽ(2,〈1,1,1,1,2βŒͺ) constraint corresponding to the πšπš›πšŠπš’πš• attributes of the tasks that overlap the last instant of the third task (i.e.,Β instant 3) that has a trail of 1.

  • The πš—πšŸπšŠπš•πšžπšŽ(2,〈2,2,1,2,2βŒͺ) constraint corresponding to the πšπš›πšŠπš’πš• attributes of the tasks that overlap the last instant of the fourth task (i.e.,Β instant 2) that has a trail of 2.

  • The πš—πšŸπšŠπš•πšžπšŽ(2,〈2,2,1,2,2βŒͺ) constraint corresponding to the πšπš›πšŠπš’πš• attributes of the tasks that overlap the last instant of the fifth task (i.e.,Β instant 3) that has a trail of 2.

See also

common keyword: πšŒπš˜πš•πš˜πšžπš›πšŽπš_πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽΒ (resource constraint).

used in graph description: πš—πšŸπšŠπš•πšžπšŽ.

Keywords

characteristic of a constraint: derived collection.

constraint type: timetabling constraint, resource constraint, temporal constraint.

Derived Collection
πšŒπš˜πš•πšƒπ™Έπ™Όπ™΄_π™Ώπ™Ύπ™Έπ™½πšƒπš‚-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš˜πš›πš’πšπš’πš—-πšπšŸπšŠπš›,πšŽπš—πš-πšπšŸπšŠπš›,πš™πš˜πš’πš—πš-πšπšŸπšŠπš›),πš’πšπšŽπš–πš˜πš›πš’πšπš’πš—-πšƒπ™°πš‚π™Ίπš‚.πš˜πš›πš’πšπš’πš—,πšŽπš—πš-πšƒπ™°πš‚π™Ίπš‚.πšŽπš—πš,πš™πš˜πš’πš—πš-πšƒπ™°πš‚π™Ίπš‚.πš˜πš›πš’πšπš’πš—,πš’πšπšŽπš–πš˜πš›πš’πšπš’πš—-πšƒπ™°πš‚π™Ίπš‚.πš˜πš›πš’πšπš’πš—,πšŽπš—πš-πšƒπ™°πš‚π™Ίπš‚.πšŽπš—πš,πš™πš˜πš’πš—πš-πšƒπ™°πš‚π™Ίπš‚.πšŽπš—πš-1
Arc input(s)

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

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

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

Arc input(s)

πšƒπ™Έπ™Όπ™΄_π™Ώπ™Ύπ™Έπ™½πšƒπš‚ πšƒπ™°πš‚π™Ίπš‚

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

Arc arity
Arc constraint(s)
β€’ πšπš’πš–πšŽ_πš™πš˜πš’πš—πšπšœ.πšŽπš—πš>πšπš’πš–πšŽ_πš™πš˜πš’πš—πšπšœ.πš˜πš›πš’πšπš’πš—
β€’ πšπšŠπšœπš”πšœ.πš˜πš›πš’πšπš’πš—β‰€πšπš’πš–πšŽ_πš™πš˜πš’πš—πšπšœ.πš™πš˜πš’πš—πš
β€’ πšπš’πš–πšŽ_πš™πš˜πš’πš—πšπšœ.πš™πš˜πš’πš—πš<πšπšŠπšœπš”πšœ.πšŽπš—πš
Sets
π–²π–΄π–’π–’β†¦πšœπš˜πšžπš›πšŒπšŽ,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ-πšŒπš˜πš•πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›),πš’πšπšŽπš–(πšŸπšŠπš›-πšƒπ™°πš‚π™Ίπš‚.πšπš›πšŠπš’πš•)]

Constraint(s) on sets
πš—πšŸπšŠπš•πšžπšŽ(π™½πšƒπšπ™°π™Έπ™»,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)
Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.336.2 respectively show the initial and final graph of the second graph constraint of the Example slot.

Figure 5.336.2. Initial and final graph of the πšπš›πšŠπšŒπš” constraint
ctrs/trackA
(a)
ctrs/trackB
(b)
Signature

Consider the first graph constraint. Since we use the 𝑆𝐸𝐿𝐹 arc generator on the πšƒπ™°πš‚π™Ίπš‚ collection, the maximum number of arcs of the final graph is equal to |πšƒπ™°πš‚π™Ίπš‚|. Therefore we can rewrite 𝐍𝐀𝐑𝐂=|πšƒπ™°πš‚π™Ίπš‚| to 𝐍𝐀𝐑𝐂β‰₯|πšƒπ™°πš‚π™Ίπš‚| and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.