5.304. soft_cumulative

DESCRIPTIONLINKS
Origin

Derived from πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ

Constraint

𝚜𝚘𝚏𝚝_πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ(πšƒπ™°πš‚π™Ίπš‚,π™»π™Έπ™Όπ™Έπšƒ,π™Έπ™½πšƒπ™΄πšπ™Όπ™΄π™³π™Έπ™°πšƒπ™΄_π™»π™΄πš…π™΄π™»,πš‚πš„πšπ™΅π™°π™²π™΄_𝙾𝙽_πšƒπ™Ύπ™Ώ)

Arguments
πšƒπ™°πš‚π™Ίπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—πš˜πš›πš’πšπš’πš—-πšπšŸπšŠπš›,πšπšžπš›πšŠπšπš’πš˜πš—-πšπšŸπšŠπš›,πšŽπš—πš-πšπšŸπšŠπš›,πš‘πšŽπš’πšπš‘πš-πšπšŸπšŠπš›
π™»π™Έπ™Όπ™Έπšƒπš’πš—πš
π™Έπ™½πšƒπ™΄πšπ™Όπ™΄π™³π™Έπ™°πšƒπ™΄_π™»π™΄πš…π™΄π™»πš’πš—πš
πš‚πš„πšπ™΅π™°π™²π™΄_𝙾𝙽_πšƒπ™Ύπ™Ώπš’πš—πš
Restrictions
πš›πšŽπššπšžπš’πš›πšŽ_𝚊𝚝_πš•πšŽπšŠπšœπš(2,πšƒπ™°πš‚π™Ίπš‚,[πš˜πš›πš’πšπš’πš—,πšπšžπš›πšŠπšπš’πš˜πš—,πšŽπš—πš])
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπ™°πš‚π™Ίπš‚,πš‘πšŽπš’πšπš‘πš)
πšƒπ™°πš‚π™Ίπš‚.πšπšžπš›πšŠπšπš’πš˜πš—β‰₯0
πšƒπ™°πš‚π™Ίπš‚.πš˜πš›πš’πšπš’πš—β‰€πšƒπ™°πš‚π™Ίπš‚.πšŽπš—πš
πšƒπ™°πš‚π™Ίπš‚.πš‘πšŽπš’πšπš‘πšβ‰₯0
π™»π™Έπ™Όπ™Έπšƒβ‰₯0
π™Έπ™½πšƒπ™΄πšπ™Όπ™΄π™³π™Έπ™°πšƒπ™΄_π™»π™΄πš…π™΄π™»β‰₯0
π™Έπ™½πšƒπ™΄πšπ™Όπ™΄π™³π™Έπ™°πšƒπ™΄_π™»π™΄πš…π™΄π™»β‰€π™»π™Έπ™Όπ™Έπšƒ
πš‚πš„πšπ™΅π™°π™²π™΄_𝙾𝙽_πšƒπ™Ύπ™Ώβ‰₯0
Purpose

Consider a set 𝒯 of n tasks described by the πšƒπ™°πš‚π™Ίπš‚ collection, where πš˜πš›πš’πšπš’πš— j , πšπšžπš›πšŠπšπš’πš˜πš— j , πšŽπš—πš j , πš‘πšŽπš’πšπš‘πš j are shortcuts for πšƒπ™°πš‚π™Ίπš‚[j].πš˜πš›πš’πšπš’πš—, πšƒπ™°πš‚π™Ίπš‚[j].πšπšžπš›πšŠπšπš’πš˜πš—, πšƒπ™°πš‚π™Ίπš‚[j].πšŽπš—πš, πšƒπ™°πš‚π™Ίπš‚[j].πš‘πšŽπš’πšπš‘πš. In addition let Ξ± and Ξ² respectively denote the earliest possible start over all tasks and the latest possible end over all tasks. The 𝚜𝚘𝚏𝚝_πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraint enforces the three following conditions:

  1. For each task πšƒπ™°πš‚π™Ίπš‚[j] (1≀j≀n) of 𝒯 we have πš˜πš›πš’πšπš’πš— j +πšπšžπš›πšŠπšπš’πš˜πš— j =πšŽπš—πš j .

  2. At each point in time, the cumulated height of the set of tasks that overlap that point, does not exceed a given limit π™»π™Έπ™Όπ™Έπšƒ (i.e.,Β βˆ€i∈[Ξ±,Ξ²]:βˆ‘ j∈[1,n]|πš˜πš›πš’πšπš’πš— j ≀i<πšŽπš—πš j πš‘πšŽπš’πšπš‘πš j β‰€π™»π™Έπ™Όπ™Έπšƒ).

  3. The surface of the profile resource utilisation, which is greater than π™Έπ™½πšƒπ™΄πšπ™Όπ™΄π™³π™Έπ™°πšƒπ™΄_π™»π™΄πš…π™΄π™», is equal to πš‚πš„πšπ™΅π™°π™²π™΄_𝙾𝙽_πšƒπ™Ύπ™Ώ (i.e., βˆ‘ i∈[Ξ±,Ξ²] max(0,(βˆ‘ j∈[1,n]|πš˜πš›πš’πšπš’πš— j ≀i<πšŽπš—πš j πš‘πšŽπš’πšπš‘πš j )-π™Έπ™½πšƒπ™΄πšπ™Όπ™΄π™³π™Έπ™°πšƒπ™΄_π™»π™΄πš…π™΄π™») = πš‚πš„πšπ™΅π™°π™²π™΄_𝙾𝙽_πšƒπ™Ύπ™Ώ).

Example
πš˜πš›πš’πšπš’πš—-1πšπšžπš›πšŠπšπš’πš˜πš—-4πšŽπš—πš-5πš‘πšŽπš’πšπš‘πš-1,πš˜πš›πš’πšπš’πš—-1πšπšžπš›πšŠπšπš’πš˜πš—-1πšŽπš—πš-3πš‘πšŽπš’πšπš‘πš-2,πš˜πš›πš’πšπš’πš—-3πšπšžπš›πšŠπšπš’πš˜πš—-3πšŽπš—πš-6πš‘πšŽπš’πšπš‘πš-2,3,2,3

FigureΒ 5.304.1 shows the cumulated profile associated with the example. To each task of the πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraint 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:

  1. For each task we have that its end is equal to the sum of its origin and its duration.

  2. At each point in time we do not have a cumulated resource consumption strictly greater than the upper limit π™»π™Έπ™Όπ™Έπšƒ=3 enforced by the second argument of the 𝚜𝚘𝚏𝚝_πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraint.

  3. The surface of the cumulated profile located on top of the intermediate level π™Έπ™½πšƒπ™΄πšπ™Όπ™΄π™³π™Έπ™°πšƒπ™΄_π™»π™΄πš…π™΄π™»=2 is equal to πš‚πš„πšπ™΅π™°π™²π™΄_𝙾𝙽_πšƒπ™Ύπ™Ώ=3.

Figure 5.304.1. Resource consumption profile associated with the 3 tasks of the example, where parts on top of the intermediate level 2 are marked by a cross
ctrs/soft_cumulative1
Symmetries
  • Items of πšƒπ™°πš‚π™Ίπš‚ are permutable.

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

  • π™»π™Έπ™Όπ™Έπšƒ can be increased.

Remark

The 𝚜𝚘𝚏𝚝_πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraint was initially introduced in CHIPΒ [Cosytec97] as a variant of the πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraint. An extension of this constraint where one can restrict the surface on top of the intermediate level on different time intervals was proposed inΒ [PetitPoder09].

See also

hard version: πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ.

Keywords

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