Topic
  • 10 replies
  • Latest Post - ‏2018-06-15T16:28:49Z by Avadrus
Avadrus
Avadrus
6 Posts

Pinned topic CP Optimizer with setup times and tool switching

‏2018-06-14T10:42:17Z |

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

  • PhilippeLaborie
    PhilippeLaborie
    162 Posts
    ACCEPTED ANSWER

    Re: CP Optimizer with setup times and tool switching

    ‏2018-06-15T13:30:39Z  
    • Avadrus
    • ‏2018-06-15T12:47:10Z

    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!

     

    It works here because the arrays of intervals and types were already indexed in the same way:

    dvar sequence machines[i in M] in all(j in N) jobs_opt[i][j] types all(j in N) INTEGERTYPE_jobs[j];

     

    And interval jobs_opt[i][j] corresponds to type INTEGERTYPE_jobs[j] ...

     

     

  • PhilippeLaborie
    PhilippeLaborie
    162 Posts

    Re: CP Optimizer with setup times and tool switching

    ‏2018-06-14T11:47:45Z  

    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.

    Philippe

     

  • Avadrus
    Avadrus
    6 Posts

    Re: CP Optimizer with setup times and tool switching

    ‏2018-06-14T14:46:34Z  

    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?

  • PhilippeLaborie
    PhilippeLaborie
    162 Posts

    Re: CP Optimizer with setup times and tool switching

    ‏2018-06-14T15:35:21Z  
    • Avadrus
    • ‏2018-06-14T14:46:34Z

    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

    <pre class="javascript dw" data-editor-lang="js" data-pbcklang="javascript" dir="ltr">dvar sequence tools[t in number_of_tools] </pre>

    If yes, over what set of interval variables would I have to define this sequence?

    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. 

  • Avadrus
    Avadrus
    6 Posts

    Re: CP Optimizer with setup times and tool switching

    ‏2018-06-14T16:23:21Z  

    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

    Updated on 2018-06-14T16:25:40Z at 2018-06-14T16:25:40Z by Avadrus
  • PhilippeLaborie
    PhilippeLaborie
    162 Posts

    Re: CP Optimizer with setup times and tool switching

    ‏2018-06-15T06:50:43Z  
    • Avadrus
    • ‏2018-06-14T16:23:21Z

    Hi,

    thanks again for your reply. I now added the following to my code:

    <pre class="javascript dw" data-editor-lang="js" data-pbcklang="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" data-editor-lang="js" data-pbcklang="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>

    then as a constraint I added

    <pre class="javascript dw" data-editor-lang="js" data-pbcklang="javascript" dir="ltr"> forall(t in 1..number_of_tools){ noOverlap(tools[t], setuptimes); } </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"

    Unfortunately, I did not really get that

    When you are using a sequence like this:

     

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

     


     

  • Avadrus
    Avadrus
    6 Posts

    Re: CP Optimizer with setup times and tool switching

    ‏2018-06-15T10:30:55Z  

    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?

  • PhilippeLaborie
    PhilippeLaborie
    162 Posts

    Re: CP Optimizer with setup times and tool switching

    ‏2018-06-15T11:39:16Z  
    • Avadrus
    • ‏2018-06-15T10:30:55Z

    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" data-editor-lang="js" data-pbcklang="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];

     

  • Avadrus
    Avadrus
    6 Posts

    Re: CP Optimizer with setup times and tool switching

    ‏2018-06-15T12:47:10Z  

    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!

     

  • PhilippeLaborie
    PhilippeLaborie
    162 Posts

    Re: CP Optimizer with setup times and tool switching

    ‏2018-06-15T13:30:39Z  
    • Avadrus
    • ‏2018-06-15T12:47:10Z

    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" data-editor-lang="js" data-pbcklang="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!

     

    It works here because the arrays of intervals and types were already indexed in the same way:

    dvar sequence machines[i in M] in all(j in N) jobs_opt[i][j] types all(j in N) INTEGERTYPE_jobs[j];

     

    And interval jobs_opt[i][j] corresponds to type INTEGERTYPE_jobs[j] ...

     

     

  • Avadrus
    Avadrus
    6 Posts

    Re: CP Optimizer with setup times and tool switching

    ‏2018-06-15T16:28:49Z  

    Okay, I think I now understand how this whole noOverlap constraint works together with the sequence variables - thanks a lot for your help!