Pinned topicCP Optimizer with setup times and tool switching
20180614T10:42:17Z

Answered question
This question has been answered.
Unanswered question
This question has not been answered yet.
Hi,
I'm currently having a hard time modeling a scheduling problem with CP Optimizer. The problem is the following:
I have multiple jobs and multiple machines in my environment. I created one interval decision variable array for the jobs and one optional decision variable array for the jobs to determine the machine they are assigned to.
Furthermore, for each machine, there's a sequence variable. N is a range for the jobs, M is the range for the machines. My code looks like this:
dvar interval jobs[j in N] in 1..(maxint div 2)1 size 5;
dvar interval jobs_opt[i in M][j in N] optional in 1..(maxint div 2)1 size 5;
dvar sequence machines[i in M] in all(j in N) jobs_opt[i][j];
Now here's my problem: For each job, there's a tool the job requires for processing. These tools have to be installed on the machine they are used on which requires a certain amount of time. I already have restrictions that represent the setup times that have to be considered if job j is processed before job k and they need different tools.
What I'm currently not able to add is the following: If the tool is used on machine 1 until 12:00, then the same tool can't be used at machine 2 at 12:01 because it has to be uninstalled at machine 1 and afterwards installed at machine 2. If that case occurs, I'd like to consider a 30minute delay between the processing of these jobs. So what I'd need is something like this:
forall(j,k in N:j!=k){
if((required_tool[j]==required_tool[k])&&(processing_machine[j]!=processing_machine[k]){
noOverlap(jobs[j], jobs[k], 30)
}
}
Obviously, like this, the code does not work in CPLEX. Can anyone help me with expressing what I want to here? I have tried various things now, but I don't seem to have the right ideas here...
Hi,
I'm currently having a hard time modeling a scheduling problem with CP Optimizer. The problem is the following:
I have multiple jobs and multiple machines in my environment. I created one interval decision variable array for the jobs and one optional decision variable array for the jobs to determine the machine they are assigned to.
Furthermore, for each machine, there's a sequence variable. N is a range for the jobs, M is the range for the machines. My code looks like this:
<pre class="javascript dw" dataeditorlang="js" datapbcklang="javascript" dir="ltr">dvar interval jobs[j in N] in 1..(maxint div 2)1 size 5;
dvar interval jobs_opt[i in M][j in N] optional in 1..(maxint div 2)1 size 5;
dvar sequence machines[i in M] in all(j in N) jobs_opt[i][j];
</pre>
Now here's my problem: For each job, there's a tool the job requires for processing. These tools have to be installed on the machine they are used on which requires a certain amount of time. I already have restrictions that represent the setup times that have to be considered if job j is processed before job k and they need different tools.
What I'm currently not able to add is the following: If the tool is used on machine 1 until 12:00, then the same tool can't be used at machine 2 at 12:01 because it has to be uninstalled at machine 1 and afterwards installed at machine 2. If that case occurs, I'd like to consider a 30minute delay between the processing of these jobs. So what I'd need is something like this:
Obviously, like this, the code does not work in CPLEX. Can anyone help me with expressing what I want to here? I have tried various things now, but I don't seem to have the right ideas here...
Okay, I think now I understand what my problem was  I added the line you proposed and everything works fine now.
I only have one question left: Why did I need to alter that tool constraint while
dvar sequence machines[i in M] in all(j in N) jobs_opt[i][j] types all(j in N)INTEGERTYPE_jobs[j];
works fine and doesn't require additional constraints in the all statement? Do I even need the to add the "types" statement here?
After all, I would like to thank you very much for your help and the advice  I would never have come this far all alone. The thing is that I originally wanted to implement the problem as an MIP. I tested multiple formulations but all of them required way too much computation time due to a huge number of Big M constraints in them. That's why I turned to Constraint Programming.
I had, to be honest, never worked with that before, and had to learn it all from scratch during the last weeks. Unfortunately, there's not exactly loads of material on this, I considered the IBM documentation, the CP tutorials and also found the slides you posted on slideshare very useful.
So again, thanks a lot for your help, and keep up the great work!
Re: CP Optimizer with setup times and tool switching
20180614T11:47:45Z
This is the accepted answer.
This is the accepted answer.
I think you need a second set of noOverlap constraints on the tools. Each tool is a unary resource so you cannot have two activities using the same tool running at the same time (that is why it is a noOverlap), and you will also have a transition matrix indexed by the machines to model the transport time from machine Mi to machine Mj.
So in your problem you should consider that you have two types of unary resources: the machines and the tools.
Re: CP Optimizer with setup times and tool switching
20180614T14:46:34Z
This is the accepted answer.
This is the accepted answer.
Hi,
first of all, thanks for your help on this! I added a counter for the number of different tools now, the creation of the transition matrix won't be a problem either.
But could you explain to me how you propose I consider the tools in my program? Should I add something like
dvar sequence tools[t in number_of_tools]
If yes, over what set of interval variables would I have to define this sequence?
Hi,
first of all, thanks for your help on this! I added a counter for the number of different tools now, the creation of the transition matrix won't be a problem either.
But could you explain to me how you propose I consider the tools in my program? Should I add something like
first of all, thanks for your help on this! I added a counter for the number of different tools now, the creation of the transition matrix won't be a problem either.
But could you explain to me how you propose I consider the tools in my program? Should I add something like
Yes, one sequence tools[t] for each tool t. And tools[t] is defined over all jobs_opt[i][j] of jobs j using tool t. And the type of interval variable jobs_opt[i][j] in the sequence is the index of the machine i.
Re: CP Optimizer with setup times and tool switching
20180614T16:23:21Z
This is the accepted answer.
This is the accepted answer.
Hi,
thanks again for your reply. I now added the following to my code:
tuple tripel { int a1; int a2; int a3; };
{tripel} setuptimes = {};
execute{
for(var j in N){
for(var k in N){
if(required_tool[j]==required_tool[k]){
setuptimes.add(j, k, 30);
}else{
setuptimes.add(j, k, 0);
}
}
}
}
and for the sequence variables:
dvar sequence tools[t in 1..number_of_tools] in all(i in M, j in N:required_tool[j]==t) jobs_opt[i][j];
then as a constraint I added
forall(t in 1..number_of_tools){
noOverlap(tools[t], setuptimes);
}
But this constraint doesn't seem right to me...I think what should work now is that all the jobs that need one certain tool t are included in the sequence variable tools. Still, the noOverlap constraint seems to be wrong because as far as I see, it forces a setup time of 30 minutes for every pair of jobs that requires the same tools, not only those pairs where the jobs need the same tools and are processed on different machines.
Do you have any idea how to fix this last issue? Obviously, I can't design the transition times to be 30 when the jobs are processed machines and require the same tool, and 0 else because which machine the jobs are processed on is determined in my model. So I don't really know how to deal with my problem here...
And could you explain to me what you mean with
"And the type of interval variable jobs_opt[i][j] in the sequence is the index of the machine i"
Unfortunately, I did not really get that
Hi,
thanks again for your reply. I now added the following to my code:
<pre class="javascript dw" dataeditorlang="js" datapbcklang="javascript" dir="ltr">tuple tripel { int a1; int a2; int a3; };
{tripel} setuptimes = {};
execute{
for(var j in N){
for(var k in N){
if(required_tool[j]==required_tool[k]){
setuptimes.add(j, k, 30);
}else{
setuptimes.add(j, k, 0);
}
}
}
}
</pre>
and for the sequence variables:
<pre class="javascript dw" dataeditorlang="js" datapbcklang="javascript" dir="ltr">dvar sequence tools[t in 1..number_of_tools] in all(i in M, j in N:required_tool[j]==t) jobs_opt[i][j];
</pre>
But this constraint doesn't seem right to me...I think what should work now is that all the jobs that need one certain tool t are included in the sequence variable tools. Still, the noOverlap constraint seems to be wrong because as far as I see, it forces a setup time of 30 minutes for every pair of jobs that requires the same tools, not only those pairs where the jobs need the same tools and are processed on different machines.
Do you have any idea how to fix this last issue? Obviously, I can't design the transition times to be 30 when the jobs are processed machines and require the same tool, and 0 else because which machine the jobs are processed on is determined in my model. So I don't really know how to deal with my problem here...
And could you explain to me what you mean with
"And the type of interval variable jobs_opt[i][j] in the sequence is the index of the machine i"
thanks again for your reply. I now added the following to my code:
<pre class="javascript dw" dataeditorlang="js" datapbcklang="javascript" dir="ltr">tuple tripel { int a1; int a2; int a3; };
{tripel} setuptimes = {};
execute{
for(var j in N){
for(var k in N){
if(required_tool[j]==required_tool[k]){
setuptimes.add(j, k, 30);
}else{
setuptimes.add(j, k, 0);
}
}
}
}
</pre>
and for the sequence variables:
<pre class="javascript dw" dataeditorlang="js" datapbcklang="javascript" dir="ltr">dvar sequence tools[t in 1..number_of_tools] in all(i in M, j in N:required_tool[j]==t) jobs_opt[i][j];
</pre>
But this constraint doesn't seem right to me...I think what should work now is that all the jobs that need one certain tool t are included in the sequence variable tools. Still, the noOverlap constraint seems to be wrong because as far as I see, it forces a setup time of 30 minutes for every pair of jobs that requires the same tools, not only those pairs where the jobs need the same tools and are processed on different machines.
Do you have any idea how to fix this last issue? Obviously, I can't design the transition times to be 30 when the jobs are processed machines and require the same tool, and 0 else because which machine the jobs are processed on is determined in my model. So I don't really know how to deal with my problem here...
And could you explain to me what you mean with
"And the type of interval variable jobs_opt[i][j] in the sequence is the index of the machine i"
dvar sequence tools[t in 1..number_of_tools] in all(i in M, j in N:required_tool[j]==t) jobs_opt[i][j];
noOverlap(tools[t], setuptimes);
The model cannot guess which index in the transition matrix is associated with an interval jobs_opt[i][j] in the sequence.
Each time you are using a transition distance in a noOverlap constraint, you need to associate a type in the sequence variable by doing something like:
dvar sequence SEQ in all(i in ...) INTERVAL[i] types all(i in ...) INTEGERTYPE[i];
the when you post a constraint noOverlap(SEQ,MATRIX), the transition time between INTERVAL[i] and INTERVAL[j] will be MATRIX[INTEGERTYPE[i]][INTEGERTYPE[j]]
So here in the noOverlap on the tools, the type should correspond to an index m of machine (the machine used by job j) and the matrix should give the time taken for moving the tool from a machine m to a machine m'.
Re: CP Optimizer with setup times and tool switching
20180615T10:30:55Z
This is the accepted answer.
This is the accepted answer.
Hi,
okay, thanks for your advice  I see that the part I didn't understand about your post was the one that would have helped me solve my problem.
I now added the following according to your post:
int INTEGERTYPE_jobs[N];
int INTEGERTYPE_machines[M];
execute{
for(var j=1; j<=number_of_jobs; j++){
INTEGERTYPE_jobs[j]=j;
}
for(var i=1; i<=number_of_machines; i++){
INTEGERTYPE_machines[i]=i;
}
}
dvar sequence machines[i in M] in all(j in N) jobs_opt[i][j] types all(j in N)INTEGERTYPE_jobs[j];
dvar sequence tools[t in 1..number_of_tools] in all(i in M, j in N:required_tool[j]==t) jobs_opt[i][j] types all(i in M) INTEGERTYPE_machines[i];
And I changed the definition of my transition matrix for the tools to match the time needed to dismount the tool on machine i and mount it on machine j.
Unfortunately, I am now getting the following errors:
Exception in presolve: Arrays 'IntervalVarArray_150' and 'IntArray_151' must have the same size in Interval Sequence Variable..
Exception in presolve: Arrays 'IntervalVarArray_154' and 'IntArray_155' must have the same size in Interval Sequence Variable..
I don't really see what went wrong here...did I get anything about your post wrong?
Hi,
okay, thanks for your advice  I see that the part I didn't understand about your post was the one that would have helped me solve my problem.
I now added the following according to your post:
<pre class="javascript dw" dataeditorlang="js" datapbcklang="javascript" dir="ltr">int INTEGERTYPE_jobs[N];
int INTEGERTYPE_machines[M];
execute{
for(var j=1; j<=number_of_jobs; j++){
INTEGERTYPE_jobs[j]=j;
}
for(var i=1; i<=number_of_machines; i++){
INTEGERTYPE_machines[i]=i;
}
}
dvar sequence machines[i in M] in all(j in N) jobs_opt[i][j] types all(j in N)INTEGERTYPE_jobs[j];
dvar sequence tools[t in 1..number_of_tools] in all(i in M, j in N:required_tool[j]==t) jobs_opt[i][j] types all(i in M) INTEGERTYPE_machines[i];
</pre>
And I changed the definition of my transition matrix for the tools to match the time needed to dismount the tool on machine i and mount it on machine j.
Unfortunately, I am now getting the following errors:
Exception in presolve: Arrays 'IntervalVarArray_150' and 'IntArray_151' must have the same size in Interval Sequence Variable..
Exception in presolve: Arrays 'IntervalVarArray_154' and 'IntArray_155' must have the same size in Interval Sequence Variable..
I don't really see what went wrong here...did I get anything about your post wrong?
okay, thanks for your advice  I see that the part I didn't understand about your post was the one that would have helped me solve my problem.
I now added the following according to your post:
<pre class="javascript dw" dataeditorlang="js" datapbcklang="javascript" dir="ltr">int INTEGERTYPE_jobs[N];
int INTEGERTYPE_machines[M];
execute{
for(var j=1; j<=number_of_jobs; j++){
INTEGERTYPE_jobs[j]=j;
}
for(var i=1; i<=number_of_machines; i++){
INTEGERTYPE_machines[i]=i;
}
}
dvar sequence machines[i in M] in all(j in N) jobs_opt[i][j] types all(j in N)INTEGERTYPE_jobs[j];
dvar sequence tools[t in 1..number_of_tools] in all(i in M, j in N:required_tool[j]==t) jobs_opt[i][j] types all(i in M) INTEGERTYPE_machines[i];
</pre>
And I changed the definition of my transition matrix for the tools to match the time needed to dismount the tool on machine i and mount it on machine j.
Unfortunately, I am now getting the following errors:
Exception in presolve: Arrays 'IntervalVarArray_150' and 'IntArray_151' must have the same size in Interval Sequence Variable..
Exception in presolve: Arrays 'IntervalVarArray_154' and 'IntArray_155' must have the same size in Interval Sequence Variable..
I don't really see what went wrong here...did I get anything about your post wrong?
When defining the sequence variable, in order to associate one integer type with one interval variables, the array of intervals and the array of types must have the same size.
You write:
dvar sequence tools[t in 1..number_of_tools] in all(i in M, j in N:required_tool[j]==t) jobs_opt[i][j] types all(i in M) INTEGERTYPE_machines[i];
The array of interval variable has a size "M * number of jobs requiring tool t" whereas the size of your array of types is M.
How do you want the model guess that an interval variable jobs_opt[i][j] is associated with its machine i ?
You need something like:
dvar sequence tools[t in 1..number_of_tools] in all(i in M, j in N:required_tool[j]==t) jobs_opt[i][j] types all(i in M, j in N:required_tool[j]==t) INTEGERTYPE_machines[i];
Re: CP Optimizer with setup times and tool switching
20180615T12:47:10Z
This is the accepted answer.
This is the accepted answer.
Okay, I think now I understand what my problem was  I added the line you proposed and everything works fine now.
I only have one question left: Why did I need to alter that tool constraint while
dvar sequence machines[i in M] in all(j in N) jobs_opt[i][j] types all(j in N)INTEGERTYPE_jobs[j];
works fine and doesn't require additional constraints in the all statement? Do I even need the to add the "types" statement here?
After all, I would like to thank you very much for your help and the advice  I would never have come this far all alone. The thing is that I originally wanted to implement the problem as an MIP. I tested multiple formulations but all of them required way too much computation time due to a huge number of Big M constraints in them. That's why I turned to Constraint Programming.
I had, to be honest, never worked with that before, and had to learn it all from scratch during the last weeks. Unfortunately, there's not exactly loads of material on this, I considered the IBM documentation, the CP tutorials and also found the slides you posted on slideshare very useful.
So again, thanks a lot for your help, and keep up the great work!
Okay, I think now I understand what my problem was  I added the line you proposed and everything works fine now.
I only have one question left: Why did I need to alter that tool constraint while
<pre class="javascript dw" dataeditorlang="js" datapbcklang="javascript" dir="ltr">dvar sequence machines[i in M] in all(j in N) jobs_opt[i][j] types all(j in N)INTEGERTYPE_jobs[j];</pre>
works fine and doesn't require additional constraints in the all statement? Do I even need the to add the "types" statement here?
After all, I would like to thank you very much for your help and the advice  I would never have come this far all alone. The thing is that I originally wanted to implement the problem as an MIP. I tested multiple formulations but all of them required way too much computation time due to a huge number of Big M constraints in them. That's why I turned to Constraint Programming.
I had, to be honest, never worked with that before, and had to learn it all from scratch during the last weeks. Unfortunately, there's not exactly loads of material on this, I considered the IBM documentation, the CP tutorials and also found the slides you posted on slideshare very useful.
So again, thanks a lot for your help, and keep up the great work!
Okay, I think now I understand what my problem was  I added the line you proposed and everything works fine now.
I only have one question left: Why did I need to alter that tool constraint while
<pre class="javascript dw" dataeditorlang="js" datapbcklang="javascript" dir="ltr">dvar sequence machines[i in M] in all(j in N) jobs_opt[i][j] types all(j in N)INTEGERTYPE_jobs[j];</pre>
works fine and doesn't require additional constraints in the all statement? Do I even need the to add the "types" statement here?
After all, I would like to thank you very much for your help and the advice  I would never have come this far all alone. The thing is that I originally wanted to implement the problem as an MIP. I tested multiple formulations but all of them required way too much computation time due to a huge number of Big M constraints in them. That's why I turned to Constraint Programming.
I had, to be honest, never worked with that before, and had to learn it all from scratch during the last weeks. Unfortunately, there's not exactly loads of material on this, I considered the IBM documentation, the CP tutorials and also found the slides you posted on slideshare very useful.
So again, thanks a lot for your help, and keep up the great work!