Originally posted by: LucaDiGaspero

I'm modeling a workforce scheduling model through CP as follows:

shttp://1..n is a set of intervals, each of them is associated with a cumulative function with the employees that are present during s
r is an interval with a cumulative function with the number of required employees (r comprises all s)

The objective function should be the difference of the two cumulative functions summed up to all timeslot of r. I could not find any way to express this (according to what I understood cumulative functions can be queried only about the contribution of a given task and not for their actual value). Is there a way to overcome this limitation?

Thanks in advance for your help.

Luca
#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

Dear Luca,
Could you give some more details about the model, in particular:

• are some of the intervals s or r fixed ? if they are not fixed, are there some particular relations between the intervals in r (or in s), like for instance a total order.
• is there a constraint in the model stating that at any time, the number of required employees is lower than the number of present employees?
• what it the grain of the time slots you mention compared with the duration of intervals in r, compared with the horizon of the schedule?

In general, one of the big advantage of CP for scheduling problems is to avoid an explicit enumeration of time, so if you need to enumerate time in the model (typically, if there is a large number of time slots) you will loose a part of this advantage.

Is it possible to compute the objective function you mention as the difference between the area of the intervals s minus the area of the intervals r on the cumul functions? Something like (I'm assuming the number of present employees is always more than or equal to the number of required ones and I'm using a unique cumul function):

dvar interval s[i in 1..n] ...; 
// Present employees 

int qs[i in 1..n] = ...; dvar interval r[j in 1..m] ...; 
// Required employees 

int qr[j in 1..m] = ...; cumulFunction nonWorkingEmployees = sum(i in 1..n) pulse(s[i], qs[i]) - sum(j in 1..m) pulse(r[j], qr[j]);   dexpr 

int objective = sum(i in 1..n) (qs[i]*lengthOf(s[i])) - sum(j in 1..m) (qr[j]*lengthOf(r[j]));   constraints
{ 0 <= nonWorkingEmployees; 
}

Of course the expression can be simplified if intervals in s (or in r) are fixed.
Philippe
#CPOptimizer
#DecisionOptimization

Originally posted by: LucaDiGaspero

Dear Philippe,

thanks for your prompt answer. First I give you some more details:

• In the model intervals s are fixed, while r are variables (s are the shifts, while r are employees breaks). Intervals r are contained in the overall union of s.
• There is no such constraint on the number of required/present employee (indeed this is a soft constraint that I would like to model as an objective function).
• The timeslot granularity is 5 minutes, whereas the length of the union of all s is about 7 hours (r, instead are 10-20 minutes long)

Concerning the model: I would need to post something like:

{code}
sum(t in timeslots) sum(i in 1..n) pulse(s[i], qs[i]) - sum(j in 1..m) pulse(r[j], qr[j])
{/code}

I.e. a summation over all the timeslots (or on a specific interval would be enough) of the values of the cumulative function.

Thanks in advance for your help.

Luca
#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

I'm probably missing something.
The expression you wrote:

sum(t in timeslots) sum(i in 1..n) pulse(s[i], qs[i]) - sum(j in 1..m) pulse(r[j], qr[j])

can be rewritten:

(sum(t in timeslots) sum(i in 1..n) pulse(s[i], qs[i])) - (sum(t in timeslots) sum(j in 1..m) pulse(r[j], qr[j]))

If the time-unit of the model is the same as the timeslots, we have:

(sum(t in timeslots) sum(i in 1..n) pulse(s[i], qs[i])) = sum(i in 1..n) lengthOf(s[i])*qs[i], and (sum(t in timeslots) sum(j in 1..m) pulse(r[j], qr[j])) = sum(j in 1..m) lengthOf(r[j])*qr[j]

So it is the expression I mentioned:

sum(i in 1..n) lengthOf(s[i])*qs[i] - sum(j in 1..m) lengthOf(r[j])*qr[j]

If you only want to compute the sum over some fixed intervals [tmin,tmax), you can use the overlapLength(x,tmin,tmax) expression that computes the length of the overlap between an interval variable x and a fixed interval:

sum(i in 1..n) overlapLength(s[i],tmin,tmax)*qs[i] - sum(j in 1..m) overlapLength(r[j],tmin,tmax)*qr[j]

Of course, as intervals s[i] are fixed in the above expressions, lengthOf(s[i]) and overlapLength(s[i],tmin,tmax) can be simplified to some constant.

Philippe
#CPOptimizer
#DecisionOptimization

Originally posted by: LucaDiGaspero

Actually I missed your solution :-)

Yes, the time-unit of the model is the same as the timeslots, therefore:

sum(i in 1..n) lengthOf(s[i])*qs[i] - sum(j in 1..m) lengthOf(r[j])*qr[j]

is exactly the expression I needed.

Thanks again!

Luca
#CPOptimizer
#DecisionOptimization