## Making it for 2014 Cup and 2016 Olympics: Scheduling Tasks with CP, part I

Recently, Brazil volunteered to host the 2014 World Cup and the 2016 Summer Games in Rio de Janeiro. Personally, I think that those guys that put our name on the candidacy lists are nuts. Indeed, Jerome Valcke, FIFA General Secretary, has been warning us about deadlines since May 2010:

“The red light has been switched on. Brazil is not on the right path. This year there is a presidential election, so almost nothing will happen. Next year, carnival comes along. So is everything going to start only after carnival?”

Nevertheless, since there is no way to go back now, maybe OR can help us planning in advance, reducing costs and avoiding last minute surprises (what didn’t happen in the 2007 Pan American Games).

First things first, how can we handle an increasingly tighter schedule of planning and operational activities subject to Brazilian reality?
Let’s start with a very simple example using constraint programming (CP) in the modeling language OPL and then elaborate over it.

Decision variables

Let’s say that we have n activities to be performed, ranging from i=1 to n, and a number of vectors representing properties of those activities, such as earlyStart, lateFinish, minSize and maxSize. With such data, it is quite straightforward to model our main decision variables:

dvar interval activity[i in 1..n]
in earlyStart[i]..lateFinish[i]
size minSize[i]..maxSize[i];

An interval is a special structure representing interrelated variables such as start, end and size. Using indexes, it was quite simple to constrain four properties of each interval of the vector with the input data.

Objective function

What about hushing things up? So far, we know that the size of each activity might vary. Probably, it might cost a bit more if we reduce its size. Thus, if we have a deadline to achieve and a finite budget (as a Brazilian taxpayer, I hope for that!), we must try to minimize such costs of anticipating conclusions. Let’s consider that the cost of reducing the size of one activity in one time unit is given by the vector reductionCost. Our objective function is as follows:

minimize sum(i in 1..n) reductionCost[i]*(maxSize[i]-sizeOf(activity[i]));

OPL is a declarative modeling language, for which reason many mathematical expressions are quite easy to describe, like the cost described in the objective function.

Constraints

The constraints of the problem are surrounded by a “subject to” block. To start with, let’s consider a very simple constraint: the execution of some tasks is constrained by others that must precede them. To represent this in OPL, I will use a tuple for each precedence relation and a set to collect them all:

tuple Precedence {
int previous;
int next;
}
{Precedence} precedencies = {<1,2>, <2, 3>, <3,4>};

Now it is easy to place a constraint among the activities:

subject to {
forall (prec in precedencies) {
endBeforeStart(activity[prec.previous], activity[prec.next]);
}
}