[ library(gfd) | Reference Manual | Alphabetic Index ]

disjunctive(+StartTimes, +Durations)

Constrain the tasks with specified start times and durations to not overlap in time.
Collection of N start times for tasks (domain variables or integers)
Collection of N durations for tasks (non-negative domain variables or integers)


A disjunctive scheduling constraint. StartTimes and Durations are collections (a la collection_to_list/2) of equal size N of integer variables or integers. Durations must be non-negative.

The declarative meaning is that the N tasks with the given start times and durations do not overlap at any point in time, i.e. for any pairs of tasks X and Y, the following holds:

        (Xstart + Xduration =< Ystart) or (Ystart + Yduration =< Xstart)

Note that the constraint is implemented by different Gecode propagators, depending on if Durations contains domain variables or not. If Durations does have domain variables, the Gecode propagator requires an extra End domain variable specifying the end time, and a constraint

      End #= Start + Duration  
for each task. These are posted as part of the constraint (the End variables are not accessible by the user).

Any input variables which are not already domain variables will be converted into domain variables with default bounds.

This constraint is also known as disjunctive in the global constraint catalog, but in the catalog, tasks with zero duration are allowed to overlap with other tasks. The constraint is implemented using Gecode's unary constraint (with extra constraints on task end times if any task duration is a domain variable).


[eclipse 2]: disjunctive([1,7,4],[3,2,1]).    % succeed

[eclipse 3]: disjunctive([1,7,3], [3,2,1]).   % fail

[eclipse 4]: disjunctive([1,4,7,4],[3,0,2,1]). % succeed 

[eclipse 5]: disjunctive([1,2,7,4],[3,0,2,1]). % fail 

[eclipse 5]: [S2,S4]::[1..9], disjunctive([1,S2,7,S4], [3,1,2,1]).

S2 = S2{[4 .. 9]}
S4 = S4{[4 .. 9]}

See Also

ic_edge_finder : disjunctive / 2, ic_edge_finder3 : disjunctive / 2, edge_finder : disjunctive / 2, edge_finder3 : disjunctive / 2, disjunctive_optional / 3, cumulative / 4, cumulatives / 5, eclipse_6 : collection_to_list / 2, lists : collection_to_list / 2