5.289. sliding_time_window

Origin

N. Beldiceanu

Constraint

sliding_time_window​(WINDOW_SIZE,​LIMIT,​TASKS)​

Argument(s)

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

Restriction(s)

WINDOW_SIZE>​0

LIMIT≥0

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

TASKS.duration≥0

Purpose

For any time window of size WINDOW_SIZE, the intersection of all the tasks of the collection TASKS with this time window is less than or equal to a given limit LIMIT.

Example

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

The lower part of Figure 5.289.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.289.1 shows the different time windows and the respective contribution of the tasks in these time windows. Observe 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 sliding_time_window constraint holds.

Figure 5.289.1. Time windows of the sliding_time_window constraint

Usage

The sliding_time_window constraint is useful for timetabling problems in order to put an upper limit on the total work over sliding time windows.

Reformulation

The sliding_time_window constraint can be expressed in term of a set of |TASKS|² reified constraints and of |TASKS| linear inequalities constraints:

1. For each pair of tasks TASKS​[i]​,​TASKS​[j]​ ​(i,​j∈​[1,​|TASKS|]​)​ of the TASKS collection we create a variable Inter_ij which is set to the intersection of TASKS​[j]​ with the time window W_i of size WINDOW_SIZE that starts at instant TASKS​[i]​.origin:

   • If i=j (i.e., TASKS​[i]​ and TASKS​[j]​ coincide):

     • Inter_ij=min​(TASKS​[i]​.duration,​WINDOW_SIZE)​.

   • If i≠j and TASKS​[j]​.origin+TASKS​[j]​.duration​<TASKS​[i]​.origin (i.e., TASKS​[j]​ for sure ends before the time window W_i):

     • Inter_ij=0.

   • If i≠j and TASKS​[j]​.origin>​TASKS​[i]​.origin+WINDOW_SIZE−1 (i.e., TASKS​[j]​ for sure starts after the time window W_i):

     • Inter_ij=0.

   • Otherwise (i.e., TASKS​[j]​ can potentially overlap the time window W_i):

     • Inter_ij=max​(0,​min​(TASKS​[i]​.origin+WINDOW_SIZE,​TASKS​[j]​.origin+TASKS​[j]​.duration)​−max​(TASKS​[i]​.origin,​TASKS​[j]​.origin)​)​.

2. For each task TASKS​[i]​ ​(i∈​[1,​|TASKS|]​)​ we create a linear inequality constraint Inter_i1+Inter_i2+...+Inter_i|TASKS|≤LIMIT.

See also

shift, sliding_time_window_from_start, sliding_time_window_sum.

Key words

constraint type: sliding sequence constraint, temporal constraint.

Arc input(s)

TASKS

Arc generator

CLIQUE↦collection​(tasks1,​tasks2)​

Arc arity

2

Arc constraint(s)

• tasks1.origin≤tasks2.origin

• tasks2.origin−tasks1.origin​<WINDOW_SIZE

Sets

SUCC↦​[source,​tasks]​

Constraint(s) on sets

sliding_time_window_from_start​(WINDOW_SIZE,​LIMIT,​tasks,​source.origin)​

---

Graph model

We generate an arc from a task t₁ to a task t₂ if task t₂ does not start before task t₁ and if task t₂ intersects the time window that starts at the origin of task t₁. Each set generated by SUCC 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.289.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.289.2. Initial and final graph of the sliding_time_window constraint

(a)	(b)