5.101. cumulatives
DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Arguments
- Restrictions
- Purpose
Consider a set of tasks described by the collection. When is equal to (respectively ), the constraint forces the following condition for each machine : At each point in time, where at least one task assigned on machine is present, the cumulated height of the set of tasks that both overlap that point and are assigned to machine should be less than or equal to (respectively greater than or equal to) the capacity associated with machine . A task overlaps a point if and only if (1)ย its origin is less than or equal to , and (2)ย its end is strictly greater than . It also imposes for each task of the constraint .
- Example
-
Figureย 5.101.1 shows with a thick line the cumulated profile on the two machines described by the collection. Within this profile a task with a positive (respectively negative) height is represented by a pink (respectively blue) rectangle, where the length of the rectangle corresponds to the duration of the task. The constraint holds since, both on machines 1 and 2, we have that at each point in time the cumulated resource consumption is greater than or equal to the limit 0 enforced by the last argument (i.e.,ย the attribute of the items of the collection) of the constraint (i.e.,ย we have a limit of 0 both on machines 1 and 2).
Figure 5.101.1. Resource consumption profiles on the different machines for the tasks of the Example slot
- Typical
- Symmetries
Items of are permutable.
Items of are permutable.
All occurrences of two distinct values in or can be swapped; all occurrences of a value in or can be renamed to any unused value.
- Arg. properties
Contractible wrt. when and .
- Usage
As shown in the Example slot, the constraint is useful for covering problems where different demand profiles have to be covered by a set of tasks. This is modelled in the following way:
To each demand profile is associated a given machine and a set of tasks for which all attributes (, , , , ) are fixed; moreover the attribute is fixed to and the attribute is strictly negative. For each machine the cumulated profile of all the previous tasks constitutes the demand profile to cover.
To each task that can be used to cover the demand is associated a task for which the attribute is a positive integer; the attribute describes the amount of demand that can be covered by the task at each instant during its execution (between its and its ) on the demand profile associated with the attribute.
In order to express the fact that each demand profile should completely be covered, we set the attribute of each machine to 0. We can also relax the constraint by setting the attribute to a negative number that specifies the maximum allowed uncovered demand at each instant.
The demand profiles might also not be completely fixed in advance.
When all the heights of the tasks are non-negative, one other possible use of the constraint is to enforce to reach a minimum level of resource consumption. This is imposed on those time points that are overlapped by at least one task.
By introducing a dummy task of height 0, of origin the minimum origin of all the tasks and of end the maximum end of all the tasks, this can also be imposed between the first and the last utilisation of the resource.
Finally the constraint is also useful for scheduling problems where several cumulative machines are available and where you have to assign each task on a specific machine.
- Algorithm
Three filtering algorithms for this constraint are described inย [BeldiceanuCarlsson02a].
- Systems
cumulatives in Gecode, cumulatives in SICStus.
- See also
assignment dimension removed: ย (negative not allowed).
common keyword: ย (scheduling constraint), ย (resource constraint).
generalisation: ย ( with and attributes replaced by orthotope).
- Keywords
application area: workload covering.
characteristic of a constraint: derived collection.
complexity: sequencing with release times and deadlines.
constraint type: scheduling constraint, resource constraint, temporal constraint, timetabling constraint.
filtering: compulsory part, sweep.
modelling: assignment dimension, assignment to the same set of values, scheduling with machine choice, calendars and preemption, zero-duration task.
modelling exercises: assignment to the same set of values, scheduling with machine choice, calendars and preemption.
- Derived Collection
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
For all items of :
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
-
- Graph class
-
- Sets
-
- Constraint(s) on sets
- Graph model
Within the context of the second graph constraint, partย (A) of Figureย 5.101.2 shows the initial graphs associated with machines 1 and 2 of the Example slot. Partย (B) of Figureย 5.101.2 shows the corresponding final graphs associated with machines 1 and 2. On the one hand, each source vertex of the final graph can be interpreted as a time point on a specific machine . On the other hand the successors of a source vertex correspond to those tasks that both overlap that time point and are assigned to machine . Since they do not have any successors we have eliminated those vertices corresponding to the end of the last three tasks of the collection. The constraint holds since for each successor set of the final graph the sum of the height of the tasks in is greater than or equal to the capacity of the machine corresponding to the time point associated with .
Figure 5.101.2. Initial and final graph of the constraint
(a) (b) - Signature
Since is the maximum number of vertices of the final graph of the first graph constraint we can rewrite to . This leads to simplify to .