Topic
  • 4 replies
  • Latest Post - ‏2014-01-06T10:23:03Z by PhilippeLaborie
qtbgo
qtbgo
134 Posts

Pinned topic how to model this constraint in parellel machine scheduling

‏2014-01-03T00:25:54Z |

Hi, in a simple parellel machine scheduling problem, we have n types of jobs and m machines. Each type of jobs should be processed only by one machine and should be processed continuously. How to model this situation?

One way is to consider all jobs of the same type as a big job, but I would not adopt this, because I will use individual job later. 

Thanks in advance.

  • qtbgo
    qtbgo
    134 Posts
    ACCEPTED ANSWER

    Re: how to model this constraint in parellel machine scheduling

    ‏2014-01-04T02:28:33Z  
    • GGR
    • ‏2014-01-03T17:45:56Z

    Hi

    If I understand well your problem: You have to define one interval variable per type

    int n = ... // number of type

    tuple operation { int ptime; int type}

    {Operation} operations = ... // the set of opertrions

    dvar interval opers[o in operations} size o.ptime;

    dvar interval types[t in i..n] size sum (o in operations: o.type = t) o.ptime;

    and add the constraints

    forall (t in 1..n)

      span(types[t], all (o in operations: o.type = t) opers[o]);

     

    Then use the interval variable types to model the multi parallel machine problem

     

    ope that helps

     

    Thank you for your help, GGR.

  • PhilippeLaborie
    PhilippeLaborie
    68 Posts
    ACCEPTED ANSWER

    Re: how to model this constraint in parellel machine scheduling

    ‏2014-01-06T10:23:03Z  
    • qtbgo
    • ‏2014-01-06T09:56:27Z

    Dear GGR, Could you tell me why there is no solution for the following simple model:

    using CP;

    int n = 3;
    int b = 10;
    int nQC = 2;
    int ScheduleLength = 1000;
    int l[1..n] =  [1,2,3];

    dvar interval opt_z1[ i in 1..n+nQC][k in 1..nQC] optional in 0..ScheduleLength;

    dvar interval y[j in 1..b]  in 0..ScheduleLength ;
    dvar interval opt_y[j in 1..b][k in 1..nQC] optional in 0..ScheduleLength;

     

    minimize max(j in 1..b)endOf(y[j]);

    subject to {

     forall (j in 1..b, k in 1..nQC)
       span(opt_y[j][k], all (i in 1..n: l[i] == j ) opt_z1[i][k]);   //1

     forall(j in 1..b)
       alternative(y[j], all(k in 1..nQC ) opt_y[j][k]);  //2
     
       
    }

    Hello,

    If you label the constraints in the model:

    subject to {
     forall (j in 1..b, k in 1..nQC)
       ct1: span(opt_y[j][k], all (i in 1..n: l[i] == j ) opt_z1[i][k]);   //1
     forall(j in 1..b)
       ct2: alternative(y[j], all(k in 1..nQC ) opt_y[j][k]);  //2
    }
    

    The conflict refiner of CP Optimizer tells that a minimal conflicting subset of constraints in the model is: { ct2[4], ct1[4][1], ct1[4][2] }

    So :

    ct2[4]:    alternative(y[4], { opt_y[4][1], opt_y[4][2] });
    ct1[4][1]: span(opt_y[4][1], {});
    ct1[4][2]: span(opt_y[4][2], {});
    

    Indeed, because the set of the spanned intervals is empty, interval variables opt_y[4][1] and opt_y[4][2] are necessarily absent. But this is incompatible with the alternative constraint that states that (because y[4] is not optional), one and only one among opt_y[4][1] and opt_y[4][2] should be present.

    Philippe

     

     

     

  • GGR
    GGR
    77 Posts

    Re: how to model this constraint in parellel machine scheduling

    ‏2014-01-03T17:45:56Z  

    Hi

    If I understand well your problem: You have to define one interval variable per type

    int n = ... // number of type

    tuple operation { int ptime; int type}

    {Operation} operations = ... // the set of opertrions

    dvar interval opers[o in operations} size o.ptime;

    dvar interval types[t in i..n] size sum (o in operations: o.type = t) o.ptime;

    and add the constraints

    forall (t in 1..n)

      span(types[t], all (o in operations: o.type = t) opers[o]);

     

    Then use the interval variable types to model the multi parallel machine problem

     

    ope that helps

     

  • qtbgo
    qtbgo
    134 Posts

    Re: how to model this constraint in parellel machine scheduling

    ‏2014-01-04T02:28:33Z  
    • GGR
    • ‏2014-01-03T17:45:56Z

    Hi

    If I understand well your problem: You have to define one interval variable per type

    int n = ... // number of type

    tuple operation { int ptime; int type}

    {Operation} operations = ... // the set of opertrions

    dvar interval opers[o in operations} size o.ptime;

    dvar interval types[t in i..n] size sum (o in operations: o.type = t) o.ptime;

    and add the constraints

    forall (t in 1..n)

      span(types[t], all (o in operations: o.type = t) opers[o]);

     

    Then use the interval variable types to model the multi parallel machine problem

     

    ope that helps

     

    Thank you for your help, GGR.

  • qtbgo
    qtbgo
    134 Posts

    Re: how to model this constraint in parellel machine scheduling

    ‏2014-01-06T09:56:27Z  
    • GGR
    • ‏2014-01-03T17:45:56Z

    Hi

    If I understand well your problem: You have to define one interval variable per type

    int n = ... // number of type

    tuple operation { int ptime; int type}

    {Operation} operations = ... // the set of opertrions

    dvar interval opers[o in operations} size o.ptime;

    dvar interval types[t in i..n] size sum (o in operations: o.type = t) o.ptime;

    and add the constraints

    forall (t in 1..n)

      span(types[t], all (o in operations: o.type = t) opers[o]);

     

    Then use the interval variable types to model the multi parallel machine problem

     

    ope that helps

     

    Dear GGR, Could you tell me why there is no solution for the following simple model:

    using CP;

    int n = 3;
    int b = 10;
    int nQC = 2;
    int ScheduleLength = 1000;
    int l[1..n] =  [1,2,3];

    dvar interval opt_z1[ i in 1..n+nQC][k in 1..nQC] optional in 0..ScheduleLength;

    dvar interval y[j in 1..b]  in 0..ScheduleLength ;
    dvar interval opt_y[j in 1..b][k in 1..nQC] optional in 0..ScheduleLength;

     

    minimize max(j in 1..b)endOf(y[j]);

    subject to {

     forall (j in 1..b, k in 1..nQC)
       span(opt_y[j][k], all (i in 1..n: l[i] == j ) opt_z1[i][k]);   //1

     forall(j in 1..b)
       alternative(y[j], all(k in 1..nQC ) opt_y[j][k]);  //2
     
       
    }

  • PhilippeLaborie
    PhilippeLaborie
    68 Posts

    Re: how to model this constraint in parellel machine scheduling

    ‏2014-01-06T10:23:03Z  
    • qtbgo
    • ‏2014-01-06T09:56:27Z

    Dear GGR, Could you tell me why there is no solution for the following simple model:

    using CP;

    int n = 3;
    int b = 10;
    int nQC = 2;
    int ScheduleLength = 1000;
    int l[1..n] =  [1,2,3];

    dvar interval opt_z1[ i in 1..n+nQC][k in 1..nQC] optional in 0..ScheduleLength;

    dvar interval y[j in 1..b]  in 0..ScheduleLength ;
    dvar interval opt_y[j in 1..b][k in 1..nQC] optional in 0..ScheduleLength;

     

    minimize max(j in 1..b)endOf(y[j]);

    subject to {

     forall (j in 1..b, k in 1..nQC)
       span(opt_y[j][k], all (i in 1..n: l[i] == j ) opt_z1[i][k]);   //1

     forall(j in 1..b)
       alternative(y[j], all(k in 1..nQC ) opt_y[j][k]);  //2
     
       
    }

    Hello,

    If you label the constraints in the model:

    subject to {
     forall (j in 1..b, k in 1..nQC)
       ct1: span(opt_y[j][k], all (i in 1..n: l[i] == j ) opt_z1[i][k]);   //1
     forall(j in 1..b)
       ct2: alternative(y[j], all(k in 1..nQC ) opt_y[j][k]);  //2
    }
    

    The conflict refiner of CP Optimizer tells that a minimal conflicting subset of constraints in the model is: { ct2[4], ct1[4][1], ct1[4][2] }

    So :

    ct2[4]:    alternative(y[4], { opt_y[4][1], opt_y[4][2] });
    ct1[4][1]: span(opt_y[4][1], {});
    ct1[4][2]: span(opt_y[4][2], {});
    

    Indeed, because the set of the spanned intervals is empty, interval variables opt_y[4][1] and opt_y[4][2] are necessarily absent. But this is incompatible with the alternative constraint that states that (because y[4] is not optional), one and only one among opt_y[4][1] and opt_y[4][2] should be present.

    Philippe