5.296. sliding_time_window_from_start

DESCRIPTIONLINKSGRAPH
Origin

Used for defining πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš .

Constraint

πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš _πšπš›πš˜πš–_πšœπšπšŠπš›πš(πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄,π™»π™Έπ™Όπ™Έπšƒ,πšƒπ™°πš‚π™Ίπš‚,πš‚πšƒπ™°πšπšƒ)

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

The sum of the intersections of all the tasks of the πšƒπ™°πš‚π™Ίπš‚ collection with interval [πš‚πšƒπ™°πšπšƒ,πš‚πšƒπ™°πšπšƒ+πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄-1] is less than or equal to π™»π™Έπ™Όπ™Έπšƒ.

Example
9,6,πš˜πš›πš’πšπš’πš—-10πšπšžπš›πšŠπšπš’πš˜πš—-3,πš˜πš›πš’πšπš’πš—-5πšπšžπš›πšŠπšπš’πš˜πš—-1,πš˜πš›πš’πšπš’πš—-6πšπšžπš›πšŠπšπš’πš˜πš—-2,5

The intersections of tasks βŒ©πš’πš-1 πš˜πš›πš’πšπš’πš—-10 πšπšžπš›πšŠπšπš’πš˜πš—-3βŒͺ, βŒ©πš’πš-2 πš˜πš›πš’πšπš’πš—-5 πšπšžπš›πšŠπšπš’πš˜πš—-1βŒͺ, and βŒ©πš’πš-3 πš˜πš›πš’πšπš’πš—-6 πšπšžπš›πšŠπšπš’πš˜πš—-2βŒͺ with interval [πš‚πšƒπ™°πšπšƒ,πš‚πšƒπ™°πšπšƒ+πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄-1]=[5,5+9-1]=[5,13] are respectively equal to 3, 1, and 2 (i.e.,Β the three tasks of the πšƒπ™°πš‚π™Ίπš‚ collection are in fact included within interval [5,13]). Consequently, the πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš _πšπš›πš˜πš–_πšœπšπšŠπš›πš constraint holds since the sum 3+1+2 of these intersections does not exceed the value of its second argument π™»π™Έπ™Όπ™Έπšƒ=6.

Symmetries
  • πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄ can be decreased.

  • π™»π™Έπ™Όπ™Έπšƒ can be increased.

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

  • πšƒπ™°πš‚π™Ίπš‚.πšπšžπš›πšŠπšπš’πš˜πš— can be decreased to any value β‰₯0.

  • One and the same constant can be added to πš‚πšƒπ™°πšπšƒ as well as to the πš˜πš›πš’πšπš’πš— attribute of all items of πšƒπ™°πš‚π™Ίπš‚.

Reformulation

Similar to the reformulation of πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš .

Used in

πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš .

Keywords

characteristic of a constraint: derived collection.

constraint type: sliding sequence constraint, temporal constraint.

Derived Collection
πšŒπš˜πš•(πš‚-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›),[πš’πšπšŽπš–(πšŸπšŠπš›-πš‚πšƒπ™°πšπšƒ)])
Arc input(s)

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

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

Arc arity
Arc constraint(s)
πšƒπšπš„π™΄
Graph property(ies)
π’π”πŒ_π–π„πˆπ†π‡π“_π€π‘π‚πš–πšŠπš‘0,πš–πš’πš—πšœ.πšŸπšŠπš›+πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄,πšπšŠπšœπš”πšœ.πš˜πš›πš’πšπš’πš—+πšπšŠπšœπš”πšœ.πšπšžπš›πšŠπšπš’πš˜πš—-πš–πšŠπš‘(𝚜.πšŸπšŠπš›,πšπšŠπšœπš”πšœ.πš˜πš›πš’πšπš’πš—)β‰€π™»π™Έπ™Όπ™Έπšƒ

Graph model

Since we use the πšƒπšπš„π™΄ arc constraint the final and the initial graph are identical. The unique source of the final graph corresponds to the interval [πš‚πšƒπ™°πšπšƒ,πš‚πšƒπ™°πšπšƒ+πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄-1]. Each sink of the final graph represents a given task of the πšƒπ™°πš‚π™Ίπš‚ collection. We associate to each arc the value given by the intersection of the task associated with one of the extremities of the arc with the time window [πš‚πšƒπ™°πšπšƒ,πš‚πšƒπ™°πšπšƒ+πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄-1]. Finally, the graph property π’π”πŒ_π–π„πˆπ†π‡π“_𝐀𝐑𝐂 sums up all the valuations of the arcs and check that it does not exceed a given limit.

PartsΒ (A) andΒ (B) of FigureΒ 5.296.1 respectively show the initial and final graph associated with the Example slot. To each arc of the final graph we associate the intersection of the corresponding sink task with interval [πš‚πšƒπ™°πšπšƒ,πš‚πšƒπ™°πšπšƒ+πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄-1]. The constraint πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš _πšπš›πš˜πš–_πšœπšπšŠπš›πš holds since the sum of the previous intersections does not exceed π™»π™Έπ™Όπ™Έπšƒ.

Figure 5.296.1. Initial and final graph of the πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš _πšπš›πš˜πš–_πšœπšπšŠπš›πš constraint
ctrs/sliding_time_window_from_startActrs/sliding_time_window_from_startB
(a) (b)