### 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

The

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

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.

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

This problem was done in Gecode with

`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[] = {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.-2, -1, -2, -2, 1, 1, 1}; int _limit[] = {0}; // just one machine

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