4.3 Edge-finder
The libraries ic_edge_finder and ic_edge_finder3
implement stronger versions of the
disjunctive and cumulative scheduling constraints. They employ
a technique known as edge-finding to derive stronger bounds on
the starting times of the tasks.
The library is loaded using either
:- use_module(library(ic_edge_finder)).
to get a weaker variant with quadratic complexity, or
:- use_module(library(ic_edge_finder3)).
to get a stronger variant with cubic complexity.
-
disjunctive(+StartTimes,+Durations)
-
A disjunctive scheduling constraint. StartTimes and Durations
are lists of equal length N of integer variables or integers.
The declarative meaning is that the N tasks with certain start times
and duration do not overlap at any point in time. - cumulative(+StartTimes,+Durations,+Resources,++ResourceLimit)
-
A cumulative scheduling constraint. StartTimes, Durations and Resources
are lists of equal length N of integer variables or integers.
ResourceLimit is an integer. The declarative meaning is:
If there are N tasks, each starting at a certain start time, having
a certain duration and consuming a certain (constant) amount of
resource, then the sum of resource usage of all the tasks does not
exceed ResourceLimit at any time.
This constraint can propagate more information than the implementation
in library(cumulative). - cumulative(+StartTimes,+Durations,+Resources,+Area,++ResourceLimit)
-
In this variant, an area (the product of duration and resource usage of
a task) can be specified, e.g. if duration or resource usage are not
known in advance. The edge-finder algorithm can make use of this information
to derive bound updates.