10.10.4.7 Scheduling Constraints

The following constraint can be thought of as constraining n tasks so that the total resource consumption does not exceed a given limit at any time. API change wrt. release 3:

cumulative(+Tasks)

cumulative(+Tasks,+Options)

A task is represented by a term task(Oi,Di,Ei,Hi,Ti) where Oi is the start time, Di the non-negative duration, Ei the end time, Hi the non-negative resource consumption, and Ti the task identifier. All fields are domain variables with bounded domains, or integers.

Let n be the number of tasks and L the global resource limit (by default 1, but see below), and:

          Hij = Hi, if Oi <= j < Oi+Di
          Hij = 0 otherwise

The constraint holds if:

1. For every task i, Oi+Di=Ei, and
2. For all instants j, H1j+...+Hnj <= L.

Corresponds to cumulative/4 in MiniZinc. If all durations are 1, corresponds to bin_packing/3 in MiniZinc.

Options is a list of zero or more of the following, where Boolean must be true or false (false is the default).

limit(L)

See above.

precedences(Ps)

Ps encodes a set of precedence constraints to apply to the tasks. Ps should be a list of terms of the form:

               Ti-Tj #= Dij

where Ti and Tj should be task identifiers, and Dij should be a a domain variable (or an integer), denoting:

               Oi-Oj = Dij and Dij in r

global(Boolean)

if true, a more expensive algorithm will be used in order to achieve tighter pruning of the bounds of the parameters.

This constraint is due to Aggoun and Beldiceanu [Aggoun & Beldiceanu 93].

The following constraint can be thought of as constraining n tasks to be placed in time and on m machines. Each machine has a resource limit, which is interpreted as a lower or upper bound on the total amount of resource used on that machine at any point in time that intersects with some task.

cumulatives(+Tasks,+Machines)

cumulatives(+Tasks,+Machines,+Options)

A task is represented by a term task(Oi,Di,Ei,Hi,Mi) where Oi is the start time, Di the non-negative duration, Ei the end time, Hi the resource consumption (if positive) or production (if negative), and Mi a machine identifier. All fields are domain variables with bounded domains, or integers.

A machine is represented by a term machine(Mj,Lj) where Mj is the identifier, an integer; and Lj is the resource bound of the machine, which must be a domain variable with bounded domains or an integer.

Let there be n tasks and:

          Hijm = Hi, if Mi=m and Oi <= j < Oi+Di
          Hijm = 0 otherwise

If the resource bound is lower (the default), the constraint holds if:

1. For every task i, Si+Di=Ei, and
2. For all machines m and instants j such that there exists a task i where Mi=m and Oi <= j < Oi+Di, H1jm+...+Hnjm >= Lm.

If the resource bound is upper, the constraint holds if:

1. For every task i, Si+Di=Ei, and
2. For all machines m and instants j, H1jm+...+Hnjm <= Lm.

Options is a list of zero or more of the following, where Boolean must be true or false (false is the default):

bound(B)

If lower (the default), each resource limit is treated as a lower bound. If upper, each resource limit is treated as an upper bound.

prune(P)

If all (the default), the constraint will try to prune as many variables as possible. If next, only variables that occur in the first nonground task term (wrt. the order given when the constraint was posted) can be pruned.

generalization(Boolean)

If true, extra reasoning based on assumptions on machine assignment will be done to infer more.

task_intervals(Boolean)

If true, extra global reasoning will be performed in an attempt to infer more.