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.