Originally posted by: SystemAdmin
[phlab said:]
I think you cannot directly model your transition time using the notion of transition distance of the noOverlap constraint in OPL because your transition time does not only depend on some interval types on the sequence.
There are two possibilities: (1) either you simplify the transition time further on so that it can be modeled in OPL without creating new decision variables in your problem or (2) you model it exactly but that will imply creating a large number of additional interval variables (quadratic with the number of intervals on the machines!). I will try to sketch the two approaches.
1. Simplifying the transition time.
For a given pair (task1,window1), (task2,window2) on a machine, I'll denote tt(t1,t2) the transition time function computed using your description where t1 and t2 are respectively the start values of task1 and task2 in their window.
And I will denote window1=[sw1,ew1], window2=[sw2,ew2].
A few ideas:
- for a given pair (task1,window1), (task2,window2) on a machine, you could pre-compute the minimal value of the minimal delay d12 that must elapse between the end of task 1 and the start of task 2 if they are executed respectively in the windows window1 and window2 and consecutively on the resource:
d12 = min (t1 in sw1..ew1-pt1, t2 in sw2..ew2-pt2: t1+pt1<=t2) max(t2-(t1+pt1), tt(t1,t2))<br />
Maybe this lower bound on the delay between the two tasks can be tight enough, especially if the two time-windows overlap and, as this delay only depends on the pairs (task1,window1), (task2,window2) it could be expressed as a transition distance.
- also, if the set of time-windows on a resource are quite separated and do not overlap a lot, you could directly add precedence constraints between the tasks that belongs to two non-overlapping time-windows with a delay expression computed using the tasks start/end times and your exact function.
The two cases above suppose that the transition time satisfies the triangular inequality that is, if task1 is scheduled before task2 and task2 before task 3 on the resource, then transition(task1,task3) >= transition(task1,task2)+duration(task2)+transition(task2,task3).
- in general, if the objective is to schedule the tasks "as close as possible" to the middle of the time-window, you could also consider adding some kind of earliness/tardiness cost with respect to this "ideal date" in the window.
2. Modeling the problem with a quadratic number of intervals
The idea, if you have n intervals (acts[i in 1..n]) in a sequence is to create a set of n additional chained intervals (chain[p in 1..n]) that represent the final sequence: one interval for each position in the sequence. Then, you need additional n^2 intervals (!) actAtPos[i ][p] that represent the possible position p in the chain for a given activity i. Activity acts[i ] is an alternative over all its possible positions in the sequence and chain[p] is an alternative over all the activities at position p. Then, you can express the transition time as a delay for the precedence constraint between two consecutive intervals in the chain. I attach a code sample where the transition time between two consecutive intervals i and j is the end time of i modulo 5.
using CP;
int n=10;
int ptmin=1;
int ptmax=n;
dvar interval acts[i in 1..n] size i;
dvar interval chain[p in 1..n] size ptmin..ptmax;
dvar interval actAtPos[i in 1..n][p in 1..n] optional;
minimize max(i in 1..n) endOf(acts[i]);
constraints {
forall(p in 2..n)
endBeforeStart(chain[p-1],chain[p],endOf(chain[p-1])%5);
forall(i in 1..n)
alternative(acts[i], all(p in 1..n)actAtPos[i][p]);
forall(p in 1..n)
alternative(chain[p], all(i in 1..n)actAtPos[i][p]);
noOverlap(acts);
}
But this can scale only for a few ten of intervals.
In your case, intervals acts[i ] are optional because they are themselves member of some alternatives and as a consequence, you do not know the number of intervals in the chain. You can define them as optional and add the constraint that only the first ones will be present: presenceOf(chain[p])=>presenceOf(chain[p-1]). You can of course decrease the number of intervals in the chain in case you have an upper bound on the final number of intervals on the resource.
Given your figures, I don't think it will scale on the complete problem but you could maybe run a first phase using a relaxed or approximated version of the problem (see above) and for instance keep the resource allocation for tasks or even the resource/windows allocations and run this second step with a smaller number of intervals on each resource.
#DecisionOptimization#OPLusingCPOptimizer