Originally posted by: SystemAdmin

Hi,
In my problem, certain tasks can be done more than once so that if one such task is scheduled k times, I receive its value k times over. E.g. if task A's duration is 10 seconds and its available time window is 20-42, then the task can be done at most twice (assuming no transition time) since 20 seconds is smaller than the time window and 30 seconds is bigger than the time window. Since the task is optional, I let the solver choose whether it is done once, twice, or not at all.

Currently, I successfully model this feature by creating k separate intervals for task A where k is the maximum number of times A could be done in its time window. I believe this is the only way to do it but thought perhaps someone knew a clever way to model this that would require only one interval variable. In practical-sized problems of mine, there may be tasks that can (and will in good solutions) be done 10, 15, or even more times, and I'd love to not have to create separate interval variables for each possible time.

Thank you
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Hello,
I think that except for some specific cases you should indeed use k intervals as in the model you describe. The best is to define a chain of k optional intervals (endBeforeStart) with presence implication constraints, something like:

int k=10; dvar interval task[ i in 1..k ] optional size 10; dvar 

int n;   constraints 
{ forall(i in 1..k) 
{ i*presenceOf(task[i]) <= n; 

if (1<i) 
{ endBeforeStart(task[i-1], task[i]); presenceOf(task[i]) => presenceOf(task[i-1]); 
} 
} 
};

Of course, in case the different instances of the same task are (or can be considered as) contiguous, you can use the same interval variable and constrain its size (or length):

int k=10; dvar interval task optional size 10..k*10; dvar 

int n;   constraints 
{ 10*n == sizeOf(task); 
// n=0 iff interval task is absent 
}

Hope this helps,
Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Thank you Philippe,

Your two ideas are both excellent - I'm not currently using a chain of intervals.

Since some tasks can only be done once no matter how large their time window and some can be done as many times as can fit inside their time window, I think this would make the interval in which I store all tasks pretty messy, right? I.e., each task's interval would have to be in reality a chain of intervals where the length would be 1 for all tasks that can only be done once, and the length would be a variable k for the other tasks, where k is the number of times it can be done within that time window.

I'm guessing it may be possible to get that to work, but I'll stick with the slightly less efficient but working code that I have for now. However, your ideas give me alternative ways to approach the issue down the road.
Thank you!
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

I think you should index the intervals by some tuple sets. Here is an example for illustration:

int nbTasks = 4; 

int k[1..nbTasks] = [1,  3,  3, 2]; 
// Maximal number of instances depends on task 

int d[1..nbTasks] = [10, 8, 10, 5]; 
// Duration of each task instance tuple TaskInstance 
{ 

int task; 

int nb; 
};   
{ TaskInstance 
} instances[i in 1..nbTasks] = 
{ <i,j> | j in 1..k[i] 
}; 
{ TaskInstance 
} allInstances = union(i in 1..nbTasks) instances[i]; dvar interval task[i in allInstances] optional size d[i.task];   maximize sum(i in allInstances) presenceOf(task[i]); constraints 
{ forall(i in 1..nbTasks) 
{ forall(j in instances[i]) 
{ 

if (1<j.nb) 
{ endBeforeStart(task[<i,j.nb-1>], task[<i,j.nb>]); presenceOf(task[<i,j.nb>]) => presenceOf(task[<i,j.nb-1>]); 
} 
} 
} 
};

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Philippe,

In your idea about varying the size of contiguous tasks, this is very close to being appropriate for what I'm doing. However, there is a small transition or set-up time between each scheduling of the task. I don't suppose it's possible to somehow work that in here?
I.e. if task A can be done 5 times, each at a length of 10, there may be a 1-second 'transition time' that must be respected between each time A is done 'contiguously'. Though I possibly could get away with just declaring that there is no transition time, is there a way to make the two things work together?

Thank you.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

The model with contiguous tasks will work only if the set of instances of a given task can be considered as a single task and grouped as a single interval variable. In particular, if the task require some resources and the resource can be interrupted in between two instances of the same task T1 in order to perform a different task T2, it won't work.

If the problem is only these additional transition times, you could just try to increase the size of the task accordingly, something like:

int k=10; dvar interval task optional size 10..k*10+(k-1)*1; 
// k-1 "transition times" dvar 

int n; constraints 
{ (11*n)-1 == sizeOf(task); 
// n=0 iff interval task is absent 
}

Philippe
#DecisionOptimization
#OPLusingCPOptimizer