5.87. cumulatives

DESCRIPTIONLINKSGRAPH
Origin

[BeldiceanuCarlsson02a]

Constraint

๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ๐šœ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚,๐™ผ๐™ฐ๐™ฒ๐™ท๐™ธ๐™ฝ๐™ด๐š‚,๐™ฒ๐šƒ๐š)

Arguments
๐šƒ๐™ฐ๐š‚๐™บ๐š‚๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—๐š–๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ-๐š๐šŸ๐šŠ๐š›,๐š˜๐š›๐š’๐š๐š’๐š—-๐š๐šŸ๐šŠ๐š›,๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-๐š๐šŸ๐šŠ๐š›,๐šŽ๐š—๐š-๐š๐šŸ๐šŠ๐š›,๐š‘๐šŽ๐š’๐š๐š‘๐š-๐š๐šŸ๐šŠ๐š›
๐™ผ๐™ฐ๐™ฒ๐™ท๐™ธ๐™ฝ๐™ด๐š‚๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐š’๐š-๐š’๐š—๐š,๐šŒ๐šŠ๐š™๐šŠ๐šŒ๐š’๐š๐šข-๐š’๐š—๐š)
๐™ฒ๐šƒ๐š๐šŠ๐š๐š˜๐š–
Restrictions
๐š›๐šŽ๐šš๐šž๐š’๐š›๐šŽ๐š(๐šƒ๐™ฐ๐š‚๐™บ๐š‚,[๐š–๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ,๐š‘๐šŽ๐š’๐š๐š‘๐š])
๐š›๐šŽ๐šš๐šž๐š’๐š›๐šŽ_๐šŠ๐š_๐š•๐šŽ๐šŠ๐šœ๐š(2,๐šƒ๐™ฐ๐š‚๐™บ๐š‚,[๐š˜๐š›๐š’๐š๐š’๐š—,๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—,๐šŽ๐š—๐š])
๐š’๐š—_๐šŠ๐š๐š๐š›(๐šƒ๐™ฐ๐š‚๐™บ๐š‚,๐š–๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ,๐™ผ๐™ฐ๐™ฒ๐™ท๐™ธ๐™ฝ๐™ด๐š‚,๐š’๐š)
๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—โ‰ฅ0
๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š˜๐š›๐š’๐š๐š’๐š—โ‰ค๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐šŽ๐š—๐š
๐š›๐šŽ๐šš๐šž๐š’๐š›๐šŽ๐š(๐™ผ๐™ฐ๐™ฒ๐™ท๐™ธ๐™ฝ๐™ด๐š‚,[๐š’๐š,๐šŒ๐šŠ๐š™๐šŠ๐šŒ๐š’๐š๐šข])
๐š๐š’๐šœ๐š๐š’๐š—๐šŒ๐š(๐™ผ๐™ฐ๐™ฒ๐™ท๐™ธ๐™ฝ๐™ด๐š‚,๐š’๐š)
๐™ฒ๐šƒ๐šโˆˆ[โ‰ค,โ‰ฅ]
Purpose

Consider a set ๐’ฏ of tasks described by the ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ collection. When ๐™ฒ๐šƒ๐š is equal to โ‰ค (respectively โ‰ฅ), the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ๐šœ 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. A task overlaps a point i if and only if (1)ย its origin is less than or equal to i, and (2)ย its end is strictly greater than i. It also imposes for each task of ๐’ฏ the constraint ๐š˜๐š›๐š’๐š๐š’๐š—+๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—=๐šŽ๐š—๐š.

Example
๐š–๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ-1๐š˜๐š›๐š’๐š๐š’๐š—-2๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐šŽ๐š—๐š-4๐š‘๐šŽ๐š’๐š๐š‘๐š--2,๐š–๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ-1๐š˜๐š›๐š’๐š๐š’๐š—-1๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-4๐šŽ๐š—๐š-5๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š–๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ-1๐š˜๐š›๐š’๐š๐š’๐š—-4๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐šŽ๐š—๐š-6๐š‘๐šŽ๐š’๐š๐š‘๐š--1,๐š–๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ-1๐š˜๐š›๐š’๐š๐š’๐š—-2๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-3๐šŽ๐š—๐š-5๐š‘๐šŽ๐š’๐š๐š‘๐š-2,๐š–๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ-1๐š˜๐š›๐š’๐š๐š’๐š—-5๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐šŽ๐š—๐š-7๐š‘๐šŽ๐š’๐š๐š‘๐š-2,๐š–๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ-2๐š˜๐š›๐š’๐š๐š’๐š—-3๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐šŽ๐š—๐š-5๐š‘๐šŽ๐š’๐š๐š‘๐š--1,๐š–๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ-2๐š˜๐š›๐š’๐š๐š’๐š—-1๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-4๐šŽ๐š—๐š-5๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š’๐š-1 ๐šŒ๐šŠ๐š™๐šŠ๐šŒ๐š’๐š๐šข-0,๐š’๐š-2 ๐šŒ๐šŠ๐š™๐šŠ๐šŒ๐š’๐š๐šข-0,โ‰ฅ

Figureย 5.87.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.87.1. Resource consumption profile on the different machines
ctrs/cumulatives1
Typical
|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š–๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š˜๐š›๐š’๐š๐š’๐š—)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐šŽ๐š—๐š)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š)>1
๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—>0
๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐šโ‰ 0
|๐™ผ๐™ฐ๐™ฒ๐™ท๐™ธ๐™ฝ๐™ด๐š‚|>1
๐™ผ๐™ฐ๐™ฒ๐™ท๐™ธ๐™ฝ๐™ด๐š‚.๐šŒ๐šŠ๐š™๐šŠ๐šŒ๐š’๐š๐šข<๐šœ๐šž๐š–(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š)
|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|>|๐™ผ๐™ฐ๐™ฒ๐™ท๐™ธ๐™ฝ๐™ด๐š‚|
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.

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 m and a set of tasks for which all attributes (๐š–๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ, ๐š˜๐š›๐š’๐š๐š’๐š—, ๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—, ๐šŽ๐š—๐š, ๐š‘๐šŽ๐š’๐š๐š‘๐š) are fixed; moreover the ๐š–๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ attribute is fixed to m and the ๐š‘๐šŽ๐š’๐š๐š‘๐š 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 ๐š‘๐šŽ๐š’๐š๐š‘๐š 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).

used in graph description: ๐šœ๐šž๐š–_๐šŒ๐š๐š›.

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.

problems: producer-consumer, demand profile.

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)
โ€ข ๐š๐š’๐š–๐šŽ_๐š™๐š˜๐š’๐š—๐š๐šœ.๐š’๐š๐š–=๐™ผ๐™ฐ๐™ฒ๐™ท๐™ธ๐™ฝ๐™ด๐š‚.๐š’๐š
โ€ข ๐š๐š’๐š–๐šŽ_๐š™๐š˜๐š’๐š—๐š๐šœ.๐š’๐š๐š–=๐š๐šŠ๐šœ๐š”๐šœ.๐š–๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ
โ€ข ๐š๐š’๐š–๐šŽ_๐š™๐š˜๐š’๐š—๐š๐šœ.๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—>0
โ€ข ๐š๐šŠ๐šœ๐š”๐šœ.๐š˜๐š›๐š’๐š๐š’๐š—โ‰ค๐š๐š’๐š–๐šŽ_๐š™๐š˜๐š’๐š—๐š๐šœ.๐š™๐š˜๐š’๐š—๐š
โ€ข ๐š๐š’๐š–๐šŽ_๐š™๐š˜๐š’๐š—๐š๐šœ.๐š™๐š˜๐š’๐š—๐š<๐š๐šŠ๐šœ๐š”๐šœ.๐šŽ๐š—๐š
Graph class
โ€ข ๐™ฐ๐™ฒ๐šˆ๐™ฒ๐™ป๐™ธ๐™ฒ
โ€ข ๐™ฑ๐™ธ๐™ฟ๐™ฐ๐š๐šƒ๐™ธ๐šƒ๐™ด
โ€ข ๐™ฝ๐™พ_๐™ป๐™พ๐™พ๐™ฟ

Sets
๐–ฒ๐–ด๐–ข๐–ขโ†ฆ๐šœ๐š˜๐šž๐š›๐šŒ๐šŽ,๐šŸ๐šŠ๐š›๐š’๐šŠ๐š‹๐š•๐šŽ๐šœ-๐šŒ๐š˜๐š•๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚-๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐šŸ๐šŠ๐š›-๐š๐šŸ๐šŠ๐š›),๐š’๐š๐šŽ๐š–(๐šŸ๐šŠ๐š›-๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š)]

Constraint(s) on sets
๐šœ๐šž๐š–_๐šŒ๐š๐š›(๐šŸ๐šŠ๐š›๐š’๐šŠ๐š‹๐š•๐šŽ๐šœ,๐™ฒ๐šƒ๐š,๐™ผ๐™ฐ๐™ฒ๐™ท๐™ธ๐™ฝ๐™ด๐š‚.๐šŒ๐šŠ๐š™๐šŠ๐šŒ๐š’๐š๐šข)
Graph model

Within the context of the second graph constraint, partย (A) of Figureย 5.87.2 shows the initial graphs associated with machines 1 and 2 of the Example slot. Partย (B) of Figureย 5.87.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 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.87.2. Initial and final graph of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ๐šœ constraint
ctrs/cumulativesA
(a)
ctrs/cumulativesB
(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 ๐๐€๐‘๐‚ ยฏ.