How to write sequence by sequence constraints for scheduling

Question

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;

Alex Fleischer · Accepted Answer · 2020-01-23 15:34:34Z

1

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.

edited Jan 23, 2020 at 15:34

answered Jan 23, 2020 at 13:04

Alex Fleischer

10.3k2 gold badges14 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Natdanai I. Over a year ago

1) From the new EQ7 , how do i make start_pour[k][j] differ from start_pour[k2][j2] about plant_process_time[c] it can not just add +plant_process_time[c] into constraint. 2) And where I can find more tutorial of scheduling with CPLEX or CPO. Thank you.

Alex Fleischer Over a year ago

I updated the model. And for more about scheduling see ibm.com/support/knowledgecenter/SSSA5P_12.8.0/…

Collectives™ on Stack Overflow

How to write sequence by sequence constraints for scheduling

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related