Originally posted by: SystemAdmin

Hi,

I am working on a preemptive scheduling problem, by using the techniques described in "P. Laborie, IBM ILOG CP Optimizer for Detailed Scheduling Illustrated on Three Problems".

In the attached example, there is only one task with two slices. And there are two labors who can perform this task. Duration of the task is 29000 secs (200 seconds more then one shift, so will need to preempt-resume in the second day). I limited the solution time to 25secs. Two issues here:

1. it consumes all the time (25secs), for such a trivial instance. (you can also try adding more tasks, and calendar days by uncommenting relevant lines).
2. Objective is to minimize the task end time, however, task is scheduled such that, small portion of it is performed in the first day, and big portion of it is scheduled in the second day. Optimally, the tasks should be completed by time 86600 (28800 in first shift, and 200 in the second shift after the break).

Please advise.

(in case you desired to have quick look, below is the copy of the model, same as attached)---

using CP;   
{string
} labors = 
{
"labor1", 
"labor2"
}; 
{string
} tasks = 
{
"task1"
}; 
//, "task2"};  

int taskSize[t in tasks] = 29000; 
//200 seconds more than one shift (28800)   tuple Slice 
{string task; 

int rank;
}; 
{Slice
} taskSlices = 
{<t,r>|t in tasks, r in 1..2
};   
// Calendar =======================================================================================                                                             tuple Tshifts 
{ string labor; 

int startTime; 

int endTime; 
}; 
{Tshifts
} shiftIntensity = 
{<
", 0, 0>, <", 100, 28800> 
// 1st day , <
",   0, 86400>, <", 100, 115200> 
// 2nd day 
//                                                 , <",   0, 172800>, <",  100, 201600> // 3rd day 
//                                                        , <",   0, 259200>, <", 100, 288000> // 4th day 
//                                                 , <", 0, 345600>, <", 100, 374400> // 5th day  , <
", 0, 0>, <", 100, 28800> 
// 1st day , <
",   0, 86400>, <", 100, 115200> 
// 2nd day 
//                                                       , <",   0, 172800>, <",  100, 201600> // 3rd day 
//                                                        , <",   0, 259200>, <", 100, 288000> // 4th day 
//                                                 , <", 0, 345600>, <", 100, 374400> // 5th day 
}; stepFunction Calendar[l in labors] = stepwise (s in shiftIntensity: s.labor==l) 
{ s.startTime -> s.endTime; 0 
}; execute 
{writeln(Calendar);
}; 
// ================================================================================================   
// EXECUTION PARAMETERS =========================================================================== execute runParameters 
{ var p = cp.param; 
// p.FailLimit = Opl.card(labors)*Opl.card(tasks)*10 + 100000; p.TimeLimit = Opl.card(labors)*Opl.card(tasks)*2 + 20; 
// p.OptimalityTolerance = 0.1; cp.param.TimeMode = 
"ElapsedTime" 
} 
// ================================================================================================     tuple Tallocation 
{ Slice slice; string labor; 
}; 
{Tallocation
} allocations = 
{<ts, l> | ts in taskSlices, l in labors
}; 
// VARIABLES ====================================================================================== dvar interval V_task[t in tasks] 
// optional ; dvar interval V_taskSlice[s in taskSlices] optional ; dvar interval V_allocation[a in allocations] optional intensity Calendar[a.labor] ; dvar sequence V_labor[l in labors] in all(a in allocations: a.labor == l) V_allocation[a]; 
// OBJECTIVE ======================================================================================  minimize   
// sum(t in tasks) presenceOf(V_task[t])  sum(t in tasks) endOf(V_task[t]) + sum(ts in taskSlices) endOf(V_taskSlice[ts]) ; 
// ================================================================================================     
// CONSTRAINTS ==================================================================================== subject to 
{ 
//     forall(t in tasks) 
//            endOf(V_task[t]) <= 86600;  forall(l in labors) noOverlap(V_labor[l]); forall(s in taskSlices) alternative(V_taskSlice[s], all(l in labors) V_allocation[<s,l>],1); forall(s1 in taskSlices, s2 in taskSlices:s1.task==s2.task && s2.rank==s1.rank+1)
{ presenceOf(V_taskSlice[s1])=>presenceOf(V_taskSlice[s2]); endBeforeStart(V_taskSlice[s1], V_taskSlice[s2]); 
} forall(t in tasks)
{ span(V_task[t],all(s in taskSlices: s.task==t)V_taskSlice[s]); taskSize[t] == sum(s in taskSlices: s.task==t)sizeOf(V_taskSlice[s]); 
} forall(a in allocations) forbidExtent(V_allocation[a],Calendar[a.labor]); 
}

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: GGR

Hi

There is two problems in your model

first, the shiftIntensity tuple set is badly defined, the name of the tuple are wrong and the tuple does not take into account the day , I suppose it should look like:

{Tshifts
} shiftIntensity = 
{<
"labor1", 100, 28800> 
// 1st day , <
"labor1", 86400, 115200> 
// 2nd day , <
"labor1",  172800, 201600> 
// 3rd day , <
"labor1", 259200, 288000> 
// 4th day , <
"labor1", 345600, 374400> 
// 5th day  , <
"labor2", 100, 28800> 
// 1st day , <
"labor2", 86400, 115200> 
// 2nd day , <
"labor2",  172800, 201600> 
// 3rd day , <
"labor2", 259200, 288000> 
// 4th day , <
"labor2", 345600, 374400> 
// 5th day 
}; stepFunction Calendar[l in labors] = stepwise (s in shiftIntensity: s.labor==l, p in 0..1) 
{ (p==0) ? 100 : 0 -> (p ==0) ? s.startTime : s.endTime; 100 
}; execute 
{writeln(Calendar);
};

Then you'll see the solver immediately the optimal solution. Eventually for a more complex problem, it may not prove it.

Hope that helps
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Hi GGR,

Thanks for your response. However, I think your suggested version of calendar is doing the reverse of mine, which is not correct. See below some output from both calendar definitions:

//original version:  [stepwise
{ 0 -> 0; 100 -> 28800; 0 -> 86400; 100 -> 115200; 0 
} 
//your suggestion: [stepwise
{ 100 -> 100; 0 -> 28800; 100 -> 86400; 0 -> 115200; 100 
}

Correct one is the first one, wherein shift starts at time 0 to 28800 (100%), then break starts till 86400 (0%).
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Any other suggestions, please?
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Hello,

I think that the following part:

sum(ts in taskSlices) endOf(V_taskSlice[ts])

of your objective function is counter productive. Without it, CP Optimizer finds and proves optimal solution in 0.43s for me. The optimal solution ends at 86 603 what is within default relative optimality tolerance 0.01% (you can change this setting using RelativeOptimalityTolerance parameter). Could you reconsider this part of the objective?

Note also that any sum in objective function does not propagate very well. If it is possible, it is better to use makespan.

Best regards, Petr
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Hello Petr,

Thanks a lot for your reply. As you suggested, removing the end times of the taskSlices from the objective function helps. But using end times of the taskSlices was the suggestion by the paper I mentioned. Not exactly same way tough: It is suggesting to use satisfaction function (wherein the case f=-2 fits my need, schedule as early as possible), which is defines as:

dexpr 

float satisfaction[t in tasks] = (1/taskSize[t])*sum(ts in taskSlices: ts.task==t) lengthOf(V_taskSlice[ts])*( (startOf(V_taskSlice[ts]) + endOf(V_taskSlice[ts]) - 1)/2 - 0)/115200; maximize         sum(t in tasks)satisfaction[t];

And when I tried this one, CP says that model has no solution.
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Hello,

It seems to me that there's a bug for very small numbers. As a workaround please replace 1/taskSize[t] by for example 1000/taskSize[t], then solution is found very quickly. I'll pass the problem to my colleagues in order to fix this bug. Thanks for letting us know!

Petr
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks again for your response Petr.

I changed 1/taskSize[t] to 1000/taskSize[t], and as you mentioned, the solution is found very quickly. However, taskSlices are scheduled in opposite way: as late as possible.

(the satisfaction function f1: Execute as much as possible of task Ti as early as possible)

below is the output of allocation variable:

slice.task slice.rank      labor                           Present Start   End     Size task1              1               labor1  <<
"task1" 1> 
"labor1">        1       28600   28800   200 task1               2               labor1  <<
"task1" 2> 
"labor1">        1       86400   115200  28800

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

I think there f1 and f-1 in that paper are mixed. Obviously, in the previous one, it is trying to maximize a function of (startOf + endOf) the taskSlices.

f-1 makes more sense, which is function of ( maxEndTime - (startOf+endOf) ), as follows:

dexpr 

float satisfaction2[t in tasks] = (1000/taskSize[t])*sum(ts in taskSlices: ts.task==t) lengthOf(V_taskSlice[ts])*(115200-  (startOf(V_taskSlice[ts]) + endOf(V_taskSlice[ts]) - 1)/2 )/115200;     
// resulting output in 25 seconds, still not optimal: slice.task     slice.rank      labor                           Present Start   End     Size task1              1               labor1  <<
"task1" 1> 
"labor1">        1       0       25815   25815 task1             2               labor1  <<
"task1" 2> 
"labor1">        1       86400   89585   3185

with this one, it is again taking too much time.
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, I agree that functions f1 and f-1 seems to be mixed in the paper. And yes, the objective function does not behave well.

The objective functions presented in the paper are not objective functions that suites best CP Optimizer. In fact it is the opposite. However the problem was originally defined this way and the model in OPL had to follow it in order to be comparable with the original approach. If you have the possibility to define (or adjust) the objective function yourself, I recommend you to use another function. Simple rules are:

• Don't use any interval variable more than once in the objective function. For example, use startOf, endOf (in more complex cases startEval or endEval) but do not use expressions like lengthOf*(startOf + endOf). Such expression doesn't propagate well since it consider each attribute separately.
• Prefer to use min or max over sum. Min and max propagate much better than sum, this is the reason why makespan objective works so well.

The result of the paper can be interpreted that CP Optimizer behaves quite well (better than original approach) despite the fact that the objective function is not very suitable for CP.

Petr
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks a lot for all your responses Petr. These information will be very helpful.
#ConstraintProgramming-General
#DecisionOptimization