5.297. sliding_time_window_sum

DESCRIPTIONLINKSGRAPH
Origin

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

Constraint

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

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

For any time window of size πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄, the sum of the points of the tasks of the collection πšƒπ™°πš‚π™Ίπš‚ that overlap that time window do not exceed a given limit π™»π™Έπ™Όπ™Έπšƒ.

Example
9,16,πš˜πš›πš’πšπš’πš—-10πšŽπš—πš-13πš—πš™πš˜πš’πš—πš-2,πš˜πš›πš’πšπš’πš—-5πšŽπš—πš-6πš—πš™πš˜πš’πš—πš-3,πš˜πš›πš’πšπš’πš—-6πšŽπš—πš-8πš—πš™πš˜πš’πš—πš-4,πš˜πš›πš’πšπš’πš—-14πšŽπš—πš-16πš—πš™πš˜πš’πš—πš-5,πš˜πš›πš’πšπš’πš—-2πšŽπš—πš-4πš—πš™πš˜πš’πš—πš-6

The lower part of FigureΒ 5.297.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.297.1 shows the different time windows and the respective contribution of the tasks in these time windows. A line with two arrows depicts each time window. The two arrows indicate the start and the end of the time window. At the right of each time window we give its occupation. Since this occupation is always less than or equal to the limit 16, the πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš _πšœπšžπš– constraint holds.

Figure 5.297.1. Time windows of the πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš _πšœπšžπš– constraint
ctrs/sliding_time_window_sum1
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 the πš˜πš›πš’πšπš’πš— and πšŽπš—πš attributes of all items of πšƒπ™°πš‚π™Ίπš‚.

Usage

This constraint may be used for timetabling problems in order to put an upper limit on the cumulated number of points in a shift.

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 πšƒπ™°πš‚π™Ίπš‚[j].πš—πš™πš˜πš’πš—πš if πšƒπ™°πš‚π™Ίπš‚[j] intersects the time window 𝒲 i of size πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄ that starts at instant πšƒπ™°πš‚π™Ίπš‚[i].πš˜πš›πš’πšπš’πš—, or 0 otherwise:

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

      • π‘ƒπ‘œπ‘–π‘›π‘‘ ij =πšƒπ™°πš‚π™Ίπš‚[i].πš—πš™πš˜πš’πš—πš.

    • If iβ‰ j and πšƒπ™°πš‚π™Ίπš‚[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 =min(1,max(0,min(πšƒπ™°πš‚π™Ίπš‚[i].πš˜πš›πš’πšπš’πš—+πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄,πšƒπ™°πš‚π™Ίπš‚[j].πšŽπš—πš)-max(πšƒπ™°πš‚π™Ίπš‚[i].πš˜πš›πš’πšπš’πš—,πšƒπ™°πš‚π™Ίπš‚[j].πš˜πš›πš’πšπš’πš—)))Β·πšƒπ™°πš‚π™Ίπš‚[j].πš—πš™πš˜πš’πš—πš.

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

See also

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

used in graph description: πšœπšžπš–_πšŒπšπš›.

Keywords

characteristic of a constraint: time window, sum.

constraint type: sliding sequence constraint, temporal constraint.

Arc input(s)

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

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

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

Arc input(s)

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

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

Arc arity
Arc constraint(s)
β€’ πšπšŠπšœπš”πšœ1.πšŽπš—πšβ‰€πšπšŠπšœπš”πšœ2.πšŽπš—πš
β€’ πšπšŠπšœπš”πšœ2.πš˜πš›πš’πšπš’πš—-πšπšŠπšœπš”πšœ1.πšŽπš—πš<πš†π™Έπ™½π™³π™Ύπš†_πš‚π™Έπš‰π™΄-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 end before the end of task t 1 and if task t 2 intersects the time window that starts at the last instant of task t 1 . Each set generated by 𝖲𝖴𝖒𝖒 corresponds to all tasks that intersect in time the time window that starts at instant πšŽπš—πš-1, where πšŽπš—πš is the end of a given task.

PartsΒ (A) andΒ (B) of FigureΒ 5.297.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 both do not end before the πšŽπš—πš of task t, and intersect the time window that starts at the πšŽπš—πš-1 of task t.

Figure 5.297.2. Initial and final graph of the πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš _πšœπšžπš– constraint
ctrs/sliding_time_window_sumActrs/sliding_time_window_sumB
(a) (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 𝐍𝐀𝐑𝐂 Β―.