5.104. disj

DESCRIPTIONLINKSGRAPH
Origin

[MonetteDevilleDupont07]

Constraint

πšπš’πšœπš“(πšƒπ™°πš‚π™Ίπš‚)

Argument
πšƒπ™°πš‚π™Ίπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—πšœπšπšŠπš›πš-πšπšŸπšŠπš›,πšπšžπš›πšŠπšπš’πš˜πš—-πšπšŸπšŠπš›,πš‹πšŽπšπš˜πš›πšŽ-πšœπšŸπšŠπš›,πš™πš˜πšœπš’πšπš’πš˜πš—-πšπšŸπšŠπš›
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπ™°πš‚π™Ίπš‚,[πšœπšπšŠπš›πš,πšπšžπš›πšŠπšπš’πš˜πš—,πš‹πšŽπšπš˜πš›πšŽ,πš™πš˜πšœπš’πšπš’πš˜πš—])
πšƒπ™°πš‚π™Ίπš‚.πšπšžπš›πšŠπšπš’πš˜πš—β‰₯1
πšƒπ™°πš‚π™Ίπš‚.πš™πš˜πšœπš’πšπš’πš˜πš—β‰₯0
πšƒπ™°πš‚π™Ίπš‚.πš™πš˜πšœπš’πšπš’πš˜πš—<|πšƒπ™°πš‚π™Ίπš‚|
Purpose

All the tasks of the collection πšƒπ™°πš‚π™Ίπš‚ should not overlap. For a given task t the attributes πš‹πšŽπšπš˜πš›πšŽ and πš™πš˜πšœπš’πšπš’πš˜πš— respectively correspond to the set of tasks starting before task t (assuming that the first task is labelled by 1) and to the position of task t (assuming that the first task has position 0).

Example
πšœπšπšŠπš›πš-1πšπšžπš›πšŠπšπš’πš˜πš—-3πš‹πšŽπšπš˜πš›πšŽ-βˆ…πš™πš˜πšœπš’πšπš’πš˜πš—-0,πšœπšπšŠπš›πš-9πšπšžπš›πšŠπšπš’πš˜πš—-1πš‹πšŽπšπš˜πš›πšŽ-{1,3,4}πš™πš˜πšœπš’πšπš’πš˜πš—-3,πšœπšπšŠπš›πš-7πšπšžπš›πšŠπšπš’πš˜πš—-2πš‹πšŽπšπš˜πš›πšŽ-{1,4}πš™πš˜πšœπš’πšπš’πš˜πš—-2,πšœπšπšŠπš›πš-4πšπšžπš›πšŠπšπš’πš˜πš—-1πš‹πšŽπšπš˜πš›πšŽ-{1}πš™πš˜πšœπš’πšπš’πš˜πš—-1

FigureΒ 5.104.1 shows the tasks of the example. Since these tasks do not overlap the πšπš’πšœπš“ constraint holds.

Figure 5.104.1. Tasks
ctrs/disj1
Typical
|πšƒπ™°πš‚π™Ίπš‚|>1
Symmetries
  • One and the same constant can be added to the πšœπšπšŠπš›πš attribute of all items of πšƒπ™°πš‚π™Ίπš‚.

  • πšƒπ™°πš‚π™Ίπš‚.πšπšžπš›πšŠπšπš’πš˜πš— can be decreased to any value β‰₯1.

Usage

The πšπš’πšœπš“ constraint was originally appliedΒ [MonetteDevilleDupont07] to solve the open -shop problem.

Remark

This constraint is similar to the πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ constraint. In addition to the πšœπšπšŠπš›πš and the πšπšžπš›πšŠπšπš’πš˜πš— attributes of a task t, the πšπš’πšœπš“ constraint introduces a set variable πš‹πšŽπšπš˜πš›πšŽ that represents the set of tasks that end before the start of task t as well as a domain variable πš™πš˜πšœπš’πšπš’πš˜πš— that gives the absolute order of task t in the resource. Since it assumes that the first task has position 0 we have that, for a given task t, the number of elements of its πš‹πšŽπšπš˜πš›πšŽ attribute is equal to the value of its πš™πš˜πšœπš’πšπš’πš˜πš— attribute.

Algorithm

The main idea of the algorithm is to apply in a systematic way shaving on the πš™πš˜πšœπš’πšπš’πš˜πš— attribute of a task. It is implemented in GecodeΒ [Gecode06].

See also

common keyword: πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽΒ (scheduling constraint).

used in graph description: πš’πš—_𝚜𝚎𝚝.

Keywords

complexity: sequencing with release times and deadlines.

constraint type: scheduling constraint, resource constraint, decomposition.

Arc input(s)

πšƒπ™°πš‚π™Ίπš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈ(β‰ )β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπšŠπšœπš”πšœ1,πšπšŠπšœπš”πšœ2)

Arc arity
Arc constraint(s)
β€’ β‹πšπšŠπšœπš”πšœ1.πšœπšπšŠπš›πš+πšπšŠπšœπš”πšœ1.πšπšžπš›πšŠπšπš’πš˜πš—β‰€πšπšŠπšœπš”πšœ2.πšœπšπšŠπš›πš,πšπšŠπšœπš”πšœ2.πšœπšπšŠπš›πš+πšπšŠπšœπš”πšœ2.πšπšžπš›πšŠπšπš’πš˜πš—β‰€πšπšŠπšœπš”πšœ1.πšœπšπšŠπš›πš
β€’ πšπšŠπšœπš”πšœ1.πšœπšπšŠπš›πš+πšπšŠπšœπš”πšœ1.πšπšžπš›πšŠπšπš’πš˜πš—β‰€πšπšŠπšœπš”πšœ2.πšœπšπšŠπš›πšβ‡”πš’πš—_𝚜𝚎𝚝(πšπšŠπšœπš”πšœ1.πš”πšŽπš’,πšπšŠπšœπš”πšœ2.πš‹πšŽπšπš˜πš›πšŽ)
β€’ πšπšŠπšœπš”πšœ1.πšœπšπšŠπš›πš+πšπšŠπšœπš”πšœ1.πšπšžπš›πšŠπšπš’πš˜πš—β‰€πšπšŠπšœπš”πšœ2.πšœπšπšŠπš›πšβ‡”πšπšŠπšœπš”πšœ1.πš™πš˜πšœπš’πšπš’πš˜πš—<πšπšŠπšœπš”πšœ2.πš™πš˜πšœπš’πšπš’πš˜πš—
Graph property(ies)
𝐍𝐀𝐑𝐂=|πšƒπ™°πš‚π™Ίπš‚|*|πšƒπ™°πš‚π™Ίπš‚|-|πšƒπ™°πš‚π™Ίπš‚|

Graph model

We generate a clique with a non-overlapping constraint between each pair of distinct tasks and state that the number of arcs of the final graph should be equal to the number of arcs of the initial graph. For two tasks t 1 and t 2 , the three conditions of the arc constraint respectively correspond to:

  • The fact that t 1 ends before the start of t 2 or that t 2 ends before the start of t 1 .

  • The equivalence between the fact that t 1 ends before the start of t 2 and the fact that the identifier of task t 1 belongs to the πš‹πšŽπšπš˜πš›πšŽ attribute of task t 2 .

  • The equivalence between the fact that t 1 ends before the start of t 2 and the fact that the πš™πš˜πšœπš’πšπš’πš˜πš— attribute of task t 1 is strictly less than the πš™πš˜πšœπš’πšπš’πš˜πš— attribute of task t 2 .

PartsΒ (A) andΒ (B) of FigureΒ 5.104.2 respectively show the initial and final graph associated with the Example slot. The πšπš’πšœπš“ constraint holds since all the arcs of the initial graph belong to the final graph: all the non -overlapping constraints holds.

Figure 5.104.2. Initial and final graph of the πšπš’πšœπš“ constraint
ctrs/disjActrs/disjB
(a) (b)