5.128. disjunctive_or_same_start

DESCRIPTIONLINKSGRAPH
Origin

Scheduling.

Constraint

πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ_πš˜πš›_πšœπšŠπš–πšŽ_πšœπšπšŠπš›πš(πšƒπ™°πš‚π™Ίπš‚)

Synonyms

πšœπšŠπš–πšŽ_πšœπšπšŠπš›πš_πš˜πš›_πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ, πš—πš˜πš—_πš˜πšŸπšŽπš›πš•πšŠπš™_πš˜πš›_πšœπšŠπš–πšŽ_πšœπšπšŠπš›πš, πšœπšŠπš–πšŽ_πšœπšπšŠπš›πš_πš˜πš›_πš—πš˜πš—_πš˜πšŸπšŽπš›πš•πšŠπš™.

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

All pairs of tasks of the collection πšƒπ™°πš‚π™Ίπš‚ that have a duration strictly greater than 0 should either not overlap either have the same start, i.e.Β βˆ€i∈[1,|πšƒπ™°πš‚π™Ίπš‚|],βˆ€j∈[i+1,|πšƒπ™°πš‚π™Ίπš‚|]: πšƒπ™°πš‚π™Ίπš‚[i].πšπšžπš›πšŠπšπš’πš˜πš—=0βˆ¨πšƒπ™°πš‚π™Ίπš‚[j].πšπšžπš›πšŠπšπš’πš˜πš—=0βˆ¨πšƒπ™°πš‚π™Ίπš‚[i].πš˜πš›πš’πšπš’πš—+πšƒπ™°πš‚π™Ίπš‚[i].πšπšžπš›πšŠπšπš’πš˜πš—β‰€πšƒπ™°πš‚π™Ίπš‚[j].πš˜πš›πš’πšπš’πš—βˆ¨πšƒπ™°πš‚π™Ίπš‚[j].πš˜πš›πš’πšπš’πš—+πšƒπ™°πš‚π™Ίπš‚[j].πšπšžπš›πšŠπšπš’πš˜πš—β‰€πšƒπ™°πš‚π™Ίπš‚[i].πš˜πš›πš’πšπš’πš—βˆ¨πšƒπ™°πš‚π™Ίπš‚[i].πš˜πš›πš’πšπš’πš—=πšƒπ™°πš‚π™Ίπš‚[j].πš˜πš›πš’πšπš’πš—.

Example
πš˜πš›πš’πšπš’πš—-4πšπšžπš›πšŠπšπš’πš˜πš—-3,πš˜πš›πš’πšπš’πš—-7πšπšžπš›πšŠπšπš’πš˜πš—-2,πš˜πš›πš’πšπš’πš—-4πšπšžπš›πšŠπšπš’πš˜πš—-1

Since the starts of the first and third tasks coincide, and since the second task does neither overlap the first task nor the third task, the πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ_πš˜πš›_πšœπšŠπš–πšŽ_πšœπšπšŠπš›πš constraint holds.

Typical
|πšƒπ™°πš‚π™Ίπš‚|>2
πšƒπ™°πš‚π™Ίπš‚.πšπšžπš›πšŠπšπš’πš˜πš—β‰₯1
Symmetries
  • Items of πšƒπ™°πš‚π™Ίπš‚ are permutable.

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

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

Arg. properties

Contractible wrt. πšƒπ™°πš‚π™Ίπš‚.

See also

common keyword: πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ, πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ_πš˜πš›_πšœπšŠπš–πšŽ_πšŽπš—πšΒ (scheduling constraint).

implied by: πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ.

Keywords

constraint type: scheduling constraint, resource constraint, decomposition.

modelling: disjunction, zero-duration task.

Arc input(s)

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

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

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

Graph model

We generate a clique with a non-overlapping constraint or a same start 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.

PartsΒ (A) andΒ (B) of FigureΒ 5.128.1 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.

Figure 5.128.1. Initial and final graph of the πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ_πš˜πš›_πšœπšŠπš–πšŽ_πšœπšπšŠπš›πš constraint
ctrs/disjunctive_or_same_startActrs/disjunctive_or_same_startB
(a) (b)