Previous Up

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.


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.

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).

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.

Previous Up