RCPSP minizinc model

Question

I'm working on a resource‐constrained project scheduling problem (RCPSP) in Minizinc but I have problems with the running times when the dataset is big (like 400 jobs, 2 resources, 1,000 precedences, and maximum time of 30). With Gecode, after two hours, the model is still running (for the smaller datasets we get the correct result).

I think it could be that the restrictions aren't the best to model this problem with constraint programming.

I'm working with binary variables x[j,t] that is 1 iff the job j starts in time t.

For the resource constraint, I'm using

constraint forall(k in RESOURCE) (
             forall(t in TIME) 
                   (sum(j in TASK)(res[k,j]*(sum(s in max(t-d[j]+1,0)..t)(x[j,s])))  <=L[k])
                   );

Where res[k,j] is the amount of resource k used by job j in each period (assume it is constant for all times that j is activated). The max operator is to avoid troubles with the index of x.

And for the precedencies constraint, I'm using the constraint

$$x[j_2,t]\leq x[j_1,t-d_{j_1}],\quad\forall t \in[0,\dots,T_{\max}],\forall(j_1,j_2)$$ where $j_1$ is predecessor of $j_2$ and $d_{j_1}$ is the duration of $j_1$.

The goal is to optimize the net present value (not makespan, like almost all implementations I have found).

Do you have any recommendations? I'm not using the classical model constraint for index problem, but I'm not sure about this formulation.

Two (meta) recommendations: a) Try other solvers, e.g. Chuffed and Google or-tools; both can be quite fast. b) Try different search heuristics to "solve". This might speed up the model a lot. — hakank, Jan 09 '20 at 18:42

score 5 · Answer 1 · answered Jan 09 '20 at 19:53

With constraint solvers, I think it is generally desirable to exploit global constraints as much as is possible. As an alternative to your resource constraint, have a look at the section on the "cumulative" constraint (and the example using it) in the MiniZinc Handbook.

RCPSP minizinc model

1 Answers1