5.86. cumulative_with_level_of_priority

DESCRIPTIONLINKSGRAPH
Origin

H.ย Simonis

Constraint

๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐š ๐š’๐š๐š‘_๐š•๐šŽ๐šŸ๐šŽ๐š•_๐š˜๐š_๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข(๐šƒ๐™ฐ๐š‚๐™บ๐š‚,๐™ฟ๐š๐™ธ๐™พ๐š๐™ธ๐šƒ๐™ธ๐™ด๐š‚)

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

Consider a set ๐’ฏ of tasks described by the ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ collection where each task has a given priority chosen in the range [1,๐™ฟ๐š๐™ธ๐™พ๐š๐™ธ๐šƒ๐™ธ๐™ด๐š‚]. Let ๐’ฏ i denote the subset of tasks of ๐’ฏ that all have a priority less than or equal to i. For each set ๐’ฏ i , 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. Finally, it also imposes for each task of ๐’ฏ the constraint ๐š˜๐š›๐š’๐š๐š’๐š—+๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—=๐šŽ๐š—๐š.

Example
๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข-1๐š˜๐š›๐š’๐š๐š’๐š—-1๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐šŽ๐š—๐š-3๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข-1๐š˜๐š›๐š’๐š๐š’๐š—-2๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-3๐šŽ๐š—๐š-5๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข-1๐š˜๐š›๐š’๐š๐š’๐š—-5๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐šŽ๐š—๐š-7๐š‘๐šŽ๐š’๐š๐š‘๐š-2,๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข-2๐š˜๐š›๐š’๐š๐š’๐š—-3๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐šŽ๐š—๐š-5๐š‘๐šŽ๐š’๐š๐š‘๐š-2,๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข-2๐š˜๐š›๐š’๐š๐š’๐š—-6๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-3๐šŽ๐š—๐š-9๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š’๐š-1 ๐šŒ๐šŠ๐š™๐šŠ๐šŒ๐š’๐š๐šข-2,๐š’๐š-2 ๐šŒ๐šŠ๐š™๐šŠ๐šŒ๐š’๐š๐šข-3

Figureย 5.86.1 shows the cumulated profile associated with both levels of priority. To each task of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐š ๐š’๐š๐š‘_๐š•๐šŽ๐šŸ๐šŽ๐š•_๐š˜๐š_๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข constraint corresponds a set of rectangles containing the same number (i.e.,ย the position of the task within the ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ collection): 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. Tasks that have a priority of 1 are coloured in pink, while tasks that have a priority of 2 are coloured in blue. The ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐š ๐š’๐š๐š‘_๐š•๐šŽ๐šŸ๐šŽ๐š•_๐š˜๐š_๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข constraint holds since:

  • At each point in time the cumulated resource consumption profile of the tasks of priority 1 does not exceed the upper capacity 2 enforced by the first item of the ๐™ฟ๐š๐™ธ๐™พ๐š๐™ธ๐šƒ๐™ธ๐™ด๐š‚ collection.

  • At each point in time the cumulated resource consumption profile of the tasks of priority 1 and 2 does not exceed the upper capacity 3 enforced by the second item of the ๐™ฟ๐š๐™ธ๐™พ๐š๐™ธ๐šƒ๐™ธ๐™ด๐š‚ collection.

Figure 5.86.1. Resource consumption profile according to both levels of priority
ctrs/cumulative_with_level_of_priority1
Typical
|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š˜๐š›๐š’๐š๐š’๐š—)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐šŽ๐š—๐š)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š)>1
๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—>0
๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š>0
|๐™ฟ๐š๐™ธ๐™พ๐š๐™ธ๐šƒ๐™ธ๐™ด๐š‚|>1
๐™ฟ๐š๐™ธ๐™พ๐š๐™ธ๐šƒ๐™ธ๐™ด๐š‚.๐šŒ๐šŠ๐š™๐šŠ๐šŒ๐š’๐š๐šข>0
๐™ฟ๐š๐™ธ๐™พ๐š๐™ธ๐šƒ๐™ธ๐™ด๐š‚.๐šŒ๐šŠ๐š™๐šŠ๐šŒ๐š’๐š๐šข<๐šœ๐šž๐š–(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š)
|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|>|๐™ฟ๐š๐™ธ๐™พ๐š๐™ธ๐šƒ๐™ธ๐™ด๐š‚|
Symmetries
  • Items of ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ are permutable.

  • ๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข can be increased to any value โ‰ค|๐™ฟ๐š๐™ธ๐™พ๐š๐™ธ๐šƒ๐™ธ๐™ด๐š‚|.

  • ๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š 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.

Usage

The ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐š ๐š’๐š๐š‘_๐š•๐šŽ๐šŸ๐šŽ๐š•_๐š˜๐š_๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข constraint was suggested by problems from the telecommunication area where one has to ensure different levels of quality of service. For this purpose the capacity of a transmission link is splitted so that a given percentage is reserved to each level. In addition we have that, if the capacities allocated to levels 1,2,...,i is not completely used, then level i+1 can use the corresponding spare capacity.

Remark

The ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐š ๐š’๐š๐š‘_๐š•๐šŽ๐šŸ๐šŽ๐š•_๐š˜๐š_๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข constraint can be modelled by a conjunction of ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraints. As shown by the next example, the consistency for all variables of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraints does not implies consistency for the corresponding ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐š ๐š’๐š๐š‘_๐š•๐šŽ๐šŸ๐šŽ๐š•_๐š˜๐š_๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข constraint. The following ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐š ๐š’๐š๐š‘_๐š•๐šŽ๐šŸ๐šŽ๐š•_๐š˜๐š_๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข constraint

๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข-1๐š˜๐š›๐š’๐š๐š’๐š—-o 1 ๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐š‘๐šŽ๐š’๐š๐š‘๐š-2,๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข-1๐š˜๐š›๐š’๐š๐š’๐š—-o 2 ๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข-2๐š˜๐š›๐š’๐š๐š’๐š—-o 3 ๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-1๐š‘๐šŽ๐š’๐š๐š‘๐š-3,๐š’๐š-1๐šŒ๐šŠ๐š™๐šŠ๐šŒ๐š’๐š๐šข-2,๐š’๐š-2๐šŒ๐šŠ๐š™๐šŠ๐šŒ๐š’๐š๐šข-3

where the domains of o 1 , o 2 and o 3 are respectively equal to {1,2,3}, {1,2,3} and {1,2,3,4} corresponds to the following conjunction of ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraints

๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ๐š˜๐š›๐š’๐š๐š’๐š—-o 1 ๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐š‘๐šŽ๐š’๐š๐š‘๐š-2,๐š˜๐š›๐š’๐š๐š’๐š—-o 2 ๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐š‘๐šŽ๐š’๐š๐š‘๐š-1,2
๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ๐š˜๐š›๐š’๐š๐š’๐š—-o 1 ๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐š‘๐šŽ๐š’๐š๐š‘๐š-2,๐š˜๐š›๐š’๐š๐š’๐š—-o 2 ๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š˜๐š›๐š’๐š๐š’๐š—-o 3 ๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-1๐š‘๐šŽ๐š’๐š๐š‘๐š-3,3

Even if the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint could achieve arc-consistency, the previous conjunction of ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraints would not detect the fact that there is no solution.

See also

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

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

Keywords

characteristic of a constraint: derived collection.

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

modelling: zero-duration task.

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.86.2 shows the initial graphs associated with priorities 1 and 2 of the Example slot. Partย (B) of Figureย 5.86.2 shows the corresponding final graphs associated with priorities 1 and 2. On the one hand, each source vertex of the final graph can be interpreted as a time point p. On the other hand the successors of a source vertex correspond to those tasks that both overlap that time point p and have a priority less than or equal to a given level. The ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐š ๐š’๐š๐š‘_๐š•๐šŽ๐šŸ๐šŽ๐š•_๐š˜๐š_๐š™๐š›๐š’๐š˜๐š›๐š’๐š๐šข constraint holds since for each successor set ๐’ฎ of the final graph the sum of the height of the tasks in ๐’ฎ is less than or equal to the capacity associated with a given level of priority.

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