Originally posted by: SystemAdmin
[pvilim said:]
Hello.
Currently, preemptive task do not have direct support in CP-Optimizer. However you can still model it for example in the following way:
[tt]
using CP;
// Total duration of the preemptive task:
int totalDur = 100;
// Maximum number of pieces into which the task can be split:
int maxPieces = 5;
dvar interval pieces[1..maxPieces] optional size 1..totalDur;
constraints {
// At least the first piece must be present:
presenceOf(pieces[1]);
// Minimum delay between two pieces must be at least 1:
forall(j in 1..maxPieces-1)
endBeforeStart(pieces[j], pieces[j+1], 1);
// If piece j+1 is present then piece j must be present too:
forall(j in 2..maxPieces-1)
presenceOf(pieces[j+1]) => presenceOf(pieces[j]);
// Total duration of the chain must be totalDur:
(sum(j in 1..maxPieces) sizeOf(pieces[j])) == totalDur;
}
[/tt]
The idea is to replace a preemptive task by a chain of non-preemptive tasks, maximum number of preemptions is limited by maxPieces parameter. Each piece has variable size, minimum size for each piece is 1. Total size of all pieces is constrained to be totalDur. Minimum delay between pieces is 1 (otherwise it would not be a real preemption).
The tricky part is to handle cases when number of preemptions is lower than maximum, i.e. when we need less than maxPieces to model the preemptive task. For this purpose all but the first piece are declared optional. This way it is possible that, for example, only 3 pieces are used (are present in the solution) and the other two are absent. To break symmetries, in this case we want only the first three pieces to be present and [tt]pieces[4][/tt] and [tt]pieces[5][/tt] to be absent. This is done by constraints [tt]presenceOf(pieces[j+1]) => presenceOf(pieces[j])[/tt].
Start time of the preemptive task is equivalent to [tt]startOf(pieces[1])[/tt]. Span constraint you mentioned may help you to find the end time of the last executed piece:
[tt]
dvar interval cover;
constraints {
...
span(cover, pieces);
}
[/tt]
However, unless you are going to use interval [tt]cover[/tt] in another constraint, it is more effective to find end time during post processing of the solution.
Finally, if such preemptive task requires (for example) a cumulative resource, then in the model all its pieces should require this resource.
One more note: If you know in advance when preemption occurs (for example there's no work during weekends) then you may consider to use also intensity function on the interval. It is much more effective but it is more limited because noOverlap and cumul constraints are not affected by intensity function declared on intervals.
I hope this helps, Petr
#DecisionOptimization#OPLusingCPOptimizer