Originally posted by: hzwpku

Hi, I have a question about alwaysEqual:

There are n jobs. These jobs are processed in one batch machine which can process B jobs simultaneously. Jobs in one batch have same start time and stop time.

Each job has a processing time p_j. The processing time of one batch is equal to the longest processing time of jobs in that batch.

How to deal with this situation with alwaysEqual?

Hi,

you have a C++ example at

https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.8.0/ilog.odms.cpo.help/CP_Optimizer/reffileformatcpo/functions/alwaysEqual.html

and that can be written in OPL:

using CP;

range R=1..6;

int sizes[R]=[5,6,8,4,7,7];
int temperatures[R]=[0,0,0,1,1,2];

dvar interval itvs[i in R] size sizes[i];
stateFunction temperature;
cumulFunction nbParallelActivities=sum(i in R) pulse(itvs[i],1);

subject to
{
forall(i in R) alwaysEqual(temperature,itvs[i],temperatures[i]);

nbParallelActivities<=2;
}

which gives

regards

https://www.linkedin.com/pulse/ibm-think-ai-optimization-me-alex-fleischer/

Originally posted by: hzwpku

Thank you very much.

The solution of the above model is:

itvs = [<1 0 5 5> <1 0 6 6> <1 5 13 8> <1 13 17 4> <1 13 20 7> <1 20 27 7>];

The main difference is that the processing time of one batch is equal to the longest processing time of jobs in that batch.  When the first two jobs are assigned into

the same batch, the processing time of the batch should be 6, and all the jobs' duration in this batch should also be 6. The actual job processing time is dependent 

on the batch form.

How to deal with this situation?

Best regards!

Hi,

to go on with the previous example, you could say that 2 intervals that overlap have the same lenth:

using CP;

range R=1..6;

int sizes[R]=[5,6,5,4,7,7];
int temperatures[R]=[0,0,0,1,1,2];

dvar interval itvs[i in R] size sizes[i];
stateFunction temperature;
cumulFunction nbParallelActivities=sum(i in R) pulse(itvs[i],1);

subject to
{
forall(i in R) alwaysEqual(temperature,itvs[i],temperatures[i]);

nbParallelActivities<=2;

forall(ordered i,j in R) (overlapLength(itvs[i],itvs[j])!=0) => (lengthOf(itvs[i])==lengthOf(itvs[j]));
}

which gives

regards

Originally posted by: hzwpku

Thanks!

The idea  to make 2 intervals that overlap have the same length may work. 

At first, I describe the problem more clearly. Each interval has a size which is given, such as the above example: [5,6,5,4,7,7]. 

But when two jobs with different sizes are in same batch, the lengths of these two jobs are equal to the larger size between these two jobs, such as job 4 and job 5 can be assigned into 

one batch, the lengths of these two jobs are equal to 7 (the larger one between 4 and 7). The following solution is better than the above solution.

R     Present  Start  End  Size

1      1            0          5       5

2      1            5         11      6     

3      1            0          5       5

4      1            11        18      7

5      1            11        18      7

6      1            18        25     7

Best regards!

Hi,

then instead of setting the sizes of intervals you may set minimal values:

using CP;

range R=1..6;
int endHorizon=1000;

int sizes[R]=[5,6,5,4,7,7];
int temperatures[R]=[0,0,0,1,1,2];

dvar interval itvs[i in R] size sizes[i]..endHorizon;
stateFunction temperature;
cumulFunction nbParallelActivities=sum(i in R) pulse(itvs[i],1);

minimize max(i in R) endOf(itvs[i]);

subject to
{
forall(i in R) alwaysEqual(temperature,itvs[i],temperatures[i]);

nbParallelActivities<=2;

forall(ordered i,j in R) (overlapLength(itvs[i],itvs[j])!=0) => (lengthOf(itvs[i])==lengthOf(itvs[j]));
}

gives

regards

https://www.linkedin.com/pulse/making-decision-optimization-simple-alex-fleischer/

Originally posted by: hzwpku

Thank you very much. It is a great help.

Originally posted by: PhilippeLaborie

Hi,

The problem with the proposed model is that it is quadratic in size because of the constraints on each pairs of interval variables. This is not a good feature at all.

On state function, for batching, we introduced the notion of state alignment. So instead of the quadratic number of constraint, you can just use the alignment on your alwaysEqual constraints :
alwaysEqual(temperature,itvs[i],temperatures[i], true, true);

See the documentation: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.ide.help/OPL_Studio/opllangref/topics/opl_langref_scheduling_statefunc.html

You can also have a look at some example of batching in this article: http://ibm.biz/Constraints2018 (section 3.8 about state function variables)