10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – hakank Jan 9 at 18:42
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.