Search code examples
schedulingcplexoplmixed-integer-programming

How to write sequence by sequence constraints for scheduling


Now, I tried to add EQ7: a new constraint that make every start_pour[k][j] differ from others start_pour[k][j] that equal to site_process_time[c] to a runnable model. It showed a relaxed solution that = no feasible solution. How do i write this constraint ? Thank you.

 EQ7 :
 forall(c in customer)
   sum(k in truck, j in job)
      (start_pour[k][j] + site_process_time[c] + (M*(1-x[c][k][j]))) <= 
   sum(k in truck, j in job)
      (start_pour[k][j] + (M*(1-x[c][k][j])));

.MOD

 int c =...;
 int k =...;
 int j =...;

 range customer     =   1..c;
 range truck        =   1..k;
 range job          =   1..j;


 float demand[customer]=...;
 float travel[customer]=...;
 float plant_process_time[customer]=...; 
 float site_process_time[customer]=...; 

 float capacity[truck]=...;

 int M=...;


 dvar int+ start_load[truck][job];
 dvar int+ start_pour[truck][job];

 dvar boolean x[customer][truck][job];
 dvar boolean y[customer];

 /***************************************/

 dexpr float Travel_Cost =  sum(c in customer, k in truck, j in job)
                              x[c][k][j];

 dexpr float Penalty_Cost = sum(c in customer)
                              M*y[c];

 minimize   Travel_Cost  + Penalty_Cost;

 /***************************************/

 subject to { 

 EQ2 : //Assignment
 forall(k in truck, j in job)
   sum(c in customer)
     x[c][k][j] <= 1 ;


 EQ3 : //Precedence
 forall(k in truck, j in job : j > 1)
   sum(c in customer)
     x[c][k][j] <=
   sum(c in customer)
     x[c][k][j-1];

 EQ4 : //Demand <= Supply
 forall(c in customer)
   sum(k in truck, j in job)
     x[c][k][j] * capacity[k] >= demand[c] * (1-y[c]);


 EQ5 : //Job-Time Sequencing;
 forall(c in customer, k in truck, j in job)
   start_load[k][j] + plant_process_time[c] + travel[c] <= start_pour[k][j] + (M*(1-x[c][k][j-1]));


 EQ6 : //Job-Time Sequencing;
 forall(c in customer, k in truck, j in job: (j-1) in job)
   start_pour[k][j-1] + site_process_time[c] + travel[c] <= start_load[k][j]+ (M*(1-x[c][k][j-1]));

 }

.DAT

 c = 2;
 k = 2;
 j = 5;

 demand = [10 30];
 travel = [5 10];
 plant_process_time = [1 1];
 site_process_time = [2 2];

 capacity = [4 5];

 M= 100000;

Solution

  • To make sur model work you need at least to change

    EQ5 : //Job-Time Sequencing;
     forall(c in customer, k in truck, j in job)
       start_load[k][j] + plant_process_time[c] + travel[c] <= start_pour[k][j] + (M*(1-x[c][k][j-1]));
    

    into

    EQ5 : //Job-Time Sequencing;
     forall(c in customer, k in truck, j in job:(j-1) in job)
       start_load[k][j] + plant_process_time[c] + travel[c] <= start_pour[k][j] + (M*(1-x[c][k][j-1]));
    

    Then you could use logical constraints instead of big M

    EQ5 : //Job-Time Sequencing;
     forall(c in customer, k in truck, j in job:(j-1) in job)
    (1==x[c][k][j-1] ) => (start_load[k][j] + plant_process_time[c] + travel[c] <= start_pour[k][j]);
    

    For EQ7 you could start with

    EQ7 :
     forall(c in customer)
       forall(ordered k,k2 in truck, ordered  j,j2 in job)
    
          start_pour[k][j] != start_pour[k2][j2];
    

    or even

        EQ7 :
     forall(c in customer)
       forall(ordered k,k2 in truck, ordered  j,j2 in job)
    
         ((1==x[c][k][j] ) && (1==x[c][k2][j2]))=> (abs(start_pour[k][j] -start_pour[k2][j2]) >=plant_process_time[c]);
    

    if you want to take process time into account

    And I would suggest you to have a look at CPOptimizer within CPLEX since that's very good for scheduling.