Hello

I'm working on a scheduling CP model using ILOG CPLEX Optimization Studio 20.1. 

In my .mod file, I'm using a set of constraints "endBeforeStart" to guarantee that the starting time of jobs in a set of machines is only possible if they completed their process on a previous set of machines.

Let's me explain that with an example:

forall (j in Jobs, p in 0..2, q in 3..4)
endBeforeStart(itvs[j][p],itvs[j][q]);

forall (j in Jobs, r in 3..4, s in 5..6)
endBeforeStart(itvs[j][r],itvs[j][s]);

For all jobs, they must accomplish their process on machines 0,1, and 2 before starting their process on machines 3 and 4. In a similar manner, all jobs must accomplish their process on machines 3 and 4 before starting their process on machines 5 and 6.

Then, I'm trying to find a way to express that set of constraints in only one parametric "endBeforeStart" expression, reading the information from a 2D array from the .dat file. For the previous example, the structure of the 2D array would be:

A = [
[0,1,2]
[3,4]
[5,6]
];

There exist a way to do that?

Thanks in advance
Francisco

------------------------------
Francisco Yuraszeck
Yuraszeck
------------------------------

#DecisionOptimization

You can do with redefining A as a set of possible precedences among machines 

in the .mod file:

using CP;

range Jobs = 1..1;

{int} machines = ...;

tuple Precedence { int pre; int post;}
{Precedence} precedences with pre, post in machines = ...;

dvar interval itvs[Jobs][machines]; //in ... 

constraints{
 forall (j in Jobs, <pre,post> in precedences)
	endBeforeStart(itvs[j,pre],itvs[j,post]);
  
}​

in the .dat file, you would have something like 

machines = {0 1 2 3 4 5 6};
precedences = {<0 3> <0 4> <1 3> <1 4>
<2 3> <2 4> <3 5> <3 6> <4 5> <4 6>};
​

------------------------------
David Gravot
------------------------------

Hello,
Following up on David Gravot's message, and if your goal is to have a simple structure to define "endBeforeStart", another option is to build the list of precedences from A as follows (providing A is instead a list of sets instead of a 2D array):

using CP;

int MAX_STAGES = 2;
range stages = 0..MAX_STAGES;

{int} machines = {0, 1, 2, 3, 4, 5, 6};

tuple machines_stage_pair {
  {int} machines_pred;
  {int} machines_post;
}

tuple Precedence { int pre; int post;}


{int} A[stages] = [{0, 1, 2}, {3, 4}, {5, 6}];

{machines_stage_pair} stages_pairs = {<A[i], A[i+1]> | i in stages : i < MAX_STAGES};

{Precedence} precedences with pre, post in machines = {<pr, po> | ms in stages_pairs, pr in ms.machines_pred, po in ms.machines_post};

execute {
  writeln("A = ", A);
  writeln("stages_pairs = ", stages_pairs);
  writeln("precedences = ", precedences);
}​

Then, executing the above OPL code produces:

A =  [{0 1 2} {3 4} {5 6}]
stages_pairs =  {<{0 1 2} {3 4}> <{3 4} {5 6}>}
precedences =  {<0 3> <0 4> <1 3> <1 4> <2 3> <2 4> <3 5> <3 6> <4 5> <4 6>}

Regards

------------------------------
Hugues Juille
------------------------------

Hello Francisco,
As an addition to the previous answers, in case your groups of activities are large (for instance if A = [  [1,...,n], [n+1,...,2n] ]), you can avoid the quadratic number of precedence constraints (exactly n^2 here) by creating one additional interval variable G[i] per group i that is constrained to span the interval variables of its group: span(G[i], [...,X[i][j],...]) and you would directly add the endBeforeStart constraints between these spanning intervals (endBeforeStart(G[i],G[i+1])). This way you only get a linear number of precedence constraints. Furthermore, these intervals G[i] may make sense from a business problem point of view (you may naturally want to express additional constraints on them, etc.)
Regards,

Philippe



------------------------------
Philippe Laborie
------------------------------