cumulative
cumulative |
Purpose
This constraint states that the tasks requiring a resource do not exceed the resource capacity. The primary use of this constraint is to express resource constraints.
Synopsis
function cumulative(starts: array(integer) of cpvar, durations:array(integer) of cpvar, ends: array(integer) of cpvar, usages: array(integer) of cpvar, sizes: array(integer) of cpvar, C: integer) : cpctr
function cumulative(starts: array(integer) of cpvar, durations:array(integer) of cpvar, ends: array(integer) of cpvar, usages: array(integer) of cpvar, sizes: array(integer) of cpvar, C: array(integer) of integer) : cpctr
Arguments
|
starts
|
Array of variables representing the start times of the tasks
|
|
ends
|
Array of variables representing the completion times of the tasks
|
|
durations
|
Array of variables representing the durations of the tasks
|
|
usages
|
Array of variables representing the resource consumptions of the tasks
|
|
sizes
|
Array of variables representing the sizes of the tasks
|
|
C
|
integer representing the initial capacity of the resource (constant over time or capacity value for each time period)
|
Return value
A cumulative constraint ensuring that the maximal resource capacity is never exceded. More formally the constraint ensures that
startsj + durationsj = endsj for all j in Tasks
usagesj · durationsj = sizesj for all j in Tasks
∑j ∈ Tasks | t ∈ [UB(startj)..LB(endj)] usagesj ≤ Ct for all times t in the planning period
Example
The following example shows how to use the cumulative constraint to express resource constraints for five tasks using the same resource:
model "Cumulative scheduling"
uses "kalis"
declarations
TASKS = 1..5
obj : cpvar
starts, ends, durations, usages, sizes : array(TASKS) of cpvar
end-declarations
C := 2 ! Resource capacity
HORIZON := 10 ! Time horizon
! Setting up the variables representing task properties
forall (t in TASKS) do
starts(t).name:= "T"+t+".start"
ends(t).name:= "T"+t+".end"
durations(t).name:= "T"+t+".duration"
sizes(t).name:= "T"+t+".size"
usages(t).name:= "T"+t+".use"
0 <= starts(t); starts(t) <= HORIZON
0 <= ends(t); ends(t) <= HORIZON
t <= durations(t); durations(t) <= t+1
1 <= sizes(t); sizes(t) <= 100
1 <= usages(t); usages(t) <= 1
obj >= ends(t)
end-do
! Cumulative resource constraint
cumulative(starts, durations, ends, usages, sizes, C)
! Define the branching strategy
cp_set_branching(assign_var(KALIS_SMALLEST_MIN,KALIS_MIN_TO_MAX))
! Solve the problem
if cp_minimize(obj) then
cp_show_sol
write("Resource use profile: ")
forall(t in TASKS, time in 0..HORIZON)
if (starts(t).sol <= time) and (ends(t).sol > time) then
rload(time) += usages(t).sol
end-if
forall(time in 0..HORIZON) write(rload(time))
writeln
else
writeln("No solution found")
end-if
end-model
Related topics