5.354. sliding_time_window_sum
DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Arguments
- Restrictions
- 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
-
The lower part of FigureΒ 5.354.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.354.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.354.1. Time windows and their use for the five tasks of the Example slot
- Typical
- Symmetries
can be decreased.
can be increased.
Items of are permutable.
can be decreased to any value .
One and the same constant can be added to the and attributes of all items of .
- Arg. properties
Contractible wrt. .
- 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 reified constraints and of linear inequalities constraints:
For each pair of tasks of the collection we create a variable which is set to if intersects the time window of size that starts at instant , or 0 otherwise:
If (i.e.,Β and coincide):
.
If and (i.e.,Β for sure ends before the time window ):
.
If and (i.e.,Β for sure starts after the time window ):
.
Otherwise (i.e.,Β can potentially overlap the time window ):
.
For each task we create a linear inequality constraint .
- 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).
- 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
-
- Arc arity
- Arc constraint(s)
-
- Sets
-
- Constraint(s) on sets
- Graph model
We generate an arc from a task to a task if task does not end before the end of task and if task intersects the time window that starts at the last instant of task . Each set generated by corresponds to all tasks that intersect in time the time window that starts at instant , where is the end of a given task.
PartsΒ (A) andΒ (B) of FigureΒ 5.354.2 respectively show the initial and final graph associated with the Example slot. In the final graph, the successors of a given task correspond to the set of tasks that both do not end before the of task , and intersect the time window that starts at the of task .
Figure 5.354.2. Initial and final graph of the constraint
(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 .