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.

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 in MiniZinc. If all durations are 1, then it corresponds to bin_packing 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, denoting:

Oi-Oj = Dij

global(Boolean)

if true, then 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.

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.

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), then 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, then 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), then each resource limit is treated as a lower bound. If upper, then each resource limit is treated as an upper bound.

prune(P)

If all (the default), then the constraint will try to prune as many variables as possible. If next, then 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, then extra reasoning based on assumptions on machine assignment will be done to infer more.

task_intervals(Boolean)

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

The following constraint is a generalization of cumulative/[1,2] in the following sense:

• The new constraint deals with the consumption of multiple resources simultaneously, not just a single resource. For the constraint to succeed, none of the resources can exceed its limit.
• Resources can be of two kinds:

  cumulative

  This is the kind of resource that cumulative/[1,2] deals with: at no point in time can the total resource use exceed the limit.

  colored

  For this kind of resource, each task specifies not a resource use, but a color, encoded as an integer. At no point in time can the total number of distinct colors in use exceed the limit. The color code 0 is treated specially: it denotes that the task does not have any color.

On the other hand, the new constraint has the limitation that all fields and parameters except start and end times must be given as integers:

multi_cumulative(+Tasks,+Capacities)   since release 4.3.1

multi_cumulative(+Tasks,+Capacities,+Options)   since release 4.3.1

A task is represented by a term task(Oi,Di,Ei,Hsi,Ti) where Oi is the start time, Di the non-negative duration, Ei the end time, Hsi the list of non-negative resource uses or colors, and Ti the task identifier. The start and end times should be domain variables with bounded domains. The other fields should be integers.

The capacities should be a list of terms of the following form, where Limit should be a non-negative integer. Capacities and all the Hsi should be of the same length:

cumulative(Limit)

denotes a cumulative resource.

colored(Limit)

denotes a colored resource.

Options is a list of zero or more of the following:

greedy(Flag)

If given, then Flag is a domain variable in 0..1. If Flag equals 1, either initially or by binding Flag during search, then the constraint switches behavior into greedy assignment mode. The greedy assignment will either succeed and assign all start and end times to values that satisfy the constraint, or merely fail. Flag is never bound by the constraint; its sole function is to control the behavior of the constraint.

precedences(Ps)

Ps encodes a set of precedence constraints to apply to the tasks. Ps should be a list of pairs Ti-Tj where Ti and Tj should be task identifiers, denoting that task Ti must complete before task Tj can start.

This constraint is due to [Letort, Beldiceanu & Carlsson 14].