5.295. sliding_time_window

DESCRIPTIONLINKSGRAPH
Origin

N.Β Beldiceanu

Constraint

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

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

For any time window of size πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄, the intersection of all the tasks of the collection πšƒπ™°πš‚π™Ίπš‚ with this time window is less than or equal to a given limit π™»π™Έπ™Όπ™Έπšƒ.

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

The lower part of FigureΒ 5.295.1 indicates the different tasks on the time axis. Each task is drawn as a rectangle with its corresponding identifier in the middle. Finally the upper part of FigureΒ 5.295.1 shows the different time windows and the respective contribution of the tasks in these time windows. Note that we only need to focus on those time windows starting at the start of one of the tasks. A line with two arrows depicts each time window. The two arrows indicate the start and the end of the time window. At the left of each time window we give its occupation. Since this occupation is always less than or equal to the limit 6, the πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš  constraint holds.

Figure 5.295.1. Time windows of the πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš  constraint
ctrs/sliding_time_window1
Symmetries
  • πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄ can be decreased.

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

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

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

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

Usage

The πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš  constraint is useful for timetabling problems in order to put an upper limit on the total work over sliding time windows.

Reformulation

The πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš  constraint can be expressed in term of a set of |πšƒπ™°πš‚π™Ίπš‚| 2 reified constraints and of |πšƒπ™°πš‚π™Ίπš‚| linear inequalities constraints:

  1. For each pair of tasks πšƒπ™°πš‚π™Ίπš‚[i],πšƒπ™°πš‚π™Ίπš‚[j] (i,j∈[1,|πšƒπ™°πš‚π™Ίπš‚|]) of the πšƒπ™°πš‚π™Ίπš‚ collection we create a variable πΌπ‘›π‘‘π‘’π‘Ÿ ij which is set to the intersection of πšƒπ™°πš‚π™Ίπš‚[j] with the time window 𝒲 i of size πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄ that starts at instant πšƒπ™°πš‚π™Ίπš‚[i].πš˜πš›πš’πšπš’πš—:

    • If i=j (i.e.,Β πšƒπ™°πš‚π™Ίπš‚[i] and πšƒπ™°πš‚π™Ίπš‚[j] coincide):

      • πΌπ‘›π‘‘π‘’π‘Ÿ ij =min(πšƒπ™°πš‚π™Ίπš‚[i].πšπšžπš›πšŠπšπš’πš˜πš—,πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄).

    • If iβ‰ j and πšƒπ™°πš‚π™Ίπš‚[j].πš˜πš›πš’πšπš’πš— Β―+πšƒπ™°πš‚π™Ίπš‚[j].πšπšžπš›πšŠπšπš’πš˜πš— Β―<πšƒπ™°πš‚π™Ίπš‚[i].πš˜πš›πš’πšπš’πš— Μ² (i.e.,Β πšƒπ™°πš‚π™Ίπš‚[j] for sure ends before the time window 𝒲 i ):

      • πΌπ‘›π‘‘π‘’π‘Ÿ ij =0.

    • If iβ‰ j and πšƒπ™°πš‚π™Ίπš‚[j].πš˜πš›πš’πšπš’πš— Μ²>πšƒπ™°πš‚π™Ίπš‚[i].πš˜πš›πš’πšπš’πš— Β―+πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄-1 (i.e.,Β πšƒπ™°πš‚π™Ίπš‚[j] for sure starts after the time window 𝒲 i ):

      • πΌπ‘›π‘‘π‘’π‘Ÿ ij =0.

    • Otherwise (i.e.,Β πšƒπ™°πš‚π™Ίπš‚[j] can potentially overlap the time window 𝒲 i ):

      • πΌπ‘›π‘‘π‘’π‘Ÿ ij =max(0,min(πšƒπ™°πš‚π™Ίπš‚[i].πš˜πš›πš’πšπš’πš—+πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄,πšƒπ™°πš‚π™Ίπš‚[j].πš˜πš›πš’πšπš’πš—+πšƒπ™°πš‚π™Ίπš‚[j].πšπšžπš›πšŠπšπš’πš˜πš—)-max(πšƒπ™°πš‚π™Ίπš‚[i].πš˜πš›πš’πšπš’πš—,πšƒπ™°πš‚π™Ίπš‚[j].πš˜πš›πš’πšπš’πš—)).

  2. For each task πšƒπ™°πš‚π™Ίπš‚[i] (i∈[1,|πšƒπ™°πš‚π™Ίπš‚|]) we create a linear inequality constraint πΌπ‘›π‘‘π‘’π‘Ÿ i1 +πΌπ‘›π‘‘π‘’π‘Ÿ i2 +...+πΌπ‘›π‘‘π‘’π‘Ÿ i|πšƒπ™°πš‚π™Ίπš‚| β‰€π™»π™Έπ™Όπ™Έπšƒ.

See also

common keyword: πšœπš‘πš’πšπšΒ (temporal constraint).

related: πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš _πšœπšžπš–Β (sum of intersections of tasks with sliding time window replaced by sum of the points of intersecting tasks with sliding time window).

used in graph description: πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš _πšπš›πš˜πš–_πšœπšπšŠπš›πš.

Keywords

constraint type: sliding sequence constraint, temporal constraint.

Arc input(s)

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

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπšŠπšœπš”πšœ1,πšπšŠπšœπš”πšœ2)

Arc arity
Arc constraint(s)
β€’ πšπšŠπšœπš”πšœ1.πš˜πš›πš’πšπš’πš—β‰€πšπšŠπšœπš”πšœ2.πš˜πš›πš’πšπš’πš—
β€’ πšπšŠπšœπš”πšœ2.πš˜πš›πš’πšπš’πš—-πšπšŠπšœπš”πšœ1.πš˜πš›πš’πšπš’πš—<πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄
Sets
𝖲𝖴𝖒𝖒↦[πšœπš˜πšžπš›πšŒπšŽ,πšπšŠπšœπš”πšœ]

Constraint(s) on sets
πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš _πšπš›πš˜πš–_πšœπšπšŠπš›πšπš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄,π™»π™Έπ™Όπ™Έπšƒ,πšπšŠπšœπš”πšœ,πšœπš˜πšžπš›πšŒπšŽ.πš˜πš›πš’πšπš’πš—
Graph model

We generate an arc from a task t 1 to a task t 2 if task t 2 does not start before task t 1 and if task t 2 intersects the time window that starts at the origin of task t 1 . Each set generated by 𝖲𝖴𝖒𝖒 corresponds to all tasks that intersect in time the time window that starts at the origin of a given task.

PartsΒ (A) andΒ (B) of FigureΒ 5.295.2 respectively show the initial and final graph associated with the Example slot. In the final graph, the successors of a given task t correspond to the set of tasks that do not start before task t and intersect the time window that starts at the origin of task t.

Figure 5.295.2. Initial and final graph of the πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš  constraint
ctrs/sliding_time_windowActrs/sliding_time_windowB
(a) (b)