« New constraint programming blog: Be-cool Blog | Main | Miscellaneous news »

Scheduling with the cumulatives constraint in Gecode

One of the few problems of my learning problems that has not been modeled in Gecode before was the Furniture moving problem (from Marriott & Stuckey "Programming with Constraints", page 112f). The reason has been that Gecode don't have the common cumulative constraint, but instead the generalized and extended cumulatives constraint (note the last "s"). This cumulatives constraint was defined and explained in the paper A new multi-resource cumulatives constraint with negative heights (ps.Z) by Nicolas Beldiceanu and Mats Carlsson.

Furniture moving

The last couple of days I have read that paper and experimented with the cumulatives constraint in modeling the Furniture moving problem. The Gecode program is here: furniture_moving.cpp.

Some notes
The cumulatives paper shows 8 examples/variants of usuage (A..H, which are explained below) and the Furniture moving problem is modeled after the G variant, a covering model of producers/consumers. The main approach is that we have the four tasks (consumers, the furnitures to move) and three movers (producers). The height of the consumers is coded as negative, and the movers as height 1 (positive), i.e.
int _durations[] = {   30,    10,  15,   15                };
int _height[] =    {   -2,    -1,  -2,   -2,      1,  1,  1};
int _limit[] =     {0}; // just one machine
Just for fun, I also let the durations of the movers "free" to see how long they have to work according to this model. The result was that the movers 2 and 3 have to work full time (60 minutes), but the first mover has to work just 10 minutes.

8 Cumulatives examples

In the paper cited above, Beldiceanu and Carlsson showed 8 different variants (A to H) of how to model with the cumulatives constraint. I have tried to implement all these examples in Gecode as faithful as possible.

The Gecode code is cumulatives_examples.cpp and is fairly general with a short explanations (cited from the paper) for each variants. For selecting a specific problem instance it takes a command line parameter where 0 is example A to parameter 7 for example H.

Below are some comments for each example, and as said before there are more comments in the Gecode code. Please note that Gecode is 0-based so we start numbering tasks and machines from 0 and onward.

Example A

This is the "plain old" cumulative with one machine.

Example B

cumulative with two machines.

Example C

Note that the atmost parameter of cumulatives is set to false since we have an at least constraint. Also a dummy task (0) are used here.

Example D

Same as the above, except for the "dummy" task. Also, I have added an another cumulatives constraint with atmost=true so all tasks are not "stacked" above each other.

Example E

Producer/consumer model. This one was quite tricky to understand first, but after reading the description some times I realized it's beauty: all producers start at time 0 and and produce whatever they produce, and all consumers ends at the "last date" (here time 6) and consumes whatever they consumes.

Example F

Generalization of example E with two machines.

Example G

A "covering problem", also elegant stated with cumulatives. Here there are two tasks (consumers, task 0 and 1) which have negative height, and 4 persons (producers) with the positive height 1. The atmost parameter must be false.

It is this variant that the above mentioned Furniture moving problem was modeled after.

Example H

A generalization of Example G with two machines. Here I have hard coded which machine a task/person should belong since otherwise only task 6 would be at machine 1. Also, I added an atmost limit for each machine for esthetic reasons.

Another scheduling example: Building a house

This example is a standard example from OPL: how to build a house with some dependencies of different tasks, e.g. that masonry must be finished before carpentry, painting must be finished before moving in etc.

This problem was done in Gecode with cumulatives (as variant A, see above) and was very straightforward to implements, both the cumulatives and the dependencies graph. There code is here: building_a_house.cpp.

See also: Some scheduling models in Comet

Comet has a great support for scheduling with a special Schedule framework, much like OPL's. Here are my Comet models that use this Schedule framework. The two first models are standard OPL examples. Also, the Comet model furniture_moving_cumulative.co is a variant of the Furniture moving problem, using a cumulative constraint implemented as a decomposition.