Part 9: Cumulative Scheduling

We ask you not to publish your solutions on a public repository. The instructors interested to get the source-code of the solutions can contact us.

Slides

Theoretical questions

Cumulative Constraint: Decomposition

The Cumulative constraint models a scheduling resource with fixed capacity. It has the following signature:

public Cumulative(IntVar[] start, int[] duration, int[] demand, int capa)

where capa is the capacity of the resource and start, duration, and demand are arrays of the same size and represents properties of activities:

  • start[i] is the variable specifying the start time of activity i
  • duration[i] is the duration of activity i
  • demand[i] is the resource consumption or demand of activity i

The constraint ensures that the cumulative consumption of activities (also called consumption profile) at any time is below a given capacity:

\forall t: \sum_{i \mid t \in \left [start[i]..start[i]+duration[i]-1 \right ]} demand[i] \le capa

The next visual example depicts three activities and their corresponding consumption profile. As it can be observed, the profile never exceeds the capacity 4.

Cumulative(start = [ 1, 2, 3], duration = [8, 3, 3], demand = [1, 2, 2], capa = 4)

Implement CumulativeDecomp.java. This is a decomposition or reformulation of the cumulative constraint in terms of simple arithmetic and logical constraints as used in the above equation to describe its semantic.

At any time t of the horizon a BoolVar overlaps[i] tells whether activity i overlaps time t or not. Then the overall consumption in t is obtained by:

\sum_{i} overlaps[i]*demand[i] \le capa

First make sure you understand the following code, then add the few lines in the TODO to make sure overlaps has the intended meaning.

public void post() throws InconsistencyException {

    int min = Arrays.stream(start).map(s -> s.getMin()).min(Integer::compare).get();
    int max = Arrays.stream(end).map(e -> e.getMax()).max(Integer::compare).get();

    for (int t = min; t < max; t++) {

        BoolVar[] overlaps = new BoolVar[start.length];
        for (int i = 0; i < start.length; i++) {
            overlaps[i] = makeBoolVar(cp);

            // TODO
            // post the constraints to enforce
            // that overlaps[i] is true iff start[i] <= t && t < start[i] + duration[i]
            // hint: use IsLessOrEqual, introduce BoolVar, use views minus, plus, etc.
            //       logical constraints (such as logical and can be modeled with sum)

        }

        IntVar[] overlapHeights = makeIntVarArray(cp, start.length, i -> mul(overlaps[i], demand[i]));
        IntVar cumHeight = sum(overlapHeights);
        cumHeight.removeAbove(capa);

    }

Check that your implementation passes the tests CumulativeDecompTest.java.

Cumulative Constraint: Time-Table filtering

The Cumulative and Time-Table Filtering introduced in [TT2015] is an efficient yet simple filtering for Cumulative.

It is a two stage algorithm:

  1. Build an optimistic profile of the resource consumption and check it does not exceed the capacity.
  2. Filter the earliest start of the activities such that they are not in conflict with the profile.

Consider on the next example the depicted activity that can be executed anywhere between the two brackets. It can not execute at its earliest start since this would violate the capacity of the resource. We thus need to push the activity up until we find a time where it can execute over its entire duration without being in conflict with the profile and the capacity. The earliest time is 7.

scheduling timetable1

Profiles

We provide a class Profile.java that is able to build efficiently a resource profile given an array of rectangles in input. A rectangle has three attributes: start, end, height as shown next:

The profile consists in 7 contiguous rectangles. The first rectangle R0 starts at Integer.MIN_VALUE with a height of zero and the last rectangle R6 ends in Integer.MAX_VALUE also with a height of zero. These two dummy rectangles are convenient because they guarantee the property that any time point falls on one rectangle of the profile.

Profile.java.

Have a quick look at ProfileTest.java for some examples of profile construction.

Filtering

Implement Cumulative.java. You have three TODO tasks:

  1. Build the optimistic profile from the mandatory parts.
  2. Check that the profile is not exceeding the capacity.
  3. Filter the earliest start of activities.

TODO 1 is to build the optimistic profile from the mandatory parts of the activities. As can be seen on the next visual example, a mandatory part of an activity is a part that is always executed whatever will be the start time of the activity on its current domain. It is the rectangle starting at start[i].getMax() that ends in start[i].getMin()+duration() with a height equal to the demand of the activity. Be careful because not every activity has a mandatory part.

scheduling timetable1

TODO 2 is to check that the profile is not exceeding the capacity. You can check that each rectangle of the profile is not exceeding the capacity otherwise you throw an InconsitencyException.

TODO 3 is to filter the earliest start of unbound activities by pushing each activity (if needed) to the earliest slot when it can be executed without violating the capacity threshold.

for (int i = 0; i < start.length; i++) {
        if (!start[i].isBound()) {
            // j is the index of the profile rectangle overlapping t
            int j = profile.rectangleIndex(start[i].getMin());
            // TODO 3: push i to the right
            // hint:
            // You need to check that at every-point on the interval
            // [start[i].getMin() ... start[i].getMin()+duration[i]-1] there is enough space.
            // You may have to look-ahead on the next profile rectangle(s)
            // Be careful that the activity you are currently pushing may have contributed to the profile.

        }
    }

Check that your implementation passes the tests CumulativeTest.java.

[TT2015]Gay, S., Hartert, R., & Schaus, P. (2015, August). Simple and scalable time-table filtering for the cumulative constraint. In International Conference on Principles and Practice of Constraint Programming (pp. 149-157). Springer.

The Resource-Constrained Project Scheduling Problem (RCPSP)

A set of activities must be executed on a set of resources.

Fill in all the gaps in order to solve the RCPSP problem.

Your task is to terminate the implementation in RCPSP.java.

  • Create the cumulative constraint
  • Post the precedence constraint
  • Add instructions to minimize the makespan
  • Minimize the makespan

Several instance of increasing sizes are available with 30,60,90 and 120 activities. In order to test your model, the instance j30_1_1.rcp should have a minimum makespan of 43. Don’t expect to prove optimality for large size instances but you should reach it easily for 30 activities.