6110https://www.ibm.com/developerworks/community/forums/atom/forums?categoryUuid=11111111-0000-0000-0000-000000002067OPL using CP Optimizer Topics and Replies2016-10-24T18:03:29.055ZIBM Connections - Discussion Forumurn:lsid:ibm.com:forum:a2511205-e711-405d-a516-137dc66341d9Modeling a sequencing problem via CP vs CP scheduler2016-10-24T18:03:29.055ZClemsonTiger270007PMKYactive2016-10-24T18:03:29.055Z2016-10-24T18:06:52.301ZClemsonTiger270007PMKYactive2016-10-24T18:03:29.285Z2016-10-24T18:03:29.285Z2016-10-24T18:03:29.407Z2016-10-24T18:03:29.407Z2016-10-24T18:03:29.539Z2016-10-24T18:03:29.539Z2016-10-24T18:03:29.639Z2016-10-24T18:03:29.639Z<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
Hi again,
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
I have been getting help in this forum in modeling my problem and I appreciate all of those who helped. Since there are more than one way to model a problem I tried to model the sequencing problem to be solved using the CP scheduler by introducing interval variables. I am not sure if this is the most efficient way but I have tried several ways of modeling it but I get stuck somewhere. The CP scheduling model is taking too much time and not getting to the optimal solution, I am wondering if I did anything wrong. I am using relative time in the first model, and actual time to define the start of each task in each station for model 2 (ie, for model 1 the start of all stations is time 0 , while for model 2 the starts of each station depends on the station length so station 1 starts at 0 and station 2 starts at 15 if station length is 15). I want to get the best performance out of the CP but looks like the scheduler is not providing any help here and the problem to be solved is harder.
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
Is my way of modeling the problem correct or is there a simpler way to model it? Thanks
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
<strong>Model 1:</strong>
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
using CP;<br />
int nbrProds=...;<br />
range Products=1..nbrProds;<br />
int nbrPeriods=nbrProds;<br />
range Periods=1..nbrPeriods;<br />
int nbrStations=...;<br />
range Stations=1..nbrStations;<br />
int c=...;<br />
int l=...;<br />
int duration[Products][Stations]=...;<br />
dvar int seq[Periods] in Products;<br />
dvar int s[Stations][Periods] in 0..c;<br />
dvar int f[Stations][Periods] in 0..2*c;<br />
dvar boolean Over[k in Stations][t in Periods];<br />
minimize sum(k in Stations, t in Periods) Over[k][t];<br />
subject to {<br />
forall (k in Stations)<br />
s[k][1]==0;<br />
forall (k in Stations)<br />
forall (t in Periods) f[k][t]==s[k][t]+duration[seq[t]][k];
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
forall (k in Stations) <br />
forall (t in Periods:t>=2){<br />
(f[k][t-1]>l) =><br />
(<br />
(s[k][t]==maxl(0,s[k][t-1]-c)) &&<br />
(Over[k][t-1]==true)<br />
);<br />
!(f[k][t-1]>l) =><br />
(<br />
(s[k][t]==maxl(0,f[k][t-1]-c)) &&<br />
(Over[k][t-1]==false)<br />
);<br />
}<br />
allDifferent(all (t in Periods) seq[t]);<br />
}
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
<strong>Model 2:</strong>
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
using CP;
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
int nbrProds = ...;<br />
int nbStations = ...;<br />
int l=...;<br />
int c=...;
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
<br />
range Products = 0..nbrProds-1;<br />
range Stations = 0..nbStations-1; <br />
range Periods = 0..nbrProds-1;
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
int Pstart[j in Stations,t in Periods]=...;<br />
int Pend[j in Stations,t in Periods]=...;
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
int Durations[i in Products][j in Stations] = ...;
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
<br />
dvar interval itvs[i in Products][j in Stations] size Durations[i][j] ;<br />
dvar interval itvsOpt[i in Products][j in Stations][t in Periods] optional in Pstart[j][t]..Pend[j][t] ;<br />
dvar boolean Over[j in Stations][t in Periods];
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
minimize sum(j in Stations,t in Periods)Over[j][t];<br />
subject to {<br />
forall (i in Products,j in Stations) <br />
alt: alternative(itvs[i][j], all (t in Periods) itvsOpt[i][j][t]);<br />
forall (j in Stations, t in Periods)<br />
sum(i in Products) presenceOf(itvsOpt[i][j][t])<=1; <br />
forall (i in Products, k in Products, j in Stations, t in Periods: t>0 && i!=l)<br />
(presenceOf(itvsOpt[i][j][t])>=1 && presenceOf (itvsOpt[k][j][t-1])>=1 && (Over[j][t]==0 && Over[j][t-1]!=1)) => (startOf(itvsOpt[i][j][t])>=Pstart[j][t]+(endOf(itvsOpt[k][j][t-1])-(Pstart[j][t-1]+c)));<br />
forall(i in Products)<br />
forall(j in Stations:j<nbStations-2)<br />
forall(t in Periods:t<nbrProds-2)<br />
presenceOf(itvsOpt[i][j][t])=>presenceOf(itvsOpt[i][j+1][t]);<br />
}
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
</p>
<p dir="ltr" style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">
</p>none, view_forum, view_categoryurn:lsid:ibm.com:forum:d9bb773c-228e-44e1-b1f2-b4d713eefe83Permutation flow shop problem 2016-10-17T17:08:29.577ZClemsonTiger270007PMKYactive2016-10-20T12:24:13.340Z<p dir="ltr">
Hi all,
</p>
<p dir="ltr">
I want to transform the sched_flowshop problem to a permutation flow shop in which a conveyor
</p>
<p dir="ltr">
transfers products across stations (machines), and at each station the task required is done. So its basically a paced production line.<br />
I have several questions:<br />
1- I need to limit the interval variables to start and end within the station boundaries.<br />
is there an easy way to loop over the logical OR operator so that this will be more
</p>
<p dir="ltr">
compact:<br />
forall (i in Products)<br />
forall (j in Stations)<br />
((j*sLength <= startOf(itvs[i][j])) &&<br />
((j+1)*sLength >= endOf(itvs[i][j])))<br />
||<br />
(((j+1)*sLength <= startOf(itvs[i][j])) &&<br />
((j+2)*sLength >= endOf(itvs[i][j])))<br />
||<br />
(((j+2)*sLength <= startOf(itvs[i][j])) &&<br />
((j+3)*sLength >= endOf(itvs[i][j])))<br />
||<br />
(((j+3)*sLength <= startOf(itvs[i][j])) &&<br />
((j+4)*sLength >= endOf(itvs[i][j])));
</p>
<p dir="ltr">
Is it possible to just define it within the interval variable definition?<br />
dvar interval itvs[i in Products][j in Stations] in (???) size Durations[i][j] ;
</p>
<p dir="ltr">
I looked into using the calendar and the step function, but I don't have any holes in the
</p>
<p dir="ltr">
calendar.I also tried to use the OR in the loop but always get errors.
</p>
<p dir="ltr">
<br />
2- I need a constraint to limit one interval variable per station.<br />
Is it better to model the problem using alternatives? I am trying to avoid using alternatives since I want to solve big problems.
</p>
<p dir="ltr">
I am basically looking for the optimal sequence of products that minimizes a given objective, I modeled this problem using the alldifferent constraint but wanted to see if using the interval variables and the CP scheduler will get me better results.<br />
Thanks
</p>none, view_forum, view_categoryurn:lsid:ibm.com:forum:f87b3fee-3e74-40b1-9ef4-e37cdedb251cRe: Permutation flow shop problem2016-10-20T12:23:30.725ZClemsonTiger270007PMKYactive2016-10-20T12:23:30.725Z
<p dir="ltr">
Thanks for your explanation, I use noOverlap but only to model the disjunctive constraint of intervals overlap in time.
</p>
<p dir="ltr">
I appreciate your help on this, I will look into using the cover intervals.
</p>
<p dir="ltr">
Thanks
</p>
none, view_forum, view_categoryurn:lsid:ibm.com:forum:dc86d245-f233-49bc-8756-b0045fbfd4dcRe: Permutation flow shop problem2016-10-20T08:07:01.767ZPetr Vilím270002KBKNactive2016-10-20T08:07:01.767Z
<p dir="ltr">
Hello,
</p>
<p dir="ltr">
your last post doesn't contain any question so I'm not sure whether you still want some advice. So last comments.
</p>
<p dir="ltr">
I recommend again the model with two interval variables per task: TASK and COVER. It allows to use noOverlap on COVER tasks very easily. The noOverlap constraint is designed to propagate "one task at a time" as efficiently as possible, it is very hard beat by anything else (in some degenerated examples it could be beaten by alldiff). NoOverlap is also much smarter than any expression could be, especially when parameter NoOverlapInferenceLevel is increased. For example, consider three tasks with durations 2, 3 and 5 that must be processed during interval 0..9. NoOverlap will see immediately that there is no solution. Furthermore, CP Optimizer is trying to exploit the structure of the problem during the search and noOverlap constraints are important to recognize the structure. Without knowing the convergence towards good solutions could be slow.
</p>
<p dir="ltr">
Best regards, Petr
</p>
none, view_forum, view_categoryurn:lsid:ibm.com:forum:48341d3e-9515-4b38-ab61-32bc98f65575Re: Permutation flow shop problem2016-10-19T15:45:21.068ZClemsonTiger270007PMKYactive2016-10-19T15:45:21.068Z
<p dir="ltr">
Yes , I think you told me its not possible to do this in OPL as it <span style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">doesn't support this kind of "sum syntax".</span>
</p>
<p dir="ltr">
sLength is given data which define the station length in time units. I wanted to say that that for any product a task that is assigned to be done on station 1 (given data) should be only performed within station 1 boundaries which is [0,sLength].
</p>
<p dir="ltr">
now for the scheduler, if the station length is 10 and we have Duration[1][1]=4 (processing time required for product 1 on station 1) and Duration[2][1]=4 , the Overlap constraint will make sure that both of these tasks don't overlap in time but I can still start the first at time 0 and the second at time 4 and both will finish within the station 1 boundaries. The disjunctive constraint is not enough here as there should be another constraint saying that only one task can be performed per station at a given time. That is why I introduced the period part.
</p>
<p dir="ltr">
The problem is really simple but there are several ways to model it, I tried to avoid the optional intervals but I think I need it here.
</p>
none, view_forum, view_categoryurn:lsid:ibm.com:forum:4a7d00c7-c3d4-4360-99d9-b2f3edec6ef0Re: Permutation flow shop problem2016-10-19T15:22:51.116ZPetr Vilím270002KBKNactive2016-10-19T15:22:51.116Z<p dir="ltr">
Hmm, I still not get it. Last time you wrote the or-expression it was:
</p>
<p dir="ltr" style="color: rgb(0, 0, 0); font-family: Arial, sans-serif;">
<span style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">forall (i in Products)</span><br style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;" />
<span style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;"> forall (j in Stations)</span>
</p>
<p dir="ltr" style="color: rgb(0, 0, 0); font-family: Arial, sans-serif;">
or (c in 0..3)<br style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;" />
<span style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;"> ((c*sLength <= startOf(itvs[i][j])) &&</span><br style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;" />
<span style="font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;"> ((c+1)*sLength >= endOf(itvs[i][j])));</span>
</p>
<p dir="ltr">
</p>
<div dir="ltr">
<span style="line-height: 1.5;">Is it the or-expression we are still talking about? If yes then is sLength a constant or a decision variable?</span>
</div>
<p dir="ltr">
<span style="line-height: 1.5;">And from your description "</span><span style="color: rgb(84, 84, 84); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; background-color: rgb(238, 238, 238);">only one product on the conveyor belt at that time in that station</span><span style="line-height: 1.5;">" this seems to me as noOverlap constraint.</span>
</p>
<p dir="ltr">
<span style="line-height: 1.5;">Petr</span>
</p>none, view_forum, view_category