5.96. cumulative

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

[AggounBeldiceanu93]

Constraint

๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚,๐™ป๐™ธ๐™ผ๐™ธ๐šƒ)

Synonym

๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐š–๐šŠ๐šก.

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

Cumulative scheduling constraint or scheduling under resource constraints. Consider a set ๐’ฏ of tasks described by the ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ collection. The ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint enforces that at each point in time, the cumulated height of the set of tasks that overlap that point, does not exceed a given limit. 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๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-3๐šŽ๐š—๐š-4๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š˜๐š›๐š’๐š๐š’๐š—-2๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-9๐šŽ๐š—๐š-11๐š‘๐šŽ๐š’๐š๐š‘๐š-2,๐š˜๐š›๐š’๐š๐š’๐š—-3๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-10๐šŽ๐š—๐š-13๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š˜๐š›๐š’๐š๐š’๐š—-6๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-6๐šŽ๐š—๐š-12๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š˜๐š›๐š’๐š๐š’๐š—-7๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐šŽ๐š—๐š-9๐š‘๐šŽ๐š’๐š๐š‘๐š-3,8
Figure 5.96.1. Resource consumption profile corresponding to the five tasks of the Example slot (note that the vertical position of a task does not really matter but is only used for displaying the contribution of a task to the resource consumption profile)
ctrs/cumulative-1-tikz

Figureย 5.96.1 shows the cumulated profile associated with the example. To each task of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint, i.e.ย each line of the example, corresponds a set of rectangles coloured with the same colour: the sum of the lengths of the rectangles corresponds to the duration of the task, while the height of the rectangles (i.e., all the rectangles associated with a task have the same height) corresponds to the resource consumption of the task. The ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint holds since at each point in time we do not have a cumulated resource consumption strictly greater than the upper limit 8 enforced by the last argument of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint.

All solutions

Figureย 5.96.2 gives all solutions to the following non ground instance of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint:

O 1 โˆˆ[1,5], D 1 โˆˆ[4,4], E 1 โˆˆ[1,9], H 1 โˆˆ[2,6],

O 2 โˆˆ[2,7], D 2 โˆˆ[6,6], E 2 โˆˆ[1,9], H 2 โˆˆ[3,3],

O 3 โˆˆ[3,6], D 3 โˆˆ[3,6], E 3 โˆˆ[1,9], H 3 โˆˆ[1,2],

O 4 โˆˆ[1,8], D 4 โˆˆ[2,3], E 4 โˆˆ[1,9], H 4 โˆˆ[3,4],

๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ(โŒฉO 1 D 1 E 1 H 1 1, O 2 D 2 E 2 H 2 2, O 3 D 3 E 3 H 3 3, O 4 D 4 E 4 H 4 4โŒช,5).

Figure 5.96.2. All solutions corresponding to the non ground example of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint of the All solutions slot
ctrs/cumulative-2-tikz
Typical
|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š˜๐š›๐š’๐š๐š’๐š—)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐šŽ๐š—๐š)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š)>1
๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—>0
๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š>0
๐™ป๐™ธ๐™ผ๐™ธ๐šƒ<๐šœ๐šž๐š–(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š)
Symmetries
  • Items of ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ are permutable.

  • ๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š— can be decreased to any value โ‰ฅ0.

  • ๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š can be decreased to any value โ‰ฅ0.

  • One and the same constant can be added to the ๐š˜๐š›๐š’๐š๐š’๐š— and ๐šŽ๐š—๐š attributes of all items of ๐šƒ๐™ฐ๐š‚๐™บ๐š‚.

  • ๐™ป๐™ธ๐™ผ๐™ธ๐šƒ can be increased.

Arg. properties

Contractible wrt. ๐šƒ๐™ฐ๐š‚๐™บ๐š‚.

Usage

The ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint occurs in most resource scheduling problems where one has to deal with renewable and/or non-renewable resources:

  • Renewable resources typically correspond to machines or persons, and tasks require such resources during all their execution (i.e. a resource starts to be used at the beginning of the task and is released at the end of the task). This means that, once a task has finished its work, the resource it was using is available for other tasks. Tasks are defined by their origin, duration, end and resource consumption and can not be interrupted. When the duration and resource consumption are not fixed tasks can be defined by their load, i.e.ย the product of their duration and resource consumption. To express the dependency between a non-fixed duration/resource consumption of a task with another decision variable (e.g.,ย to state that the duration of a task depends on its start) one can use the ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š constraint where the decision variable corresponds to the index argument of the ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š constraint.

  • Non renewable resources typically correspond to stock or money, i.e., resources that do not come back when a task finishes to use them. In this context the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint is used for modelling producer-consumer problems, i.e.ย problems where a first set of tasks produces a non-renewable resource, while a second set of tasks consumes this resource so that a limit on the minimum or the maximum stock at each instant is imposed.

The ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint is also used as a necessary condition for non-overlapping rectangles (see the ๐š๐š’๐š๐š๐š— constraint).

Remark

In the original ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint of CHIP the ๐™ป๐™ธ๐™ผ๐™ธ๐šƒ parameter was a domain variable corresponding to the maximum peak of the resource consumption profile. Given a fixed time frame, this variable could be used as a cost in order to directly minimise the maximum resource consumption peak. Fixing this variable is potentially dangerous since it imposes the maximum peak to be equal to a given target value.

Some systems like Ilogย CPย Optimizer also assume that a zero-duration task overlaps a point i if and only if (1)ย its origin is less than or equal to i, and (2)ย its end is greater than or equal to i. Under this definition, the height of a zero-duration task is also taken into account in the resource consumption profile.

Note that the concept of cumulative is different from the concept of rectangles non-overlapping even though, most of the time, each task of a ground solution to a ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint is simply drawn as a single rectangle. As illustrated by Figureย 5.118.7, this is in fact not always possible (i.e., some rectangles may need to be broken apart). In fact the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint is only a necessary condition for rectangles non-overlapping (see Figureย 5.118.6 and the corresponding explanation in the Algorithm slot of the ๐š๐š’๐š๐š๐š— constraint).

In MiniZinc (http://www.minizinc.org/) the tasks of a ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint have no ๐šŽ๐š—๐š attribute.

Algorithm

The first filtering algorithms were related to the notion of compulsory part of a taskย [Lahrichi82]. They compute a cumulated resource profile of all the compulsory parts of the tasks and prune the origins of the tasks with respect to this profile in order to not exceed the resource capacity. These methods are sometimes called time tabling. Even though these methods are quite local, i.e., a task has a non-empty compulsory part only when the difference between its latest start and its earliest start is strictly less than its duration, it scales well and is therefore widely used. Later on, more global algorithmsEven though these more global algorithms usually can prune more early in the search tree, these algorithms do not catch all deductions derived from the cumulated resource profile of compulsory parts. based on the resource consumption of the tasks on specific intervals were introducedย [ErschlerLopez90], [CaseauLaburthe96b], [Lock96]. A popular variant, called edge finding, considers only specific intervalsย [MercierVanHentenryck08]. An efficient implementation of edge finding in O(knlogn), where k is the number of distinct task heights and n is the number of tasks, based on a specific data structure, so called a cumulative ฮฆ-treeย [Vilim09a], is provided inย [Vilim09b]. When the number of distinct task heights k is not small, a usually almost faster implementation in O(n 2 ) is described inย [KameugneFotsoScottNgoKateu11]. A O(n 2 logn) filtering algorithm based on tasks that can not be the earliest (or not be the latest) is described inย [SchuttWolf10].

Within the context of linear programming, the referenceย [HookerYan02] provides a relaxation of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint.

A necessary condition for the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint is obtained by stating a ๐š๐š’๐šœ๐š“๐šž๐š—๐šŒ๐š๐š’๐šŸ๐šŽ constraint on a subset of tasks ๐’ฏ such that, for each pair of tasks of ๐’ฏ, the sum of the two corresponding minimum heights is strictly greater than ๐™ป๐™ธ๐™ผ๐™ธ๐šƒ. This can be done by applying the following procedure:

  • Let h be the smallest minimum height strictly greater than โŒŠ๐™ป๐™ธ๐™ผ๐™ธ๐šƒ 2โŒ‹ of the tasks of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint. If no such task exists then the procedure is stopped without stating any ๐š๐š’๐šœ๐š“๐šž๐š—๐šŒ๐š๐š’๐šŸ๐šŽ constraint.

  • Let ๐’ฏ h denote the set of tasks of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint for which the minimum height is greater than or equal to h. By construction, the tasks of ๐’ฏ h cannot overlap. But we can possibly add one more task as shown by the next step.

  • When it exists, we can add one task that does not belong to ๐’ฏ h and such that its minimum height is strictly greater than ๐™ป๐™ธ๐™ผ๐™ธ๐šƒ-h. Again, by construction, this task cannot overlap all the tasks of ๐’ฏ h .

When the tasks are involved in several ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraints more sophisticated methods are available for extracting ๐š๐š’๐šœ๐š“๐šž๐š—๐šŒ๐š๐š’๐šŸ๐šŽ constraintsย [BaptisteLePape00], [BaptisteDemassey04].

In the context where, both the duration and height of all the tasks are fixed, [BeldiceanuCarlssonPoder08] provides two kinds of additional filtering algorithms that are especially useful when the slack ฯƒ (i.e., the difference between the available space and the sum of the surfaces of the tasks) is very small:

  • The first one introduces bounds for the so called cumulative longest hole problem. Given an integer ฯต that does not exceed the resource limit, and a subset of tasks ๐’ฏ ' for which the resource consumption is a most ฯต, the cumulative longest hole problem is to find the largest integer ๐‘™๐‘š๐‘Ž๐‘ฅ ฯƒ ฯต (๐’ฏ ' ) such that there is a cumulative placement of maximum height ฯต involving a subset of tasks of ๐’ฏ ' where, on one interval [i,i+๐‘™๐‘š๐‘Ž๐‘ฅ ฯƒ ฯต (๐’ฏ ' )-1] of the cumulative profile, the area of the empty space does not exceed ฯƒ.

  • The second one used dynamic programming for filtering so called balancing knapsack constraints. When the slack is 0, such constraints express that the total height of tasks ending at instant i must equal the total height of tasks starting at instant i. Such constraints can be generalised to non-zero slack.

Systems

cumulativeMax in Choco, cumulative in Gecode, cumulative in JaCoP, cumulative in MiniZinc, cumulative in SICStus.

See also

assignment dimension added: ๐šŒ๐š˜๐š•๐š˜๐šž๐š›๐šŽ๐š_๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ๐šœย (sum of ๐š๐šŠ๐šœ๐š” ๐š‘๐šŽ๐š’๐š๐š‘๐š๐šœ replaced by number of distinct ๐šŒ๐š˜๐š•๐š˜๐šž๐š›๐šœ, assignment dimension added), ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ๐šœย (negative ๐š‘๐šŽ๐š’๐š๐š‘๐š๐šœ allowed and assignment dimension added).

common keyword: ๐šŒ๐šŠ๐š•๐šŽ๐š—๐š๐šŠ๐š›ย (scheduling constraint), ๐šŒ๐š˜๐š•๐š˜๐šž๐š›๐šŽ๐š_๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽย (resource constraint, sum of ๐š๐šŠ๐šœ๐š” ๐š‘๐šŽ๐š’๐š๐š‘๐š๐šœ replaced by number of distinct values), ๐šŒ๐š˜๐š•๐š˜๐šž๐š›๐šŽ๐š_๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ๐šœย (resource constraint), ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šกย (resource constraint, ๐š๐šŠ๐šœ๐š” defined by a set of ๐š™๐š˜๐š’๐š—๐š๐šœ), ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐š™๐š›๐š˜๐š๐šž๐šŒ๐šย (resource constraint, sum of ๐š๐šŠ๐šœ๐š” ๐š‘๐šŽ๐š’๐š๐š‘๐š๐šœ replaced by product of ๐š๐šŠ๐šœ๐š” ๐š‘๐šŽ๐š’๐š๐š‘๐š๐šœ), ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐š ๐š’๐š๐š‘_๐š•๐šŽ๐šŸ๐šŽ๐š•_๐š˜๐š_๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šขย (resource constraint, a ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint for each set of ๐š๐šŠ๐šœ๐š”๐šœ having a priority less than or equal to a given threshold).

generalisation: ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐š๐š ๐š˜_๐šย (๐š๐šŠ๐šœ๐š” replaced by ๐š›๐šŽ๐šŒ๐š๐šŠ๐š—๐š๐š•๐šŽ with a ๐š‘๐šŽ๐š’๐š๐š‘๐š).

implied by: ๐š๐š’๐š๐š๐š—ย (๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ is a neccessary condition for each dimension of the ๐š๐š’๐š๐š๐š— constraint).

related: ๐š•๐šŽ๐šก_๐šŒ๐š‘๐šŠ๐š’๐š—_๐š•๐šŽ๐šœ๐šœ, ๐š•๐šŽ๐šก_๐šŒ๐š‘๐šŠ๐š’๐š—_๐š•๐šŽ๐šœ๐šœ๐šŽ๐ššย (lexicographic ordering on the origins of ๐š๐šŠ๐šœ๐š”๐šœ, ๐š›๐šŽ๐šŒ๐š๐šŠ๐š—๐š๐š•๐šŽ๐šœ, ...), ๐š˜๐š›๐š๐šŽ๐š›๐šŽ๐š_๐š๐š•๐š˜๐š‹๐šŠ๐š•_๐šŒ๐šŠ๐š›๐š๐š’๐š—๐šŠ๐š•๐š’๐š๐šขย (controlling the shape of the cumulative profile for breaking symmetry).

soft variant: ๐šœ๐š˜๐š๐š_๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ.

specialisation: ๐šŠ๐š๐š–๐š˜๐šœ๐šย (๐š๐šŠ๐šœ๐š” replaced by ๐šŸ๐šŠ๐š›๐š’๐šŠ๐š‹๐š•๐šŽ), ๐š‹๐š’๐š—_๐š™๐šŠ๐šŒ๐š”๐š’๐š—๐šย (all ๐š๐šŠ๐šœ๐š”๐šœ have a ๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š— of 1 and a fixed ๐š‘๐šŽ๐š’๐š๐š‘๐š), ๐š๐š’๐šœ๐š“๐šž๐š—๐šŒ๐š๐š’๐šŸ๐šŽย (all ๐š๐šŠ๐šœ๐š”๐šœ have a ๐š‘๐šŽ๐š’๐š๐š‘๐š of 1), ๐š–๐šž๐š•๐š๐š’_๐š’๐š—๐š๐šŽ๐š›_๐š๐š’๐šœ๐š๐šŠ๐š—๐šŒ๐šŽย (all ๐š๐šŠ๐šœ๐š”๐šœ have the same ๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š— equal to ๐™ณ๐™ธ๐š‚๐šƒ and the same ๐š‘๐šŽ๐š’๐š๐š‘๐š equal to 1).

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

Keywords

characteristic of a constraint: core, automaton, automaton with array of counters.

complexity: sequencing with release times and deadlines.

constraint type: scheduling constraint, resource constraint, temporal constraint.

filtering: linear programming, dynamic programming, compulsory part, cumulative longest hole problems, Phi-tree.

modelling: zero-duration task.

problems: producer-consumer.

puzzles: squared squares.

Cond. implications

๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚,๐™ป๐™ธ๐™ผ๐™ธ๐šƒ)

ย ย ย  withย  ๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š>0

ย ย implies ๐šŒ๐š˜๐š•๐š˜๐šž๐š›๐šŽ๐š_๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚:๐šƒ๐™ฐ๐š‚๐™บ๐š‚,๐™ป๐™ธ๐™ผ๐™ธ๐šƒ:๐™ป๐™ธ๐™ผ๐™ธ๐šƒ).

Arc input(s)

๐šƒ๐™ฐ๐š‚๐™บ๐š‚

Arc generator
๐‘†๐ธ๐ฟ๐นโ†ฆ๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐š๐šŠ๐šœ๐š”๐šœ)

Arc arity
Arc constraint(s)
๐š๐šŠ๐šœ๐š”๐šœ.๐š˜๐š›๐š’๐š๐š’๐š—+๐š๐šŠ๐šœ๐š”๐šœ.๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—=๐š๐šŠ๐šœ๐š”๐šœ.๐šŽ๐š—๐š
Graph property(ies)
๐๐€๐‘๐‚=|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|

Arc input(s)

๐šƒ๐™ฐ๐š‚๐™บ๐š‚ ๐šƒ๐™ฐ๐š‚๐™บ๐š‚

Arc generator
๐‘ƒ๐‘…๐‘‚๐ท๐‘ˆ๐ถ๐‘‡โ†ฆ๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐š๐šŠ๐šœ๐š”๐šœ1,๐š๐šŠ๐šœ๐š”๐šœ2)

Arc arity
Arc constraint(s)
โ€ข ๐š๐šŠ๐šœ๐š”๐šœ1.๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—>0
โ€ข ๐š๐šŠ๐šœ๐š”๐šœ2.๐š˜๐š›๐š’๐š๐š’๐š—โ‰ค๐š๐šŠ๐šœ๐š”๐šœ1.๐š˜๐š›๐š’๐š๐š’๐š—
โ€ข ๐š๐šŠ๐šœ๐š”๐šœ1.๐š˜๐š›๐š’๐š๐š’๐š—<๐š๐šŠ๐šœ๐š”๐šœ2.๐šŽ๐š—๐š
Graph class
โ€ข ๐™ฐ๐™ฒ๐šˆ๐™ฒ๐™ป๐™ธ๐™ฒ
โ€ข ๐™ฑ๐™ธ๐™ฟ๐™ฐ๐š๐šƒ๐™ธ๐šƒ๐™ด
โ€ข ๐™ฝ๐™พ_๐™ป๐™พ๐™พ๐™ฟ

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

Constraint(s) on sets
๐šœ๐šž๐š–_๐šŒ๐š๐š›(๐šŸ๐šŠ๐š›๐š’๐šŠ๐š‹๐š•๐šŽ๐šœ,โ‰ค,๐™ป๐™ธ๐™ผ๐™ธ๐šƒ)
Graph model

The first graph constraint forces for each task the link between its origin, its duration and its end. The second graph constraint makes sure, for each time point t corresponding to the start of a task, that the cumulated heights of the tasks that overlap t does not exceed the limit of the resource.

Partsย (A) andย (B) of Figureย 5.96.3 respectively show the initial and final graph associated with the second graph constraint of the Example slot. On the one hand, each source vertex of the final graph can be interpreted as a time point. On the other hand the successors of a source vertex correspond to those tasks that overlap that time point. The ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint holds since for each successor set ๐’ฎ of the final graph the sum of the heights of the tasks in ๐’ฎ does not exceed the limit ๐™ป๐™ธ๐™ผ๐™ธ๐šƒ=8.

Figure 5.96.3. Initial and final graph of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint
ctrs/cumulativeA
(a)
ctrs/cumulativeB
(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 ๐๐€๐‘๐‚ ยฏ.

Automaton

Figureย 5.96.4 depicts the automaton associated with the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint. To each item of the collection ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ corresponds a signature variable S i that is equal to 1.

Figure 5.96.4. Automaton of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint
ctrs/cumulative-3-tikz
Quiz

ย ย 

๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ: checking whether a ground instance holds or not ctrs/cumulative-4-tikz ย 

๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ: finding all solutions ctrs/cumulative-5-tikz ย 

ctrs/cumulative-6-tikz ย 

ctrs/cumulative-7-tikz