5.290. sliding_time_window_from_start

Origin

Used for defining sliding_time_window.

Constraint

sliding_time_window_from_start​(WINDOW_SIZE,​LIMIT,​TASKS,​START)​

Argument(s)

WINDOW_SIZE	int
LIMIT	int
TASKS	collection​(origin−dvar,​duration−dvar)​
START	dvar

Restriction(s)

WINDOW_SIZE>​0

LIMIT≥0

required​(TASKS,​​[origin,​duration]​)​

TASKS.duration≥0

Purpose

The sum of the intersections of all the tasks of the TASKS collection with interval ​[START,​START+WINDOW_SIZE−1]​ is less than or equal to LIMIT.

Example

( 9,​6,​〈origin−10 duration−3,​origin−5 duration−1,​origin−6 duration−2〉,​5 )

The intersections of tasks 〈id−1 origin−10 duration−3〉, 〈id−2 origin−5 duration−1〉, and 〈id−3 origin−6 duration−2〉 with interval ​[START,​START+WINDOW_SIZE−1]​=​[5,​5+9−1]​=​[5,​13]​ are respectively equal to 3, 1, and 2 (i.e., the three tasks of the TASKS collection are in fact included within interval ​[5,​13]​). Consequently, the sliding_time_window_from_start constraint holds since the sum 3+1+2 of these intersections does not exceed the value of its second argument LIMIT=6.

Reformulation

Similar to the reformulation of sliding_time_window.

Used in

sliding_time_window.

Key words

characteristic of a constraint: derived collection.

constraint type: sliding sequence constraint, temporal constraint.

Derived Collection(s)

col​(S−collection​(var−dvar)​,​​[item​(var−START)​]​)​

---

Arc input(s)

S TASKS

Arc generator

PRODUCT↦collection​(s,​tasks)​

Arc arity

2

Arc constraint(s)

TRUE

Graph property(ies)

SUM_WEIGHT_ARC( max( 0,​ min​(s.var+WINDOW_SIZE,​tasks.origin+tasks.duration)​− max​(s.var,​tasks.origin)​ ) )≤LIMIT

---

Graph model

Since we use the TRUE arc constraint the final and the initial graph are identical. The unique source of the final graph corresponds to the interval ​[START,​START+WINDOW_SIZE−1]​. Each sink of the final graph represents a given task of the TASKS 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 ​[START,​START+WINDOW_SIZE−1]​. Finally, the graph property SUM_WEIGHT_ARC 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.290.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 ​[START,​START+WINDOW_SIZE−1]​. The constraint sliding_time_window_from_start holds since the sum of the previous intersections does not exceed LIMIT.

Figure 5.290.1. Initial and final graph of the sliding_time_window_from_start constraint

(a)	(b)