Pinned topicHow can I synch the sizes of interval variables
20120403T16:22:48Z

Answered question
This question has been answered.
Unanswered question
This question has not been answered yet.
I am modeling a simple scheduling problem, where each task needs a labor assignment. Labor has working calendar as: 10hrs work, 10hrs break, 10hrs work, which is defined by intensity function as below:
// a calendar with two shifts [0,10] and [20, 30], with 10 units break in between tuple Tshifts
{
int startTime;
int endTime;
};
{Tshifts
} shiftIntensity =
{<0, 0>, <100, 10>, <0, 20>, <100, 30>
}; stepFunction Calendar = stepwise (s in shiftIntensity)
{ s.startTime > s.endTime; 0
}; execute
{writeln(Calendar);
};
// output of the calendar: stepwise{ 0 > 0; 100 > 10; 0 > 20; 100 > 30; 0 }
Task requires 11 hrs of work time. So expected results is labor start working at time 0 and end at time 21, resulting 11 hrs of working time (size(labor) = 11).
I am using alternate function to force picking a labor for each task, and synch the start and end times of the task and allocation variables, but this does not sync their sizes, resulting labor to start at time 0 and end at time 11, with net working time of 10 hrs ( size(labor) = 10).
Is there a way of synching the sizes of these interval variables (task and allocation)?
I attached the model, which you can directly run and get the results (no data file needed).
Thanks a lot,
I am modeling a simple scheduling problem, where each task needs a labor assignment. Labor has working calendar as: 10hrs work, 10hrs break, 10hrs work, which is defined by intensity function as below:
<pre class="jivepre">
// a calendar with two shifts [0,10] and [20, 30], with 10 units break in between tuple Tshifts
{
int startTime;
int endTime;
};
{Tshifts
} shiftIntensity =
{<0, 0>, <100, 10>, <0, 20>, <100, 30>
}; stepFunction Calendar = stepwise (s in shiftIntensity)
{ s.startTime > s.endTime; 0
}; execute
{writeln(Calendar);
};
// output of the calendar: stepwise{ 0 > 0; 100 > 10; 0 > 20; 100 > 30; 0 }
</pre>
Task requires 11 hrs of work time. So expected results is labor start working at time 0 and end at time 21, resulting 11 hrs of working time (size(labor) = 11).
I am using alternate function to force picking a labor for each task, and synch the start and end times of the task and allocation variables, but this does not sync their sizes, resulting labor to start at time 0 and end at time 11, with net working time of 10 hrs ( size(labor) = 10).
Is there a way of synching the sizes of these interval variables (task and allocation)?
I attached the model, which you can directly run and get the results (no data file needed).
The intensity declaration induces a constraint between the size, the length (end  start) and the intensity function of an interval variable.
In your model:
dvar interval V_task[t in tasks] optional size 11;
You tell that a V_task element has a size of 11 without intensity function. So you implicitly tell that length == size = 11 for the interval variable.
dvar interval V_allocation[a in allocations] optional intensity Calendar;
A V_allocation has an intensity function but a free size in [0, intervalMax]. Then the alternative constraint fixes its length to 11 and the intensity constraint adapts the size of the V_allocation element to a compatible one (for sure not 11).
You must declare the size in the interval variables that have the intensity function. That is the right model is:
dvar interval V_task[t in tasks] optional; dvar interval V_allocation[a in allocations] optional size 11; intensity Calendar
A good practice when you deal with alternative is to not set any parameter (apart the optionality) in the slaves interval variables declaration.
A last detail, the value of a numerical expression on an interval variables in case of absence in a solution should be given in the absence value argument of the expression. Your objective becomes:
maximize  sum(t in tasks) endOf(V_task[t], 100);
// or minimize sum(t in tasks) endOf(V_task[t], 100);
For full information about all these points, I suggest you consult the conceot part of the reference manual:
Go to CP Optimizer > CP Optimizer C++ API Reference Manual
then select Concepts
Hope that helps
Hi
The intensity declaration induces a constraint between the size, the length (end  start) and the intensity function of an interval variable.
In your model:
<pre class="jivepre">
dvar interval V_task[t in tasks] optional size 11;
</pre>
You tell that a V_task element has a size of 11 without intensity function. So you implicitly tell that length == size = 11 for the interval variable.
A V_allocation has an intensity function but a free size in [0, intervalMax]. Then the alternative constraint fixes its length to 11 and the intensity constraint adapts the size of the V_allocation element to a compatible one (for sure not 11).
You must declare the size in the interval variables that have the intensity function. That is the right model is:
<pre class="jivepre">
dvar interval V_task[t in tasks] optional; dvar interval V_allocation[a in allocations] optional size 11; intensity Calendar
</pre>
A good practice when you deal with alternative is to not set any parameter (apart the optionality) in the slaves interval variables declaration.
A last detail, the value of a numerical expression on an interval variables in case of absence in a solution should be given in the absence value argument of the expression. Your objective becomes:
<pre class="jivepre">
maximize  sum(t in tasks) endOf(V_task[t], 100);
// or minimize sum(t in tasks) endOf(V_task[t], 100);
</pre>
For full information about all these points, I suggest you consult the conceot part of the reference manual:
Go to CP Optimizer > CP Optimizer C++ API Reference Manual
then select Concepts
Thanks GGR, but your suggestion really does not work for this problem.
Because of the nature of the problem, sizes of the tasks are known and are part of the requirement. But the size of the labors (workers) are not known, and should be made by decisions. In the attached problem, it is over simplified, with one labor and task. But in reality, there are many tasks and labors, so size of the labor will depend on the tasks it is assigned to.
On the other hand, labors have working calendar but tasks do not have a calendar.
Putting these together, I have to define V_task with task duration, and V_task with calendar and no duration.
Still need to tie their sizes to make sure that labor really work at its assigned duration (so sleeping time is not counted as work :) ).
Thanks GGR, but your suggestion really does not work for this problem.
Because of the nature of the problem, sizes of the tasks are known and are part of the requirement. But the size of the labors (workers) are not known, and should be made by decisions. In the attached problem, it is over simplified, with one labor and task. But in reality, there are many tasks and labors, so size of the labor will depend on the tasks it is assigned to.
On the other hand, labors have working calendar but tasks do not have a calendar.
Putting these together, I have to define V_task with task duration, and V_allocation with calendar and no duration.
Still need to tie their sizes to make sure that labor really work at its assigned duration (so sleeping time is not counted as work :) ).
As GGR suggested, I can not fix the size of the task variables, because the final size will be driven by the allocations and labor availability, this was step one.
Next, added a conditional constraint on the size of the allocation, such that, if allocation exist, then the size should be greater than or equal to the size of the task it is assigned to.
These both together solved my problem.
below is the updated code :
using CP;
{string
} labors =
{
"labor1",
"labor2"
};
{string
} tasks =
{
"task1",
"task2"
};
// a calendar with two shifts [0,10] and [20, 30], with 10 units break in between tuple Tshifts
{
int startTime;
int endTime;
};
{Tshifts
} shiftIntensity =
{<0, 0>, <100, 10>, <0, 20>, <100, 30>
}; stepFunction Calendar = stepwise (s in shiftIntensity)
{ s.startTime > s.endTime; 0
}; execute
{writeln(Calendar);
};
// output of the calendar: stepwise{ 0 > 0; 100 > 10; 0 > 20; 100 > 30; 0 } tuple Tallocation
{ string t; string l;
};
{Tallocation
} allocations =
{<t, l>  t in tasks, l in labors
};
// VARIABLES ====================================================================================== dvar interval V_task[t in tasks] optional
// size 11 ; dvar interval V_allocation[a in allocations] optional intensity Calendar; dvar sequence V_labor[l in labors] in all(a in allocations: a.l == l) V_allocation[a];
// OBJECTIVE ====================================================================================== maximize 100*sum(t in tasks) presenceOf(V_task[t])  sum(t in tasks) endOf(V_task[t], 100);
// ================================================================================================
// CONSTRAINTS ==================================================================================== subject to
{
// C_No_Overlap: forall(l in labors) noOverlap(V_labor[l]);
// C_Alternative: forall(t in tasks) alternative(V_task[t], all(a in allocations: a.t==t) V_allocation[a], 1); forall(a in allocations) presenceOf(V_allocation[a]) => sizeOf(V_allocation[a]) >= 11;
}
Final note: this may not be the most efficient formulation, since it is using conditional constraints. I still would like to hear, if anyone knows a better / direct way of doing this.
My second question is about assigning one task to the multiple labors during the time horizon (labor1 will do the work today, and labor2 will continue tomorrow). I will prepare an example code and post the question here.
Found a solution!
As GGR suggested, I can not fix the size of the task variables, because the final size will be driven by the allocations and labor availability, this was step one.
Next, added a conditional constraint on the size of the allocation, such that, if allocation exist, then the size should be greater than or equal to the size of the task it is assigned to.
These both together solved my problem.
below is the updated code :
<pre class="jivepre">
using CP;
{string
} labors =
{
"labor1",
"labor2"
};
{string
} tasks =
{
"task1",
"task2"
};
// a calendar with two shifts [0,10] and [20, 30], with 10 units break in between tuple Tshifts
{
int startTime;
int endTime;
};
{Tshifts
} shiftIntensity =
{<0, 0>, <100, 10>, <0, 20>, <100, 30>
}; stepFunction Calendar = stepwise (s in shiftIntensity)
{ s.startTime > s.endTime; 0
}; execute
{writeln(Calendar);
};
// output of the calendar: stepwise{ 0 > 0; 100 > 10; 0 > 20; 100 > 30; 0 } tuple Tallocation
{ string t; string l;
};
{Tallocation
} allocations =
{<t, l>  t in tasks, l in labors
};
// VARIABLES ====================================================================================== dvar interval V_task[t in tasks] optional
// size 11 ; dvar interval V_allocation[a in allocations] optional intensity Calendar; dvar sequence V_labor[l in labors] in all(a in allocations: a.l == l) V_allocation[a];
// OBJECTIVE ====================================================================================== maximize 100*sum(t in tasks) presenceOf(V_task[t])  sum(t in tasks) endOf(V_task[t], 100);
// ================================================================================================
// CONSTRAINTS ==================================================================================== subject to
{
// C_No_Overlap: forall(l in labors) noOverlap(V_labor[l]);
// C_Alternative: forall(t in tasks) alternative(V_task[t], all(a in allocations: a.t==t) V_allocation[a], 1); forall(a in allocations) presenceOf(V_allocation[a]) => sizeOf(V_allocation[a]) >= 11;
}
</pre>
Final note: this may not be the most efficient formulation, since it is using conditional constraints. I still would like to hear, if anyone knows a better / direct way of doing this.
My second question is about assigning one task to the multiple labors during the time horizon (labor1 will do the work today, and labor2 will continue tomorrow). I will prepare an example code and post the question here.
/**/ dvar interval V_allocation[a in allocations] optional intensity Calendar;
/**/ subject to
{
/**/ forall(a in allocations) presenceOf(V_allocation[a]) => sizeOf(V_allocation[a]) >= 11;
/**/
};
Is equivalent with the declaration
/**/
int horizon = intMax/21
// a very big number dvar interval V_allocation[a in allocations] optional size 11..horizon intensity Calendar;
/**/
};
Another point, it is useless to add an implication between the presence of an interval variable and any numerical expression on this interval variable. The dependence is more efficiently enforced in the declaration of the interval variable.
That is
forall(a in allocations) presenceOf(V_allocation[a]) => sizeOf(V_allocation[a]) >= 11;
Should be replaced by
forall(a in allocations) sizeOf(V_allocation[a], 11) >= 11;
In general, before using a interval variable based construct in a metaconstraint (and, or, => constraints), you should verify if the condition on presence is not covered by the model constructs on the interval variables.
Hope that helps
Hi
Two remarks
Your model
<pre class="jivepre">
/**/ dvar interval V_allocation[a in allocations] optional intensity Calendar;
/**/ subject to
{
/**/ forall(a in allocations) presenceOf(V_allocation[a]) => sizeOf(V_allocation[a]) >= 11;
/**/
};
</pre>
Is equivalent with the declaration
<pre class="jivepre">
/**/
int horizon = intMax/21
// a very big number dvar interval V_allocation[a in allocations] optional size 11..horizon intensity Calendar;
/**/
};
</pre>
Another point, it is useless to add an implication between the presence of an interval variable and any numerical expression on this interval variable. The dependence is more efficiently enforced in the declaration of the interval variable.
That is
<pre class="jivepre">
forall(a in allocations) presenceOf(V_allocation[a]) => sizeOf(V_allocation[a]) >= 11;
</pre>
Should be replaced by
<pre class="jivepre">
forall(a in allocations) sizeOf(V_allocation[a], 11) >= 11;
</pre>
In general, before using a interval variable based construct in a metaconstraint (and, or, => constraints), you should verify if the condition on presence is not covered by the model constructs on the interval variables.
Thank you very much GGR. I was confused between the concepts of size and length. I Realized that, actually your first suggestion was perfectly correct. I can put size requirement to the V_Allocation variables directly, since those are task dependent (so sizes are known).
dvar interval V_allocation[a in allocations] optional size taskSize[a.task] intensity Calendar[a.labor];
Now, second part of my question is, how to handle assigning multiple labors to single task during the horizon, i.e., if task size is 15 and labor1 calendar allows working in 0,10] and labor2 calendar allows working in (10,20, then labor1 should work 10hrs and labor2 should work remaining 5 hrs. (see calendar definition as below):
I also attached the full example model, if you would like to try.
Thank you very much GGR. I was confused between the concepts of size and length. I Realized that, actually your first suggestion was perfectly correct. I can put size requirement to the V_Allocation variables directly, since those are task dependent (so sizes are known).
<pre class="jivepre">
dvar interval V_allocation[a in allocations] optional size taskSize[a.task] intensity Calendar[a.labor];
</pre>
Now, second part of my question is, how to handle assigning multiple labors to single task during the horizon, i.e., if task size is 15 and labor1 calendar allows working in 0,10] and labor2 calendar allows working in (10,20, then labor1 should work 10hrs and labor2 should work remaining 5 hrs. (see calendar definition as below):
<pre class="jivepre">
{Tshifts
} shiftIntensity =
{<labor1, 0, 0>, <labor1, 100, 10>, <labor1, 0, 20>, <labor2, 0, 0>, <labor2, 0, 10>, <labor2, 100, 20>
}; stepFunction Calendar[l in labors] = stepwise (s in shiftIntensity: s.labor==l)
{ s.startTime > s.endTime; 0
}; execute
{writeln(Calendar);
};
// output of the calendar: [stepwise{ 0 > 0; 100 > 10; 0 } stepwise{ 0 > 0; 0 > 10; 100 > 20; 0 }]
</pre>
I also attached the full example model, if you would like to try.
Basically, you want to cut a task in several operations that will be executed on different <<labors>>. In practice that means that you want having interruptible task.
The best way to write such a model heavily depends upon the exact problems. That is what are actual operational constraints that conditions allowing/forbidding interruption and the conditions that allows restoring execution.
Nevertheless, the foundations of such model is to create a logico temporal chain of interval variables.
int N = ...;
//number of task
int NSlices[1..N] = ...;
// number of execution intervals for a task tuple Slice
{
int task,
int rank
};
{Slice
} Slices =
{<t, r>  t in 1..N, r in 1..NSlices[i]
}; dvar interval tasks[i in 1..N] = ...; dvar interval slices[s in Slices] = ...; constraints
{ forall(t in tasks)
{ span(tasks[t], all(s in Slices, s.t == t) slices[s]); forall(r in 1..NSlices[i]1)
{ <<precedence>>(NSlices[<t, r>], NSlices[<t, r+1>)];
// choose the right precedence type presenceOf(NSlices[<t, r>]) >= presenceOf(NSlices[<t, r+1>]);
}
}
Then, define on the slices the model for their conditions and requirement of execution.
You will find a model containing interruptible activities in: (third problem in the paper)
Philippe Laborie, IBM ILOG CP Optimizer for Detailed Scheduling Illustrated on Three Problems, Proc. CPAIOR 2009, 2009
Hope that helps
Hi
Basically, you want to cut a task in several operations that will be executed on different <<labors>>. In practice that means that you want having interruptible task.
The best way to write such a model heavily depends upon the exact problems. That is what are actual operational constraints that conditions allowing/forbidding interruption and the conditions that allows restoring execution.
Nevertheless, the foundations of such model is to create a logico temporal chain of interval variables.
<pre class="jivepre">
int N = ...;
//number of task
int NSlices[1..N] = ...;
// number of execution intervals for a task tuple Slice
{
int task,
int rank
};
{Slice
} Slices =
{<t, r>  t in 1..N, r in 1..NSlices[i]
}; dvar interval tasks[i in 1..N] = ...; dvar interval slices[s in Slices] = ...; constraints
{ forall(t in tasks)
{ span(tasks[t], all(s in Slices, s.t == t) slices[s]); forall(r in 1..NSlices[i]1)
{ <<precedence>>(NSlices[<t, r>], NSlices[<t, r+1>)];
// choose the right precedence type presenceOf(NSlices[<t, r>]) >= presenceOf(NSlices[<t, r+1>]);
}
}
</pre>
Then, define on the slices the model for their conditions and requirement of execution.
You will find a model containing interruptible activities in: (third problem in the paper)
Philippe Laborie, IBM ILOG CP Optimizer for Detailed Scheduling Illustrated on Three Problems, Proc. CPAIOR 2009, 2009
Thanks again GGR, for your response.
I saw Philippe's suggestion for interruptible previously, but in my case I think (and hope) that we can model the problem without slices. Because, my case, we don't really need to divide the tasks, they are continuous, single piece. Just need to have flexibility of assigning multiple resources. I am not sure if it is possible, but I was thinking that a modified alternative constraint with some other size constraint may solve the problem, something like:
// instead of assigning 1, lets say will assign 2 resources forall(t in tasks) alternative(V_task[t], all(a in allocations: a.task==t) V_allocation[a], 2); forall(t in tasks) sum(a in allocations: a.task=t) sizeOf(V_allocation[a]) == t.size
Above code, will only work when we know that 2 resources will be allocated to each task. So is not really correct. Maybe, can create a dummy resource, which can be allocated to any task but not preferred. So in the case of single allocation, model can pick a real resource with full size and a dummy resource with 0 size.
Again, I am not sure if this is a correct approach, but just trying to avoid implementing full interruption, since I believe this problem is one step simpler.
Thanks again GGR, for your response.
I saw Philippe's suggestion for interruptible previously, but in my case I think (and hope) that we can model the problem without slices. Because, my case, we don't really need to divide the tasks, they are continuous, single piece. Just need to have flexibility of assigning multiple resources. I am not sure if it is possible, but I was thinking that a modified alternative constraint with some other size constraint may solve the problem, something like:
<pre class="jivepre">
// instead of assigning 1, lets say will assign 2 resources forall(t in tasks) alternative(V_task[t], all(a in allocations: a.task==t) V_allocation[a], 2); forall(t in tasks) sum(a in allocations: a.task=t) sizeOf(V_allocation[a]) == t.size
</pre>
Above code, will only work when we know that 2 resources will be allocated to each task. So is not really correct. Maybe, can create a dummy resource, which can be allocated to any task but not preferred. So in the case of single allocation, model can pick a real resource with full size and a dummy resource with 0 size.
Again, I am not sure if this is a correct approach, but just trying to avoid implementing full interruption, since I believe this problem is one step simpler.