5.126. disjunctive

DESCRIPTIONLINKSGRAPH
Origin

[Carlier82]

Constraint

πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ(πšƒπ™°πš‚π™Ίπš‚)

Synonym

πš˜πš—πšŽ_πš–πšŠπšŒπš‘πš’πš—πšŽ.

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

All the tasks of the collection πšƒπ™°πš‚π™Ίπš‚ that have a duration strictly greater than 0 should not overlap.

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

FigureΒ 5.126.1 shows the tasks with non-zero duration of the example. Since these tasks do not overlap the πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ constraint holds.

Figure 5.126.1. Tasks with non-zero duration of the Example slot
ctrs/disjunctive-1-tikz
All solutions

FigureΒ 5.126.2 gives all solutions to the following non ground instance of the πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ constraint: O 1 ∈[2,5], D 1 ∈[2,4], O 2 ∈[2,4], D 2 ∈[1,6], O 3 ∈[3,6], D 3 ∈[4,4], O 4 ∈[2,7], D 4 ∈[1,3], πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ(〈O 1 D 1 , O 2 D 2 , O 3 D 3 , O 4 D 4 βŒͺ).

Figure 5.126.2. All solutions corresponding to the non ground example of the πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ constraint of the All solutions slot
ctrs/disjunctive-2-tikz
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. πšƒπ™°πš‚π™Ίπš‚.

Usage

The πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ constraint occurs in many resource scheduling problems in order to model a resource that can not be shared. This means that tasks using this resource can not overlap in time. Quite often πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ constraints are used together with precedence constraints. A precedence constraint between two tasks models the fact that the processing of a task has to be postponed until an other task is completed. Such mix of disjunctive and precedence constraints occurs for instance in job-shop problems.

Remark

Some systems like IlogΒ CPΒ Optimizer also imposes that zero duration tasks do not overlap non-zero duration tasks.

A soft version of this constraint, under the hypothesis that all durations are fixed, was presented by P.Β Baptiste et al. inΒ [BaptisteLePapePeridy98]. In this context the goal was to perform as many tasks as possible within their respective due-dates.

When all tasks have the same (fixed) duration the πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ constraint can be reformulated as an πšŠπš•πš•_πš–πš’πš—_πšπš’πšœπš constraint for which a filtering algorithm achieving bound-consistency is availableΒ [ArtiouchineBaptiste05].

Within the context of linear programmingΒ [Hooker07book] provides several relaxations of the πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ constraint.

Some solvers use in a pre-processing phase, while stating precedence and cumulative constraints, an algorithm for automatically extracting large cliquesΒ [BronKerbosch73] from a set of tasks that should not pairwise overlap (i.e., two tasks t i and t j can not overlap either, because t i ends before the start of t j , either because the sum of resource consumption of t i and t j exceeds the capacity of a cumulative resource that both tasks use) in order to state πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ constraints.

Algorithm

We have four main families of methods for handling the πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ constraint:

  • Methods based on the compulsory partΒ [Lahrichi82] of the tasks (also called time-tabling methods). These methods determine the time slots which for sure are occupied by a given task, an propagate back this information to the attributes of each task (i.e., the origin and the duration). Because of their simplicity, these methods have been originally used for handling the πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ constraint. Even if they propagate less than the other methods they can in practice handle a large number of tasks. To our best knowledge no efficient incremental algorithm devoted to this problem was published up to now (i.e., SeptemberΒ 2006).

  • Methods based on constructive disjunction. The idea is to try out each alternative of a disjunction (e.g.,Β given two tasks t 1 and t 2 that should not overlap, we successively assume that t 1 finishes before t 2 , and that t 2 finishes before t 1 ) and to remove values that were pruned in both alternatives.

  • Methods based on edge-finding. Given a set of tasks 𝒯, edge-finding determines that some task must, can, or cannot execute first or last in 𝒯. Efficient edge-finding algorithms for handling the πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ constraint were originally described inΒ [CarlierPinson88], [CarlierPinson90] and more recently inΒ [Vilim04], [PeridyRivreau05].

  • Methods that, for any task t, consider the maximal number of tasks that can end up before the start of task t as well as the maximal number of tasks that can start after the end of task tΒ [Wolf05].

All these methods are usually used for adjusting the minimum and maximum values of the variables of the πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ constraint. However some systems use these methods for pruning the full domain of the variables. Finally, Jackson priority ruleΒ [Jackson55] provides a necessary conditionΒ [CarlierPinson90] for the πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ constraint. Given a set of tasks 𝒯, it consists to progressively schedule all tasks of 𝒯 in the following way:

  • It assigns to the first possible time point (i.e., the earliest start of all tasks of 𝒯) the available task with minimal latest end. In this context, available means a task for which the earliest start is less than or equal to the considered time point.

  • It continues by considering the next time point until all the tasks are completely scheduled.

Systems

disjunctive in Choco, unary in Gecode.

See also

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

generalisation: πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽΒ (πšπšŠπšœπš” πš‘πšŽπš’πšπš‘πšπšœ and πš›πšŽπšœπš˜πšžπš›πšŒπšŽ πš•πš’πš–πš’πš are not necessarly all equal to 1), πšπš’πšπšπš—Β (πšπšŠπšœπš” of πš‘πšŽπš’πšπšπš‘ 1 replaced by orthotope).

implied by: πš™πš›πšŽπšŒπšŽπšπšŽπš—πšŒπšŽ.

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

specialisation: πšŠπš•πš•_πš–πš’πš—_πšπš’πšœπšΒ (πš•πš’πš—πšŽ πšœπšŽπšπš–πšŽπš—πš replaced by πš•πš’πš—πšŽ πšœπšŽπšπš–πšŽπš—πš, of same length), πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (πšπšŠπšœπš” replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ).

Keywords

characteristic of a constraint: core, sort based reformulation.

complexity: sequencing with release times and deadlines.

constraint type: scheduling constraint, resource constraint, decomposition.

filtering: compulsory part, constructive disjunction, Phi-tree.

modelling: disjunction, sequence dependent set-up, zero-duration task.

modelling exercises: sequence dependent set-up.

problems: maximum clique.

Cond. implications

β€’ πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ(πšƒπ™°πš‚π™Ίπš‚)

Β Β Β  withΒ  πš–πš’πš—πšŸπšŠπš•(πšƒπ™°πš‚π™Ίπš‚.πšπšžπš›πšŠπšπš’πš˜πš—)>0

Β Β implies πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(πšƒπ™°πš‚π™Ίπš‚.πš˜πš›πš’πšπš’πš—).

β€’ πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ(πšƒπ™°πš‚π™Ίπš‚)

Β Β Β  withΒ  πš–πš’πš—πšŸπšŠπš•(πšƒπ™°πš‚π™Ίπš‚.πšπšžπš›πšŠπšπš’πš˜πš—)>0

Β Β implies πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_𝚌𝚜𝚝(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚:πšƒπ™°πš‚π™Ίπš‚).

Arc input(s)

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

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

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

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.

PartsΒ (A) andΒ (B) of FigureΒ 5.126.3 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.126.3. Initial and final graph of the πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ constraint
ctrs/disjunctiveActrs/disjunctiveB
(a) (b)
Quiz

Β Β 

πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽ: checking whether a ground instance holds or not ctrs/disjunctive-3-tikz

ctrs/disjunctive-4-tikz