Originally posted by: ClemsonTiger

Hi all,

I want to transform the sched_flowshop problem to a permutation flow shop in which a conveyor 

transfers products across stations (machines), and at each station the task required is done. So its basically a paced production line.
I have several questions:
1- I need to limit the interval variables to start and end within the station boundaries.
is there an easy way to loop over the logical OR operator so that this will be more 

compact:
forall (i in Products)
    forall (j in Stations)
    ((j*sLength <= startOf(itvs[i][j])) &&
    ((j+1)*sLength >= endOf(itvs[i][j])))
    ||
    (((j+1)*sLength <= startOf(itvs[i][j])) &&
    ((j+2)*sLength >= endOf(itvs[i][j])))
    ||
    (((j+2)*sLength <= startOf(itvs[i][j])) &&
    ((j+3)*sLength >= endOf(itvs[i][j])))
    ||
    (((j+3)*sLength <= startOf(itvs[i][j])) &&
    ((j+4)*sLength >= endOf(itvs[i][j])));

Is it possible to just define it within the interval variable definition?
dvar interval itvs[i in Products][j in Stations] in (???) size Durations[i][j] ;

I looked into using the calendar and the step function, but I don't have any holes in the 

calendar.I also tried to use the OR in the loop but always get errors.

2- I need a constraint to limit one interval variable per station.
Is it better to model the problem using alternatives? I am trying to avoid using alternatives since I want to solve big problems. 

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.
Thanks

Originally posted by: Petr Vilím

Hello,

to the question 1, I think that you can use forbidOverlap constraint(s). Or, if durations of the tasks are fixed, you can also use forbidStart or forbidEnd instead (however forbidOverlap is more convenient).

Regarding question 2, is there some reason why noOverlap constraint cannot be used for each station? The constraint noOverlap is done exactly to limit only one interval variable at a time.

From the question 1 it seems to me that all the tasks have the same duration (and therefore you were able to model the problem using alldiff). My guess is that in this case the model with alldiff will perform better, but it is indeed worth trying.

Best regards, Petr 

Originally posted by: ClemsonTiger

Hi,

So for 1, there is no way to loop using the logical OR? I can't find the forbidOverlap constraint, did you mean forbid start/end? I know the noOverlap is used for the sequencing variable.

For 2: Does that mean I have to model stations as resources? I am not worried about interval variables overlapping. I want to forbid having two tasks done at the same station consecutively. That is if one task is finished early during the station window, no other task should be scheduled for that station window (keep it idle).

As for the tasks, each task has a different duration but I used alldiff just to generate the sequence and then the calculations are done based on that. 

Thanks

Originally posted by: Petr Vilím

Ha, I'm sorry, I messed up the name of the constraint. The right name is forbidExtent. not forbidOverlap. Using this constraint you can forbid a time interval to overlap specific time points (or intervals). I believe that's what you do in the big or expression.

And for 2, I better understand now what you need. Yes, I think that you need a noOverlap constraint for each station. Additionally, at least for the point of view of the station I suggest to prolong the tasks to cover whole "station window". It could be done by having two interval variables per task, lets call them TASK and COVER. TASK is the "real task" with the right duration and COVER is its extension to cover whole station window. Those intervals could be tied together using the following constraints:

• startBeforeStart(COVER, TASK) or even startAtStart(COVER, TASK)
• endBeforeEnd(TASK, COVER)
• forbidStart/forbidEnd on COVER to allow start/end only at the window boundaries
• COVER should have fixed length (and length of TASK shouldn't be bigger than length of COVER).

I hope this helps,

Best regards, Petr

Originally posted by: ClemsonTiger

So for the forbidExtent the use is " to indicate that a given interval variable cannot overlap a particular date", does this mean I should have a step function to define each station?

​For 2, I am trying to model it in an efficient way so if I have 1000 tasks I would end up with double that by adding the cover interval. I think I can deal with that using just the forbidStart constraint.

I am still wondering why I can't loop over OR condition like this:

forall (i in Products)
    forall (j in Stations)

            or (c in 0..3)
    ((c*sLength <= startOf(itvs[i][j])) &&
    ((c+1)*sLength >= endOf(itvs[i][j])));

Thanks 

Originally posted by: Petr Vilím

Ad 1, yes, if the windows are different between stations then you need a different function for each station. Otherwise you can share the function.

Ad 2, unfortunately operator or doesn't support this kind of "sum syntax" in OPL. You can use boolean expression as 0/1 expression. I.e instead you can use "1 <= sum (...) boolExpr". However it is not good modeling practice, especially when the boolean expressions contain the same variable(s), because constraint propagation for such expressions is weak.

If you can avoid doubling the number of interval variables using forbidStart then it is of course the best solution. Otherwise adding more interval variables is not costly, the main cost are additional constraints. "Small" constraints are usually cheap: precedences, forbidStart/End/Extent etc. "Big" constraints are much more costly: noOverlap, cumulative expressions etc. Note that long integer expressions, such as the or statement we are discussing, are often also expensive.

Petr

Originally posted by: ClemsonTiger

hi, Thanks for you help.

I am trying the alternative route now since its hard to loop over the OR condition. So basically defining different periods each with a start - end window.

I am having trouble loading the model as it gives me error. Could you please check what is wrong?

dvar interval itvs[i in Products][j in Stations]  size Durations[i][j] ;
dvar interval itvsOpt[i in Products][j in Stations][t in Periods] in Pstart[t]..Pend[t];

..

forall (i in Cars, j in Stations)
   alternative(itvs[i in Products][j in Stations], all (t in Periods) itvsOpt[i in Products][j in Stations][t in Periods]);

Basically the product,station interval can occur in one of different periods.  
 

I am getting  (Internal error: unsupported array slot index at ../../../src/loader.cpp:3716.)

Is there anything wrong with the idea?

Thanks

Originally posted by: Petr Vilím

Hello,

I think that the red text should be removed from the constraint:

forall (i in Cars, j in Stations)
   alternative(itvs[i in Products][j in Stations], all (t in Periods) itvsOpt[i in Products][j in Stations][t in Periods]);

I'm wondering why do you still need the long OR condition? I thought that you can replace it by forbidStart..

Petr

Originally posted by: ClemsonTiger

Thanks that was the mistake.

forbidStart will help me in solving the 1 task per station problem but will not help me in determining the boundaries of stations in which the task should be performed.

basically I am looking at the sched_flowshop problem in which a task need to be done within a time window since the product is moving on a conveyor belt. And instead of machines I have these stations that the product moves through. My other constraint is only one task is to be done in each station as there will be only one product on the conveyor belt at that time in that station. There are still more constraints to come to define the problem and at this point I am starting to question if this will be more efficient than the other model I have or not.

Originally posted by: Petr Vilím

Hmm, I still not get it. Last time you wrote the or-expression it was:

forall (i in Products)
    forall (j in Stations)

            or (c in 0..3)
    ((c*sLength <= startOf(itvs[i][j])) &&
    ((c+1)*sLength >= endOf(itvs[i][j])));

And from your description "only one product on the conveyor belt at that time in that station" this seems to me as noOverlap constraint.

Petr

Originally posted by: ClemsonTiger

Yes , I think you told me its not possible to do this in OPL as it doesn't support this kind of "sum syntax".

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].

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. 

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. 

Originally posted by: Petr Vilím

Hello,

your last post doesn't contain any question so I'm not sure whether you still want some advice. So last comments.

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.

Best regards, Petr

Originally posted by: ClemsonTiger

Thanks for your explanation, I use noOverlap but only to model the disjunctive constraint of intervals overlap in time. 

I appreciate your help on this, I will look into using the cover intervals.

Thanks