5.84. cumulatives
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
cumulatives(TASKS,MACHINES,CTR)
- Argument(s)
-
TASKS collection(
)machine−dvar, origin−dvar, duration−dvar, end−dvar, height−dvar MACHINES collection(id−int,capacity−int) CTR atom - Restriction(s)
-
required(TASKS,[machine,height]) require_at_least(2,TASKS,[origin,duration,end]) in_attr(TASKS,machine,MACHINES,id) TASKS.duration≥0 TASKS.origin≤TASKS.end required(MACHINES,[id,capacity]) distinct(MACHINES,id) CTR∈[≤,≥] - Purpose
Consider a set T of tasks described by the TASKS collection. When CTR is equal to ≤ (respectively ≥), the cumulatives constraint enforces the following condition for each machine m: At each point in time, where at least one task assigned on machine m is present, the cumulated height of the set of tasks that both overlap that point and are assigned to machine m should be less than or equal to (respectively greater than or equal to) the capacity associated with machine m. It also imposes for each task of T the constraint origin+duration=end.
- Example
-
(
)〈
〉,machine−1 origin−2 duration−2 end−4 height−−2, machine−1 origin−1 duration−4 end−5 height−1, machine−1 origin−4 duration−2 end−6 height−−1, machine−1 origin−2 duration−3 end−5 height−2, machine−1 origin−5 duration−2 end−7 height−2, machine−2 origin−3 duration−2 end−5 height−−1, machine−2 origin−1 duration−4 end−5 height−1 〈id−1 capacity−0,id−2 capacity−0〉,≥ Figure 5.84.1 shows with a thick line the cumulated profile on the two machines described by the MACHINES 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 cumulatives 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 capacity of the items of the MACHINES collection) of the cumulatives constraint (i.e., we have a limit of 0 both on machines 1 and 2).
Figure 5.84.1. Resource consumption profile on the different machines
- Usage
As shown in the Example slot, the cumulatives 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 m and a set of tasks for which all attributes (machine, origin, duration, end, height) are fixed; moreover the machine attribute is fixed to m and the height attribute is strictly negative. For each machine m 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 height attribute is a positive integer; the height attribute describes the amount of demand that can be covered by the task at each instant during its execution (between its origin and its end) on the demand profile associated with the machine attribute.
In order to express the fact that each demand profile should completely be covered, we set the capacity attribute of each machine to 0. We can also relax the constraint by setting the capacity 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 cumulatives 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 cumulatives 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
- Key words
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.
- Derived Collection(s)
-
col(
)TIME_POINTS−collection(idm−int,duration−dvar,point−dvar), [
]item(idm−TASKS.machine,duration−TASKS.duration,point−TASKS.origin), item(idm−TASKS.machine,duration−TASKS.duration,point−TASKS.end)
- Arc input(s)
TASKS
- Arc generator
-
SELF↦collection(tasks) - Arc arity
-
1 - Arc constraint(s)
-
tasks.origin+tasks.duration=tasks.end - Graph property(ies)
-
NARC=|TASKS|
For all items of MACHINES:
- Arc input(s)
TIME_POINTS TASKS
- Arc generator
-
PRODUCT↦collection(time_points,tasks) - Arc arity
-
2 - Arc constraint(s)
-
• time_points.idm=MACHINES.id • time_points.idm=tasks.machine • time_points.duration>0 • tasks.origin≤time_points.point • time_points.point<tasks.end - Graph class
-
• ACYCLIC • BIPARTITE • NO_LOOP - Sets
-
SUCC↦ [
]source, variables−col(
)VARIABLES−collection(var−dvar), item(var−TASKS.height)] - Constraint(s) on sets
-
sum_ctr(variables,CTR,MACHINES.capacity)
- Graph model
Within the context of the second graph constraint, part (A) of Figure 5.84.2 shows the initial graphs associated with machines 1 and 2 of the Example slot. Part (B) of Figure 5.84.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 p on a specific machine m. On the other hand the successors of a source vertex correspond to those tasks that both overlap that time point p and are assigned to machine m. Since they don't have any successors we have eliminated those vertices corresponding to the end of the last three tasks of the TASKS collection. The cumulatives constraint holds since for each successor set S of the final graph the sum of the height of the tasks in S is greater than or equal to the capacity of the machine corresponding to the time point associated with S.
Figure 5.84.2. Initial and final graph of the cumulatives constraint
(a) 
(b) - Signature
Since TASKS is the maximum number of vertices of the final graph of the first graph constraint we can rewrite NARC=|TASKS| to NARC≥|TASKS|. This leads to simplify to .