Decision Optimization

Originally posted by: Avadrus

Hi,

I'm currently trying to integrate calendars in my program that is to be solved using CP optimizer. I have already managed to extract the working hours for my problem from an excel sheet and created a step function that is then connected to the intervals representing the tasks which should be scheduled.

Unfortunately, I now have the issue that shifts in my problem only have a duration of 12 hours with some tasks exceeding 12 hours of processing time. Therefore, some tasks would have to be split up in multiple "parts" so that they're carried out over multiple days. This is not done automatically by CP Optimizer, the software is therefore not able to find a feasible solution.

Does anybody have an idea on how to solve this type of problem using Constraint Programming?

Thanks in advance!

Originally posted by: Petr Vilím

Hello,

you can use your step function as "intensity" of an interval variable to automatically prolong it so that it continues from one shift to another shift and doesn't count the time in between the shifts as a processing time. Yes, it doesn't split the task into smaller sub-tasks. Sometimes it is not an issue: if the task requires some resource (e.g. noOverlap or cumul function) then the machine is also stopped in between the shifts. But sometimes it is a problem: the machine is used by another workers in between the particular shifts and such posponed task would block it. Is it your case?

In the worst case you can split your task. Say for example that the task can overlap 5 shifts maximum, then create 5 interval variables part[1]..part[5]. The idea is that part[1] is (chronologically) the first part, then part[2] and so on. Duration of the parts is not known in advance but minimum duration should be 1 (I guess). Since we don't know how many parts we will need the interval variables should be marked as optional. Then connect the parts together by constraints:

endBeforeStart(part[i], part[i+1]); // Parts are chronological
presenceOf(part[i+1]) <= presenceOf(part[i]); // If part[i+1] is used then part[i] must be also used
forbidOverlap(task[i], stepFunctionsForShifts); // Parts cannot overlap breaks between shifts
taskDuration == sum(i in 1..5) lengthOf(part[i]); // Total duration of the parts
if ((i-1)*maxDurationOfAPart < taskDuration) presenceOf(part[i]); // Depending on taskDuration several first parts are known to be used

Moreover only first part can start at any time, the remaining parts must start at the beginning of a shift. We can create a step function that allows only such start times and then use it for all but not the first part:

forbidStart(part[i], NotShiftStartStepFunction);

Similarly only the last part can end at any time, remaining parts must end at the end of a shift. The issue is that we don't know in advance which part is the last one and function forbidEnd cannot be used in a logical expression. So we can model it as:

!presenceOf(part[i+1]) || (endOf(part[i], 0) in ArrayOfShiftEndsAndZero)

Note that endOf(part[i], 0) returns 0 when part[i] is absent and so ArrayOfShiftEndsAndZero must contain value 0 (you can use another value if you want) to make the constraint satisfied when part[i] is absent. In other languages than OPL the "in" operator is called IloAllowedAssignments.

There should be also max-delay constraint to make sure there isn't a whole shift between two parts. It could be achieved by:

startBeforeEnd(start[i+1], start[i], -maxLengthOfABreak)

Notice that the last parameter is negative.

Best regards,

Petr

Originally posted by: Avadrus

Hi,

first of all, thank you very much for your reply!

you can use your step function as "intensity" of an interval variable to automatically prolong it so that it continues from one shift to another shift and doesn't count the time in between the shifts as a processing time. Yes, it doesn't split the task into smaller sub-tasks. Sometimes it is not an issue: if the task requires some resource (e.g. noOverlap or cumul function) then the machine is also stopped in between the shifts. But sometimes it is a problem: the machine is used by another workers in between the particular shifts and such posponed task would block it. Is it your case?

 That's actually exactly what I did, which is why I do not really understand why my code doesn't work.

stepFunction Calendar[i in Machines] = stepwise (s in Steps[i]) { s.v -> s.x; 100 };

dvar interval tasks[j in Tasks] in 1..(maxint div 2)-1 size ftoi(ceil(task_duration[j]));       
dvar interval tasks_opt[i in Machines][j in Tasks] optional in 1..(maxint div 2)-1 size ftoi(ceil(task_duration[j])) intensity Calendar[i];

As you can see, I used the step-Function modeling the working hours as intensity for my optional intervals that represent the execution of a task on a certain machine. In my case, the task blocking the machine between two shifts is not an issue as the production is completely shut down outside of production hours. So I should normally be able to avoid the modeling alternative you proposed, right?

Despite this, when I execute my program, all tasks that exceed a duration of 12 hours (which is the shift length) are scheduled to be carried out at the "end" of my planning horizon when the step function has, per definition, the value "100" for an infinite period of time. Do you have any idea why this might be happening? The behaviour that you describe where the task is just "prolonged" thorugh multiple shifts is exactly what I need, but it currently doesn't seem to work for me.

Thanks as well for the alternative you proposed. Because there are not only the shifts to be respected in my problem, but also sequence-dependent setup times and further resources apart from the workers discussed, I feel like using the it would make my program become far more complicate.

Originally posted by: Petr Vilím

Sure, for your problem using the model with task parts is an overkill.

I believe the problem in your case is the fact that tasks have size specified, it should be enough to specify size on tasks_opt (or vice versa: specify size on tasks but do not on tasks_opt). Note that if you specify a size and not intensity then it is the same as specifying the length of the interval. Constraint "alternative" synchronizes task with the chosen tasks_opt, i.e. it synchronizes their start and end (and therefore also the length). The two intervals can use different intensities though and so their size could be different.

In your case "tasks" have fixed size but not intensity, so they have fixed length. This fixed length effectively rules out all alternatives in tasks_opt with bigger length, i.e. all the alternatives with the task preempted by a break between shifts.

Best regards, Petr

Originally posted by: Avadrus

Hi,

thanks for your reply, I apologize for my delayed reply but I've been quite busy for the past few days.

I have now found the time to try out your suggestion and therefore changed my code as follows:

stepFunction Calendar[i in Machines] = stepwise (s in Steps[i]) { s.v -> s.x; 100 };

dvar interval tasks[j in Tasks] in 1..(maxint div 2)-1;       
dvar interval tasks_opt[i in Machines][j in Tasks] optional in 1..(maxint div 2)-1 size ftoi(ceil(task_duration[j])) intensity Calendar[i];

So what I did was to remove the size specified for tasks, now only tasks_opt have a specified size. Unfortunately, that didn't solve my problem. I also tried it out the other way around (size specified for tasks, but not for tasks_opt, but that too doesn't work). It is still the case that tasks exceeding the shift duration of 12 hours are not split up.

Do you have any idea what might cause this behaviour? In addition to the stepFunction for the working hours, I have specified two sequence variables over tasks_opt that are used together with a noOverlap-Constraint in order to have CP Optimizer respect setup times between the tasks.

Then there's the alternative-Constraint for tasks and tasks_opt, a constraint that forces tasks to not start before minute "15" and the following constraint:

forall(i in Machines, j in Tasks){    
                forbidExtent(tasks_opt[i][j], Calendar[i]);
                forbidStart(tasks_opt[i][j], Calendar[i]);
                forbidEnd(tasks_opt[i][j], Calendar[i]);
        }

I have mainly learned what I know about CP Optimizer for scheduling by using the pdfs that came with the software, and there's an example program there that suggests using these constraints to force the program to respect the feasible working hours defined by the intensity function. Could these constraints be the origin of my problem?

Kind regards

Originally posted by: Petr Vilím

Hello,

yes, I believe that the constraint forbidExtent is the problem. This constraints forbids the interval to overlap a segement for the calendar with value 0. So it does exactly the opposite of what you want.

The other two constraints forbids the interval to start/end during non-working hours (segment with 0 value in the function). For example, sometimes it could be that a task acquire the right size exactly at the end of a shift. Extending the task during non-working hours would not change the size of the interval variable since the intensity is 0. So without forbidEnd a solution when such task ends during non-working hours would be valid.

For reference, here is some doc:

https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/refcppcplex/html/interval_variables.html#50

And here is an example (not in OPL but syntax is similar and the semantics is exactly the same):

https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cpo.help/CP_Optimizer/reffileformatcpo/functions/forbidExtent.html

Best regards, Petr

Originally posted by: Avadrus

Hello,

thanks a lot for your reply, the problem was indeed caused by the "forbidExtent" constraints. I had assumed that they were necessary to enforce the solver to respect the working hours. As it turns out, this is already achieved by defining the stepFunction as intensity for the interval variables.

Thanks again for your help, it is much appreciated!
Kind regards

Originally posted by: Avadrus

Hello,

I now tried to integrate another component in my model and unfortunately, I am encountering yet another problem (which is similar, therefore I didn't start a new thread).

Deleting the "forbidExtent"  command lead to the tasks being split up perfectly. Now there's another thing I need to respect in my model which is certain workers are available.To model this, I used a cumulFunction as follow:

cumulFunction usage_workers = sum(j in Tasks) pulse(tasks[j],1);

cumulFunction availability_workers = sum(a in working_hours)(pulse(a.s, a.e, a.p));

and then the constraint

availability_workers - usage_workers >= 0;

The set "working_hours" contains tuples created in an execute block right before that contain the working hours as follow: <"start", "end", "number of workers present from start to end">.

This again leads to tasks longer than the maximum length of a shift (12 hours) not being split up --> model is not feasible. When adding something like "+ pulse(400000, 800000, 1)" to the definition of my availability function, everything works fine.

I guess the problem here are the intervals overlapping times when no workers are present. Could it be that, although the intensity during these periods equals zero, the interval "pushes" up the cumulFunction or its whole length? If yes, is there any way to resolve this problem or an alternative approach to model what I'm trying to achieve?

Kind regards

Originally posted by: Petr Vilím

Hello,

yes, you're right. Intensity function can prolong an interval variable, but pulse function always increases the cumul function from start to end, regardless the intensity function on the interval variable. It is quite a common misconception that intensity also affects the pulse.

From your previous answers it seems to me that in your case it should be enough to stop limitting the cumul function in between the shifts (for example by prolonging working_hours records by the following shift). Because anyway no tasks could start or end between the shifts (if your still using forbidStart and forbidEnd constraints) and so only the interrupted tasks could contribute to the cumul function between the shifts. And such interrupted tasks are already constrained enough by the cumul during the shifts.

Best regards, Petr

Originally posted by: Avadrus

Hello,

thank you very much for your reply, it is now clear to me what the problem with my original code was.

I added pulses to the times in between the single shifts and my code now works as I wish.

One (hopefully last) question remains:

Because I now have to differentiate between tasks requiring the presence of a worker and tasks that don't, I had to split up my sequence variable representing the assignment of the tasks to the specific machines. As I also have setup times to be respected, these have a "type" assigned to them as follows:

dvar sequence machines_without_worker[i in Machines1] in all(j in Tasks : requires_worker[j]==0) tasks_opt[i][j] types all(j in N : requires_worker[j]==0) INTEGERTYPE_tasks[j];
dvar sequence machines_with_worker[i in Machines2] in all(j in Tasks : requires_worker[j]==1) tasks_opt[i][j] types all(j in N : requires_worker[j]==1) INTEGERTYPE_tasks[j];

where INTEGERTYPE_tasks[j] = j. This is necessary because lateron, I have

forall (i in Machines1)
        noOverlap(machines_without_worker[i], setuptimes);
        
        forall(i in Machines2)
                noOverlap(machines_with_worker[i], setuptimes);

Does CP assign these types correctly to the intervals in my sequence variables in this case (although they are now split up in two sequence variables) or would I have to define two separate INTEGERTYPE-arrays for that?

Kind regards

Originally posted by: rdumeur

Dear Avadrus,

I don't see why you'd need two different INTEGERTYPE arrays since you use it to map tasks to task types in your sequence declaration.

But in your model fragment you use the setuptimes matrix for both kinds of sequence (with and without workers). Are setup times actually identical for these two cases?

Cheers,

Originally posted by: Petr Vilím

Hello,

actually I don't understand the question. Of course you can reuse the same array for multiple sequence variables. You can also reuse the same transition matrix for more noOverlap constraints.

Note that setup times are respected between every two intervals variables belonging to the same sequence (when the sequence is constrained by noOverlap). Interval variables in two different sequences are not constrained even if the two sequences use the same setup times matrix (if it was the question).

Best regards, Petr

Originally posted by: Avadrus

Hi,

thanks for your replies, looking at my question again, I do have to admit that it is quite logical this shouldn't pose a problem. I thought I had identified this as the cause for some of my tasks not respecting setup times after the adding the differentiation between the two machine types. But the problem was, in fact, that I had to forgotten to alter the alternative constraints I am using. So now everything works fine, thanks again for your help on this!

Kind regards