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

disjunctive_bools(+StartTimes, +Durations, ?OrderingBools)

Constrain the tasks with specified start times and durations to not overlap in time.
StartTimes
Collection of start times for tasks (integer variables or integers)
Durations
Collection of duration for tasks (integer variables or integers)
OrderingBools
Variable, or list of ordering Booleans (variable or 0 or 1)

Description

A disjunctive scheduling constraint. StartTimes and Durations are collections (a la collection_to_list/2) of equal size N of integer variables or integers. The declarative meaning is that the N tasks with the given start times and durations do not overlap at any point in time.

OrderingBools is a list of ordering Booleans. For each possible pair of tasks, there is one Boolean which describes the order of these two tasks. If the Tasks are numbered 1..N, and the Booleans are numbered 1..N*(N-1)//2, then the Boolean corresponding to the task pair I,J (with I>J) has the index (I-1)(I-2)//2 + J. In other words, the OrderingBools list is a flattened version of a strictly lower triangular matrix of ordering Booleans, i.e.

        I\J|  1    2    3    4    5
        ---+--------------------------
        1  |  .    .    .    .    .
        2  | B[1]  .    .    .    .
        3  | B[2] B[3]  .    .    .
        4  | B[4] B[5] B[6]  .    .
        5  | B[7] B[8] B[9] B[10] .
    
The Boolean being set to 1 indicates that task I is before task J, a value of 0 indicates that task J is before task I. If uninstantiated, the order is not (yet) determined. Operationally, the constraint will both infer start time bounds from the setting of the Booleans, and infer Boolean settings from the start times and durations.

The Booleans should be used for making search choices, typically by setting them such that a task is chosen to be first (or last) among a group of tasks.

Any Start and Duration variables which do not already have finite bounds will be given default bounds of -10000000 to 10000000. The Booleans on the other hand can be domainless variables, and the only way in which the constraint will affect them is by instantiation to 0 or 1.

Modes and Determinism

See Also

disjunctive / 2, lists : collection_to_list / 2, edge_finder3 : disjunctive_bools / 3, edge_finder : disjunctive_bools / 3, ic_edge_finder3 : disjunctive_bools / 3