Originally posted by: PhilippeLaborie
Ok. That is what I guessed but I wanted to be sure.
In your model, nothing constrains the position of the maintenance activities with respect to the production activities.
So you could add a set of integer variable (one for each production activity) that counts the total processing time since last maintenance activity (variable ptCountAtEnd in the model below). The domain of these variables is in 0..maxpt where maxpt is the limit on the total processing time before doing a maintenance.
In the sequence, each of the n production activities have a type in 1..n whereas the maintenance activities have a type 0. The constraint that maintains the counters ptCountAtEnd is:
ptCountAtEnd[i] == ptCountAtEnd[typeOfPrev(seq,act[i],0)] + sizeOf(act[i]);
It says that the counter of processing time at the end of a production activity i is the value of the counter of the previous activity plus the size of the activity. But there is a small trick here: if the type of the previous activity is a maintenance (typeOfPrev=0), then the value of the counter is 0, that is why we add an index 0 in the array and post ptCountAtEnd[0]==0 for maintenance activities.
To speed-up the search, it may be useful to tell CP Optimizer to first focus on fixing the production activities, as the maintenance ones should be fixed by propagation as consequence. This can be done with a search phase. This gives the following model:
using CP;
int n = 100;
int maxpt = 20;
int maintdur = 10;
int pt[i in 1..n] = 1+rand(10); // Processing time for activity i
int m = n;
dvar interval act[i in 1..n] size pt[i]; // decision variables
dvar interval maint[j in 1..m] size maintdur;
dvar sequence seq in append(act, maint) types append(all(i in 1..n) i, all(j in 1..m) 0);
dvar int ptCountAtEnd[i in 0..n] in 0..maxpt;
execute {
var f = cp.factory;
cp.setSearchPhases(f.searchPhase(act));
}
minimize max(i in 1..n) endOf(act[i]);
subject to {
noOverlap(seq);
forall(j in 2..m) {
endBeforeStart(maint[j-1], maint[j], maxpt);
}
ptCountAtEnd[0]==0; // For maintenance activities
forall(i in 1..n) {
ptCountAtEnd[i] == ptCountAtEnd[typeOfPrev(seq,act[i],0)] + sizeOf(act[i]);
}
}
Now, you can also have a slightly more involved model that 'removes' the useless maintenance activities at the end of the schedule by having those activities optional. Only the first ones, that are required will be executed. The constraint typeOfNext(seq,maint[j],0,1)!=0 says that you cannot have two consecutive maintenance activities without any production in between and that the schedule cannot end with a maintenance activity.
using CP;
int n = 100;
int maxpt = 20;
int maintdur = 10;
int pt[i in 1..n] = 1+rand(10); // Processing time for activity i
int m = n;
dvar interval act[i in 1..n] size pt[i]; // decision variables
dvar interval maint[j in 1..m] optional size maintdur;
dvar sequence seq in append(act, maint) types append(all(i in 1..n) i, all(j in 1..m) 0);
dvar int ptCountAtEnd[i in 0..n] in 0..maxpt;
execute {
var f = cp.factory;
cp.setSearchPhases(f.searchPhase(act));
}
minimize max(i in 1..n) endOf(act[i]);
subject to {
noOverlap(seq);
forall(j in 2..m) {
endBeforeStart(maint[j-1], maint[j], maxpt);
presenceOf(maint[j]) => presenceOf(maint[j-1]);
typeOfNext(seq,maint[j],0,1) != 0;
}
ptCountAtEnd[0]==0; // For maintenance activities
forall(i in 1..n) {
ptCountAtEnd[i] == ptCountAtEnd[typeOfPrev(seq,act[i],0)] + sizeOf(act[i]);
}
}
Hope it helps,
Philippe
#DecisionOptimization#OPLusingCPOptimizer