5.105. disjunctive

Origin

[Carlier82]

Constraint

disjunctive​(TASKS)​

Synonym(s)

one_machine.

Argument(s)

TASKS

collection​(origin−dvar,​duration−dvar)​

Restriction(s)

required​(TASKS,​​[origin,​duration]​)​

TASKS.duration≥0

Purpose

All the tasks of the collection TASKS that have a duration strictly greater than 0 should not overlap.

Example

( 〈 origin−1 duration−3,​ origin−2 duration−0,​ origin−7 duration−2,​ origin−4 duration−1 〉 )

Figure 5.105.1 shows the tasks with non -zero duration of the example. Since these tasks do not overlap the disjunctive constraint holds.

Figure 5.105.1. Tasks with non-zero duration

Remark

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 disjunctive constraint can be reformulated as an all_min_dist constraint for which a filtering algorithm achieving bound-consistency is available [ArtiouchineBaptiste05].

Within the context of linear programming [Hooker07book] provides several relaxations of the disjunctive 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 disjunctive constraints.

Algorithm

We have four main families of methods for handling the disjunctive 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 disjunctive 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₁ and t₂ that should not overlap, we successively assume that t₁ finishes before t₂, and that t₂ finishes before t₁) and to remove values that were pruned in both alternatives.

• Methods based on edge -finding. Given a set of tasks T, edge -finding determines that some task must, can, or cannot execute first or last in T. Efficient edge -finding algorithms for handling the disjunctive 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 disjunctive 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 disjunctive constraint. Given a set of tasks T, it consists to progressively schedule all tasks of T in the following way:

• It assigns to the first possible time point (i.e., the earliest start of all tasks of T) 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.

See also

disj, all_min_dist, cumulative, diffn, calendar.

Key words

characteristic of a constraint: core.

complexity: sequencing with release times and deadlines.

constraint type: scheduling constraint, resource constraint, decomposition.

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

modelling: disjunction.

problems: maximum clique.

Arc input(s)

TASKS

Arc generator

CLIQUE​(​<)​↦collection​(tasks1,​tasks2)​

Arc arity

2

Arc constraint(s)

⋁( tasks1.duration=0,​ tasks2.duration=0,​ tasks1.origin+tasks1.duration≤tasks2.origin,​ tasks2.origin+tasks2.duration≤tasks1.origin )

Graph property(ies)

NARC=|TASKS|*​(|TASKS|−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.105.2 respectively show the initial and final graph associated with the Example slot. The disjunctive constraint holds since all the arcs of the initial graph belong to the final graph: all the non -overlapping constraints holds.

Figure 5.105.2. Initial and final graph of the disjunctive constraint

(a)	(b)