5.60. coloured_cumulative

DESCRIPTIONLINKSGRAPH
Origin

Derived from ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ and ๐š—๐šŸ๐šŠ๐š•๐šž๐šŽ๐šœ.

Constraint

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

Synonym

๐šŒ๐š˜๐š•๐š˜๐š›๐šŽ๐š_๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ.

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

Consider the set ๐’ฏ of tasks described by the ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ collection. The ๐šŒ๐š˜๐š•๐š˜๐šž๐š›๐šŽ๐š_๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint enforces that, at each point in time, the number of distinct colours 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. For each task of ๐’ฏ it also imposes the constraint ๐š˜๐š›๐š’๐š๐š’๐š—+๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—=๐šŽ๐š—๐š.

Example
๐š˜๐š›๐š’๐š๐š’๐š—-1๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐šŽ๐š—๐š-3๐šŒ๐š˜๐š•๐š˜๐šž๐š›-1,๐š˜๐š›๐š’๐š๐š’๐š—-2๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-9๐šŽ๐š—๐š-11๐šŒ๐š˜๐š•๐š˜๐šž๐š›-2,๐š˜๐š›๐š’๐š๐š’๐š—-3๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-10๐šŽ๐š—๐š-13๐šŒ๐š˜๐š•๐š˜๐šž๐š›-3,๐š˜๐š›๐š’๐š๐š’๐š—-6๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-6๐šŽ๐š—๐š-12๐šŒ๐š˜๐š•๐š˜๐šž๐š›-2,๐š˜๐š›๐š’๐š๐š’๐š—-7๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐šŽ๐š—๐š-9๐šŒ๐š˜๐š•๐š˜๐šž๐š›-3,2

Figureย 5.60.1 shows the solution associated with the example. Each rectangle of the figure corresponds to a task of the ๐šŒ๐š˜๐š•๐š˜๐šž๐š›๐šŽ๐š_๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint. Tasks that have their colour attribute set to 1, 2 and 3 are respectively coloured in yellow, blue and pink. The ๐šŒ๐š˜๐š•๐š˜๐šž๐š›๐šŽ๐š_๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint holds since at each point in time we do not have more than ๐™ป๐™ธ๐™ผ๐™ธ๐šƒ=2 distinct colours.

Figure 5.60.1. A coloured cumulative solution with at most two distinct colours in parallel
ctrs/coloured_cumulative1
Typical
|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š˜๐š›๐š’๐š๐š’๐š—)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐šŽ๐š—๐š)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐šŒ๐š˜๐š•๐š˜๐šž๐š›)>1
๐™ป๐™ธ๐™ผ๐™ธ๐šƒ<๐š—๐šŸ๐šŠ๐š•(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐šŒ๐š˜๐š•๐š˜๐šž๐š›)
Symmetries
  • Items of ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ are permutable.

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

  • All occurrences of two distinct values of ๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐šŒ๐š˜๐š•๐š˜๐šž๐š› can be swapped; all occurrences of a value of ๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐šŒ๐š˜๐š•๐š˜๐šž๐š› can be renamed to any unused value.

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

Usage

Useful for scheduling problems where a machine can only proceed in parallel a maximum number of tasks of distinct type. This condition cannot be modelled by the classical ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint.

Reformulation

The ๐šŒ๐š˜๐š•๐š˜๐šž๐š›๐šŽ๐š_๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint can be expressed in term of a set of reified constraints and of |๐šƒ๐™ฐ๐š‚๐™บ๐š‚| ๐š—๐šŸ๐šŠ๐š•๐šž๐šŽ constraints:

  1. For each pair of tasks ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i],๐šƒ๐™ฐ๐š‚๐™บ๐š‚[j] (i,jโˆˆ[1,|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|]) of the ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ collection we create a variable C ij which is set to the colour of task ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[j] if task ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[j] overlaps the origin attribute of task ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i], and to the colour of task ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i] otherwise:

    • If i=j:

      • C ij =๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i].๐šŒ๐š˜๐š•๐š˜๐šž๐š›.

    • If iโ‰ j:

      • C ij =๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i].๐šŒ๐š˜๐š•๐š˜๐šž๐š›โˆจC ij =๐šƒ๐™ฐ๐š‚๐™บ๐š‚[j].๐šŒ๐š˜๐š•๐š˜๐šž๐š›.

      • ((๐šƒ๐™ฐ๐š‚๐™บ๐š‚[j].๐š˜๐š›๐š’๐š๐š’๐š—โ‰ค๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i].๐š˜๐š›๐š’๐š๐š’๐š— โˆง

        ย ย ย ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[j].๐šŽ๐š—๐š>๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i].๐š˜๐š›๐š’๐š๐š’๐š—)โˆง(C ij =๐šƒ๐™ฐ๐š‚๐™บ๐š‚[j].๐šŒ๐š˜๐š•๐š˜๐šž๐š›)) โˆจ

        ((๐šƒ๐™ฐ๐š‚๐™บ๐š‚[j].๐š˜๐š›๐š’๐š๐š’๐š—>๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i].๐š˜๐š›๐š’๐š๐š’๐š— โˆจ

        ย ย ย ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[j].๐šŽ๐š—๐šโ‰ค๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i].๐š˜๐š›๐š’๐š๐š’๐š—)โˆง(C ij =๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i].๐šŒ๐š˜๐š•๐š˜๐šž๐š›))

  2. For each task ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i] (iโˆˆ[1,|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|]) we create a variable N i which gives the number of distinct colours associated to the tasks that overlap the origin of task ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i] (๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i] overlaps its own origin) and we impose N i to not exceed the maximum number of distinct colours ๐™ป๐™ธ๐™ผ๐™ธ๐šƒ allowed at each instant:

See also

assignment dimension added: ๐šŒ๐š˜๐š•๐š˜๐šž๐š›๐šŽ๐š_๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ๐šœ.

common keyword: ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ, ๐š๐š›๐šŠ๐šŒ๐š”ย (resource constraint).

related: ๐š—๐šŸ๐šŠ๐š•๐šž๐šŽ.

specialisation: ๐š๐š’๐šœ๐š“๐š˜๐š’๐š—๐š_๐š๐šŠ๐šœ๐š”๐šœย (a colour is assigned to each collection of tasks of constraint ๐š๐š’๐šœ๐š“๐š˜๐š’๐š—๐š_๐š๐šŠ๐šœ๐š”๐šœ and a limit of one single colour is enforced).

used in graph description: ๐š—๐šŸ๐šŠ๐š•๐šž๐šŽ๐šœ.

Keywords

characteristic of a constraint: coloured.

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

filtering: compulsory part.

modelling: number of distinct values, zero-duration task.

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

Same as ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ, except that we use another constraint for computing the resource consumption at each time point.

Partsย (A) andย (B) of Figureย 5.60.2 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 number of distinct colours of the tasks in ๐’ฎ does not exceed the ๐™ป๐™ธ๐™ผ๐™ธ๐šƒ 2.

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