Originally posted by: SystemAdmin

[deborah said:]

Hi!!
I have to solve a scheduling problem using two different approach: MP e CP, so I write two models. But I obtain two different solutions. I think that the problem is the implementation in CP, because I'm new in CP.

The model in MP is:
[hr]
dvar int W[0..nJobs][0..nJobs][0..mMachine]  in 0..1; //  W[i,j,m] = 1 if machine m run job j soon after job i  
dvar int R[0..nJobs]; //Delay of job j
dvar int t[0..nJobs]; //starting time of job j

minimize sum(j in 1..nJobs-1) (R[j]);

constraints{

   forall(j in 0..nJobs) R[j]>=0;  
   forall(j in 0..nJobs) t[j]>= Jobs[j].releaseData;  
   forall(j in 1..nJobs-1) R[j] >= t[j]+(sum(l in 0..nJobs-1 : l!=j)processamento[j] - Jobs[j].dueDate);  
   forall(m in 0..mMachine) sum(l in 1..nJobs) W[0,l,m] == 1;  
   forall(m in 0..mMachine) sum(j in 0..nJobs-1) W[j,nJobs,m] == 1;  
   forall(j in 1..nJobs-1) sum(m in 0..mMachine, l in 1..nJobs: l != j) W[j,l,m] == 1;    
   forall(j in 1..nJobs-1, m in 0..mMachine) sum(l in 1..nJobs: l != j) W[j,l,m]-sum(l in 0..nJobs-1: l !=j) W[l,j,m] == 0;  
   forall(l in 1..nJobs, j in 0..nJobs-1  : l!=j) (1- (sum(m in 0..mMachine)W[j,l,m]))*M + t[l] -  t[j]  >= (processamento[j] + s[j,l]);

}
/**********************************
// solution with objective 471
M 0: 4 2
M 1:
M 2:
M 3: 5 1 7 6
M 4: 3
M 5: 8
**********************************/
[hr]

The model in CP is:
[hr]
dvar interval tasks[i in 1..nJobs-1] in Jobs[i].releaseData..(maxint div 2)-1 size processamento[i];
dvar interval tasksOnMachines[k in 0..mMachine][i in 1..nJobs-1] optional;
dvar sequence machines[k in 0..mMachine] in all(i in 1..nJobs-1) tasksOnMachines[k][i];
dvar int R[1..nJobs-1];
 
minimize sum(j in 1..nJobs-1) (R[j]);     

constraints {

  forall(j in 1..nJobs-1) R[j]>=0;  
 forall(j in 1..nJobs-1) R[j] >= startOf(tasks[j])+(sum(l in 1..nJobs-1 : l!=j)processamento[j] - Jobs[j].dueDate);  
 forall(i in 1..nJobs-1) alternative(tasks[i], all(k in 0..mMachine) tasksOnMachines[k][i]); // Un task è assegnato ad una sola crane
 forall(k in 0..mMachine) noOverlap(machines[k]); // I task non si sovrappongono
 
}
/**********************************
// solution with objective 0
M 0:
M 1: 5
M 2:
M 3: 4 7
M 4: 3 6 2 8
M 5: 1
**********************************/
[hr]

What is my mistake???

Thanks in advance

Deborah
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[jfk said:]

sorry, I haven't looked at it in details, but if I just assume that you have 2 exactly the same goals with the same optimum value then isn't it possible that you have 2 different solutions? You could count down all the optimal solutions with one of the approaches (say with CP) and see if you could match the one found by the other (MP)...

cheers
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[phlab said:]

Hi Deborah,
In your code sample, some [i ] seem to be missing (it is probably because [i ] is a special instruction to format the post). Could you attach a more readable sample (you can add a space after the "i": [i ])? Furthermore, if the have the data that would be useful too.

By the way, this constraint is a little strange:

forall(j in 1..nJobs-1) R[j] >= t[j] + (sum(l in 0..nJobs-1 : l!=j) processamento[j] - Jobs[j].dueDate); 

Are you sure the last elements should be indexed by j and not l? What does it represent?

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[Didier Vidal said:]

In your code sample, some [i ] seem to be missing
The easiest way is to use the "Insert Code" icon (displayed as #) before entering code statements.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[deborah said:]

Hi!!

I review my code. I try to attach my models and .dat file, but I receive this message:

"The upload folder is full. Please try a smaller file and/or contact an administrator"... so :

DATA AND PREPROCESSING (this is the same in the models):
using CP;
int n = ...;
int nJobs = n-1;
assert{
nJobs>=0;
}

tuple job {
  int id;
  float releaseData;
  float dueDate;
  float XF;
  float XT;
  float YF;
  float YT;
}

job Jobs[0..nJobs]=...;

int m = ...;
int mMachine = m-1;
assert{
mMachine>=0;
}

tuple machine {
  int id;
  float speed;
  float empty_speed;
}

machine Machines[0..mMachine]=...;

float processamento[0..nJobs];
execute{
for (var j = 0; j <= nJobs; j++) <br /> for(var  sc= 0; sc <= mMachine; sc++){ <br />         if(j==0 || j==nJobs)
        processamento[j] = 0;
        else{
        var handling1 = Jobs[j].XT - Jobs[j].XF;
if(handling1 < 0)<br /> handling1 = - handling1;
var handling2 = Jobs[j].YT - Jobs[j].YF;
if(handling2 < 0)<br /> handling2 = - handling2;
var handling = (handling1 + handling2)/1;
        processamento[j] = handling;
}
}
writeln("PROCESSAMENTO : "+processamento);
}

float s[0..nJobs][0..nJobs]; //tempi di set-up
execute{
for (var j = 0; j <= nJobs; j++) <br /> for (var l = 0; l <= nJobs; l++) <br /> for(var  sc= 0; sc < mMachine; sc++) {<br /> if(j == 0 || l == nJobs || l == 0 || j == nJobs || l == j)
s[j][l] = 0;
else{
    var deltaX = Jobs[j].XF - Jobs[j].XT;
    if(deltaX < 0)<br />     deltaX = - deltaX;
var deltaY = Jobs[l].YF - Jobs[l].YT;
if(deltaY < 0)<br /> deltaY = - deltaY;
var setup = deltaX + deltaY;
s[j][l] = setup/1;
}
}
writeln("SET UP : "+s);
}


int minMachineSPEED;
execute{
    minMachineSPEED = 0;
var minSPEED = Machines[minMachineSPEED].speed;
for(var  sc= 1; sc <= mMachine; sc++){<br /> var speed = Machines[sc].speed;
if(speed < minSPEED){<br /> minSPEED = speed;
minMachineSPEED = sc;
}
}
}



MP model:
float M ;
execute{
M+=Number.MAX_VALUE;
}

dvar int W[0..nJobs][0..nJobs][0..mMachine]  in 0..1; //W[j][l][m]=1 if the machine 'k' run job 'l' soon after job 'j', otherwise W[j][l][m]=0.    
dvar int R[0..nJobs]; //Delay of job j
dvar int t[0..nJobs]; //Start time of job j 
minimize sum(j in 1..nJobs-1) (R[j]);
constraints{
        forall(j in 0..nJobs) R[j]>=0;
forall(j in 0..nJobs) t[j]>= Jobs[j].releaseData;
forall(j in 1..nJobs-1) R[j] >= t[j] + processamento[j] - Jobs[j].dueDate;   
forall(m in 0..mMachine) sum(l in 1..nJobs) W[0,l,m] == 1; 
forall(m in 0..mMachine) sum(j in 0..nJobs-1) W[j,nJobs,m] == 1; 
forall(j in 1..nJobs-1) sum(m in 0..mMachine, l in 1..nJobs: l != j) W[j,l,m] == 1;   
forall(j in 1..nJobs-1, m in 0..mMachine)    sum(l in 1..nJobs: l != j) W[j,l,m]-sum(l in 0..nJobs-1: l !=j) W[l,j,m] == 0; 
forall(l in 1..nJobs, j in 0..nJobs-1  : l!=j) (1- (sum(m in 0..mMachine)W[j,l,m]))*M + t[l] -  t[j]  >= processamento[j] + s[j,l];
}



CP model:
dvar int R[1..nJobs-1]; //Delay of job j
dvar interval tasks[i in 1..nJobs-1] in Jobs[i].releaseData..(maxint div 2)-1  size processamento[i];
dvar interval tasksOnMachines[k in 0..mMachine][i in 1..nJobs-1] optional;
dvar sequence machines[k in 0..mMachine] in all(i in 1..nJobs-1) tasksOnMachines[k][i] types all(i in 1..nJobs-1) i;
tuple triplet { int loc1; int loc2; int value; };
{triplet} transitionTimes = { <i,j, s&#91;i&#93;&#91;j&#93;> | i in 1..nJobs-1, j in 1..nJobs-1};
minimize sum(j in 1..nJobs-1) (R[j]); 
constraints {
  forall(i in 1..nJobs-1) alternative(tasks[i], all(k in 0..mMachine) tasksOnMachines[k][i]);
  forall(k in 0..mMachine) noOverlap(machines[k],transitionTimes);
  forall(j in 1..nJobs-1) R[j]>=0;   
  forall(j in 1..nJobs-1) R[j] >= endOf(tasks[j]) - Jobs[j].dueDate;
}



.dat file:
n=17;
Jobs = #[
0: <0 0 0 0 0 0 0>,
1: <1 2171 168 2359 377 120 600>,
        2: <2 2171 168 2459 358 240 720>,
        3: <3 2171 168 2380 255 360 840>,
        4: <4 2171 168 2363 383 480 960>,
        5: <5 2171 168 2483 346 600 1080>,
        6: <6 2171 168 2483 346 720 1200>
        7: <7 2171&nbsp; 168&nbsp; 2342&nbsp; 267 840&nbsp; 1320>
        8: <8 2171&nbsp; 168 2371&nbsp; 218 960&nbsp; 1440 >
        9: <9 2171&nbsp; 168 2342&nbsp; 267 1080&nbsp; 1560&nbsp; >
        10: <10 2516&nbsp; 239 2415&nbsp; 170 0&nbsp; 120 >
        11: <11 2545&nbsp; 215 2415&nbsp; 170 0&nbsp; 240 >
        12: <12 2305&nbsp; 301 2415&nbsp; 170 0&nbsp; 360&nbsp; >
        13: <13 2686&nbsp; 276 2415&nbsp; 170 0&nbsp; 480 >
        14: <14 1775&nbsp; 641 2415&nbsp; 170 0&nbsp; 600 >
        15: <15 2342&nbsp; 267 2415&nbsp; 170 120&nbsp; 720>
        16: <16 0 0 0 0 0 0>
    ]#;
m= 8;   
Machines = #[
    0: <0 170 1>,
    1: <1 170 1>,
    2: <2 252 1>,
    3: <3 170 1 >,
    4: <4 170 1 >,
    5: <5 408 1 >,
    6: <6 334 1 >,
    7: <7 280 1 >
]#;


Thanks to all

deborah
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[phlab said:]

Deborah,
Something seems to be wrong in your MP model. I didn't look the model in detail but in the solution, all jobs start at their release date and, for instance there are more that 8 jobs starting at date 2171 whereas only 8 machines are available.

// solution (optimal) with objective 69212
R = ...;
t = [0 2171 2171 2171 2171 2171 2171 2171 2171 2171 2516 2545 2305 2686 1775 2342 0];

Something is probably wrong with the way you model the fact each machine can only process one job at a time.

As far as the CPO model is concerned, you could slightly improve it by avoiding the decision variables on the tardiness and directly use an integer expression instead:

dvar interval tasks[i in 1..nJobs-1] in ftoi(Jobs[i].releaseData)..(maxint div 2)-1  size ftoi(processamento[i]);
dvar interval tasksOnMachines[k in 0..mMachine][i in 1..nJobs-1] optional;
dvar sequence machines[k in 0..mMachine] in all(i in 1..nJobs-1) tasksOnMachines[k][i] types all(i in 1..nJobs-1) i;
tuple triplet { int loc1; int loc2; int value; };
{triplet} transitionTimes = { <i,j, ftoi(s&#91;i&#93;&#91;j&#93;)> | i in 1..nJobs-1, j in 1..nJobs-1};

minimize sum(j in 1..nJobs-1) maxl(0, endOf(tasks[j]) - Jobs[j].dueDate); 
constraints {
  forall(i in 1..nJobs-1) alternative(tasks[i], all(k in 0..mMachine) tasksOnMachines[k][i]);
  forall(k in 0..mMachine) noOverlap(machines[k],transitionTimes);
}


That will be more efficient (but on the small data you provide, it doesn't change the solution).

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[deborah said:]

Hi Philippe,

thank you for your support.

When I run MP model, I obtain:

// solution with objective 69218
R = [1249383660 4465 4584 4608 4464 4622 4620
        4559 4638 4558 4642 4815 4609 5135 3979 4920 781701271];
t = [0 2171 2171 2171 2172 2173 2171 2172 2173 2171 2516 2545 2305 2686 1775
        2342 1300057889];

I don't know why you obtain a different solution!!

However, my preoblem is CP model, because I don't obtain a solution in a reasonable time...
Yesterday I abort the process after 2 hours, the solution is 102,683.
Why???

Deborah
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[phlab said:]

But your solution also does not seem to be feasible:

t = [0 2171 2171 2171 2172 2173 2171 2172 2173 2171 2516 2545 2305 2686 1775 2342 1300057889];

The processing time of the tasks is as follows:

[0 2462 2581 2605 2460 2617 2617 2555 2633 2555 2365 2485 2605 2725 2845 2845 0]

So there seem to be more than 8 machines used at, say date 2173.

About the results with CP Optimizer: on this instance, the engine is not able to prove optimality. It finds a solution with objective value 102,683 but cannot improve it anymore. You should use a time limit (or any other limit) to have the engine stop and return the best solution it has found so far.

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[deborah said:]

Ok, I review my MP model...

So is my CP model correct? Does it rappresents the same problem of my MP?? I don't know if I use correctly CP construct for the scheduling Problem.

Thank you very much.

Deborah
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[phlab said:]

I slightly change the MP model to:

float M  = 1e5; // BigM (! currently this value depends on the instance !)
dvar int X[1..nJobs-1][0..mMachine]  in 0..1;
// X[j][m]: If job 'j' is allocated to machine 'm'
dvar int W[1..nJobs-1][1..nJobs-1][0..mMachine]  in 0..1;
//W[l][j][m]=1 if the machine 'm' run both jobs 'l' and 'j' and 'l' is executed before 'j'.    
dvar int R[0..nJobs]; // Delay of job j
dvar int t[0..nJobs]; // Start time of job j 
minimize sum(j in 1..nJobs-1) (R[j]);
constraints{
  forall(j in 0..nJobs) R[j]>=0;
  forall(j in 0..nJobs) t[j]>= Jobs[j].releaseData;
  forall(j in 1..nJobs-1) R[j] >= t[j] + processamento[j] - Jobs[j].dueDate;   
  forall(j in 1..nJobs-1) sum(m in 0..mMachine) X[j][m]==1;
  forall(m in 0..mMachine, l in 1..nJobs-1, j in 1..nJobs-1  : l<j) {<br />    // Cannot have l before j and j before l on the same machine
    W[j][l][m] + W[l][j][m] <= 1;<br />  }
  forall(m in 0..mMachine, l in 1..nJobs-1, j in 1..nJobs-1  : l<j) {<br />    // Two jobs executed on the same machine must be ordered
W[j][l][m] + W[l][j][m] >= 1 - (1-X[j][m]) - (1-X[l][m]);
  }
  forall(m in 0..mMachine, l in 1..nJobs-1, j in 1..nJobs-1  : l!=j) {
    // Delay between two consecutive jobs (on the same machine)
t[j] + processamento[j] + s[j,l] <= t[l] + (1- W[j][l][m])*M;<br />  }
}

This model is equivalent to the CP one. And it also finds a solution at 102683, and can't prove optimality neither. Note that you probably can improve this MP model.

Your CP model is equivalent to this MP model. But you can consider my suggestion to improve it by using an integer expression for the tardiness cost, it will probably allow the model to scale better to larger instances.

Philippe


#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[deborah said:]

Hi Philipe,
your model is perfect.
I review my MP model, maybe I find the error.

forall(l in 1..nJobs, j in 0..nJobs-1  : l!=j)
((1- (sum(m in 0..mMachine)W[j,l,m]))*M ) + t[l] - t[j] >= processamento[j] + s[j,l];


This constraint isn't respected.

I wanted to ask you if there is an ather way to express that the starting time of a job [i]l[/i] has to depend from the sum of starting time, processing time, transition time(between job [i]j[/i] and job [i]l[/i]) of job [i]j[/i], if and only if the job [i]l[/i] is performed soon after job [i]j[/i]...
Now I think that I will use your model, adding other constraint on it.

Could you recommend me some books where I can learn how to use CP and MP? What do you have studied to become so good in CP and MP?

Thank you very much. 

Deborah
#DecisionOptimization
#OPLusingCPOptimizer