Saturday, March 3, 2012

RSPSP

Here is an example of a simple resource-constrained project scheduling problem formulation as presented in a computational study:

image

I probably would write this as:

image

This can save us a few non-zeros in the problem. In general if there are repetitive structures in the model, you should think about introducing extra variables and constraints. So I would write the model equations in GAMS like:

calcstart(j)..
  y(j) =e=
sum
(t, tval(t)*x(j,t));

objective..
  makespan =e=
sum
(last, y(last));

precedence(prec(i,j))..
  y(j) =g= y(i) + duration(i);

resources(r,t)..
 
sum
(overlap(j,t,tstart),usage(j,r)*x(j,tstart)) =l= available(r);

onestart(j)..
 
sum
(t, x(j,t)) =e= 1;


Notes:
  • The set start is a singleton set. Looks like a summation in the objective, but it really is just picking the correct element.
  • The set overlap is constructed to simplify equation (5). In general equations are more difficult to debug than sets. They can only be looked at in the listing file after you have a working model (the equation listing is only visible when . Sets can more easily be inspected (using a display statement or through the gdx viewer). So it makes sense to introduce extra sets to make the equations as simple as possible.

The paper presenting this model (here) makes -- in my opinion -- a mistake by only considering the number of variables and equations as a measure of the size of a particular model formulation. The number of nonzero elements should also be considered, and sometimes we are happy to add more variables and equations if this reduces the number of nonzero elements in a significant way.