Originally posted by: Wahiba123

Hello every one.

I am writing some line of code to solve a permutation scheduling flowshop. I have use the example qiven by Cplex (sched_pflowshop) and try to modify it.

I have define a dvar intarval  "cover" that covers some sub inetrvals (dvar itvs) with the "alternative constraint" . What I want to get is that each machine stops for break each time it reaches a given "limit" time (for a duration).

Next is the modified code but the model replies no solution. Can you help me.

sing CP;
int n = ...;
int m = ...;
int L = ...;
int limit=...;
int P[k in 0..m-1][j in 0..n-1] = ...;
int M[k in 0..m-1][l in 0..L-1]=...;


//variable de décision
dvar interval itvs[j in 0..n-1][k in 0..m-1] size P[k][j];
dvar interval cover[l in 0..L-1][k in 0..m-1]optional;
dvar sequence mchs[k in 0..m-1] in all(j in 0..n-1) itvs[j][k] types all(j in 0..n-1) j;
execute {
 //cp.param.FailLimit = 10000;
  cp.param.TimeLimit=10;
  cp.param.Workers = 1;
}
//the objective function
minimize max(j in 0..n-1) endOf(itvs[j][m-1]);
subject to {
  forall (k in 0..m-1)
    noOverlap(mchs[k]);
  forall (j in 0..n-1, k in 0..m-2)
     endBeforeStart(itvs[j][k], itvs[j][k+1]);
  forall (k in 0..m-1, j in 0..n-1: 0<k) 
    typeOfPrev(mchs[k],itvs[j][k],n)==typeOfPrev(mchs[0],itvs[j][0],n);
  forall(k in 0..m-1, l in 0..L-1)
    alternative(cover[l][k],all(j in 0..n-1)itvs[j][k]);
  forall(k in 0..m-1, l in 0..L-1)
    lengthOf(cover[l][k])<=limit;
  forall(k in 0..m-1, l in 0..L-2)
    endBeforeStart(cover[l][k],cover[l+1][k],M[k][l]);
    
}
execute {
  for (var j = 0; j <= nbJobs-1; j++) {
    for (var o = 0; o <= nbMchs-1; o++) {
      write(itvs[j][o].start + " ");
    }
    writeln("");
}  
 }
  

Originally posted by: Petr Vilím

Hello,

the model has no solution because each alternative constraint says that only one of the constrained itvs intervals can be present. However all of them are declared present from the beginning (only cover are optional).

You can use span constraint instead. However maybe better is to model breaks also as interval variables that are part of the mchs sequence variable. This way nothing can overlap with breaks. Breaks then can be ordered using:

  endBeforeStart(break1, break2);

and maximum delay "limit" between consecutive breaks can be set by:

  startBeforeEnd(break2, break1, limit);

Best regards, Petr

Originally posted by: Wahiba123

Thanks a lot for your response.

Can you just help me on how to formulate the declaration of the sequence to take into account both of "itvs" and "breaks" such as the number of breaks is not prefixed???

And if i have understand well, the breaks should be declared us next:

dvar interval breaks[k in 0..m-1][l in 0..L-1] size M[k][l];

Originally posted by: Wahiba123

Hello, I have change my model according to the cited recommandation but it still not working. It may be wrong ??? I need some Help.

sing CP;
int n = ...;
int m = ...;
int L = ...;
int limit=...;
int P[k in 0..m-1][j in 0..n-1] = ...;
int M[k in 0..m-1][l in 0..L-1]=...;


//variable de décision
dvar interval itvs[k in 0..m-1][j in 0..n-1] size P[k][j];
dvar interval mts[k in 0..m-1][l in 0..L-1] size M[k][l];
//dvar interval cover[l in 0..L-1][k in 0..m-1] optional;
dvar sequence mchs[k in 0..m-1] in append(all(j in 0..n-1) itvs[k][j],all(l in 1..L-1)mts[k][l]) types append(all(j in 0..n-1) j, all(l in 0..L-1) l);
execute {
 //cp.param.FailLimit = 10000;
  cp.param.TimeLimit=10;
  cp.param.Workers = 1;
}
//the objective function
minimize max(j in 0..n-1) endOf(itvs[j][m-1]);
subject to {
  forall (k in 0..m-1)
    noOverlap(mchs[k]);
  forall (j in 0..n-1, k in 0..m-2)
     endBeforeStart(itvs[k][j], itvs[k+1][j]);
  forall (k in 0..m-1, j in 0..n-1: 0<k) 
    typeOfPrev(mchs[k],itvs[k][j],n)==typeOfPrev(mchs[0],itvs[0][j],n);
  forall(k in 0..m-1, l in 0..L-2)
    endBeforeStart(mts[k][l],mts[k][l+1]);
  forall(k in 0..m-1, l in 0..L-2)
    startBeforeEnd(mts[k][l+1],mts[k][l],limit); 
}

Originally posted by: Petr Vilím

Hello,

I think I forgot "-" sign in the following constraint:

startBeforeEnd(break2, break1, -limit);

and because of that your model my be infeasible (is it what you meant by not working?). I'm sorry about that.

Otherwise your model seems OK to me, although I do not understand the constraint with typeOfPrev.

If it still doesn't work then could you also give us your .dat file?

Best regards, Petr

Originally posted by: Wahiba123

Hello, the model still not working. It returns errors for the "noOverlap" and the "TypeOfPrev". Next is the data file:

.dat

n=5;
m=3;
L=3;
limit=150;
P=[[
51,6,94,98,50],
[10,62,22,78,87],
[30,82,4,72,16],
];
M=[
[10,8,6],
[4,1,2],
[10,8,9],
];

Let me explain my problem much more.

What I want to get is a sequence with the same order of "itvs" from the first to the last machine. For the "mts", which designates the breaks interval in this case,has to be processed (each time the total processing time in each machine reaches the limit) first by first (for example for the first machine the first break is about 10 the next about 8 and the last one is about 6). 

Thanks.

Originally posted by: Petr Vilím

Hello,

the issue seems to be in the definition of sequence variables mchs. When listing interval variables l is in 1..L-1 but in types it is in 0..L-1. The arrays then have a different length, therefore the error.

Typically permutation flowshop uses sameSequence constraint (as in example sched_pflowshop). In your case I guess that maintenance intervals are not considered part of the same sequence. However although the constraints on typeOfPrev are limitted to itvs, it will still force the maintenance intervals to be in the same sequence (as typeOfPrev could be a maintenance interval). I recommend you to have a look on the sameCommonSubSequence constraint, it can force the same order subsets of two sequence variables.

Best regards, Petr

Originally posted by: Wahiba123

Thanks for your response. But the sameCommonSubSequence constraint can not be used in this case such as the sequence variables should be of the same size.

Is there an other way to do it ????