[BeldiceanuCarlsson02a]

$\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜}(\mathrm{𝚃𝙰𝚂𝙺𝚂},\mathrm{𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂},\mathrm{𝙲𝚃𝚁})$

Figure 5.101.1 shows with a thick line the cumulated profile on the two machines described by the $\mathrm{𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂}$ 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 $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜}$ 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 $\mathrm{𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢}$ of the items of the $\mathrm{𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂}$ collection) of the $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜}$ 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

• Items of $\mathrm{𝚃𝙰𝚂𝙺𝚂}$ are permutable.

• Items of $\mathrm{𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂}$ are permutable.

• All occurrences of two distinct values in $\mathrm{𝚃𝙰𝚂𝙺𝚂}.\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}$ or $\mathrm{𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂}.\mathrm{𝚒𝚍}$ can be swapped; all occurrences of a value in $\mathrm{𝚃𝙰𝚂𝙺𝚂}.\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}$ or $\mathrm{𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂}.\mathrm{𝚒𝚍}$ can be renamed to any unused value.

Contractible wrt. $\mathrm{𝚃𝙰𝚂𝙺𝚂}$ when $\mathrm{𝚁𝙴𝙻𝙾𝙿}\in [\le ]$ and $\mathrm{𝚖𝚒𝚗𝚟𝚊𝚕}(\mathrm{𝚃𝙰𝚂𝙺𝚂}.\mathrm{𝚑𝚎𝚒𝚐𝚑𝚝})\ge 0$.

As shown in the Example slot, the $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜}$ 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 ($\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}$, $\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}$, $\mathrm{𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗}$, $\mathrm{𝚎𝚗𝚍}$, $\mathrm{𝚑𝚎𝚒𝚐𝚑𝚝}$) are fixed; moreover the $\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}$ attribute is fixed to $m$ and the $\mathrm{𝚑𝚎𝚒𝚐𝚑𝚝}$ 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 $\mathrm{𝚑𝚎𝚒𝚐𝚑𝚝}$ attribute is a positive integer; the $\mathrm{𝚑𝚎𝚒𝚐𝚑𝚝}$ attribute describes the amount of demand that can be covered by the task at each instant during its execution (between its $\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}$ and its $\mathrm{𝚎𝚗𝚍}$) on the demand profile associated with the $\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}$ attribute.

• In order to express the fact that each demand profile should completely be covered, we set the $\mathrm{𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢}$ attribute of each machine to 0. We can also relax the constraint by setting the $\mathrm{𝚌𝚊𝚙𝚊𝚌𝚒𝚝𝚢}$ 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 $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜}$ 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 $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜}$ 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.

Three filtering algorithms for this constraint are described in [BeldiceanuCarlsson02a].

cumulatives in Gecode, cumulatives in SICStus.

assignment dimension removed: $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ (negative $\mathrm{𝚑𝚎𝚒𝚐𝚑𝚝𝚜}$ not allowed).

common keyword: $\mathrm{𝚌𝚊𝚕𝚎𝚗𝚍𝚊𝚛}$ (scheduling constraint), $\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍}\_\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜}$ (resource constraint).

generalisation: $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ ($\mathrm{𝚝𝚊𝚜𝚔}$ with $\mathrm{𝚖𝚊𝚌𝚑𝚒𝚗𝚎}$ $\mathrm{𝚊𝚜𝚜𝚒𝚐𝚗𝚖𝚎𝚗𝚝}$ and $\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}$ attributes replaced by orthotope).

used in graph description: $\mathrm{𝚜𝚞𝚖}\_\mathrm{𝚌𝚝𝚛}$.

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.

problems: producer-consumer, demand profile.