Constraint programming in OPL: intervals covering time slots

I am trying to model the following: There is a shop open from xx AM to yy PM. In each 30 min time slot, there have to be demand[timeSlot] = x employees present.

E.g. the shop is open from 08am to 10am. Then there are the slots 8am-08:30, 08:30-09:00, 09:00-09:30 and 09:30-10:00 with demand = [1,2,2,1].

I have a set of employees. For each employee, I want to represent their working time with an interval decision variable: dvar interval x[e in Employees] optional size 4..8

My problem now is formulating the constraint that in each time slot, the demand for employees must be met. How can I match the intervals (having start and end time) with the coverage of the time slot?

The constraint should be like this:

sum(e in Employees, x[e] covers time slot s) x[e] >= demand[s], for all time slots s

For example, in the time slot 09:00-09:30, two employees have to be present. So I need at least to decision variable intervals, which each have a starting time smaller or equal than 09:00 and endTime greater or equal than 09:30.

Anyone understand what I am trying to do and maybe have some hint or the solution?

Thanks a lot!

• Hi, welcome to OR.SE! If I understand correctly, you know on beforehand the times at which every employee will (be available to) work? In that case, you could create a boolean parameter C(e,s) to represent if the working time of employee covers the desired slot, e.g. C(e,s) = 1 if employee e's working time covers time slot s (and C(e,s)=0 otherwise). Then, you can represent the demand constraint by using a sum of products of C[e,s]*x[e]. Mar 16, 2020 at 21:37
• Hi, thanks for your comment! The problem is that I don't know beforehand the times at which an employe will work. E.g. the shop is open from 08am to 8pm. The employee has to work between x and y hours while the shop is open. E.g. x = 6 and y = 8 so there are countless options for the employee's working time(8am-2pm, 8am-3pm, 8am-4pm,9am-3pm, 2pm-8pm, ...). Fractional working times like 10:30am to 4:30pm are allowed. There is the possibility that the employee doesn't work at all if x=y=0. In conclusion I can't use a boolean parameter to represent if an employee covers the desired slot. Mar 18, 2020 at 16:05
• My comment was too long: Somehow I need to link the time the optional interval spans with the time slots. In logical constraint: startingTime(x)=10am and endTime(x)=4pm ==> covered[s] = 1 for all s in [10am,4pm] Mar 18, 2020 at 16:08
• can an employee work multiple times like from 8 am to 2 pm and 4 pm to 8 pm?
– ooo
Mar 20, 2020 at 12:09
• No, an employee can only work once per day. Mar 21, 2020 at 12:56

within CPOptimizer scheduling, you could use cumul functions:

using CP;

int xx=8*2;
int yy=17*2; // time unit is 30 minutes

{string} Employees={"A","B","C","D","E","F"};

tuple demand
{
key int time;
int d; // demand
}

{demand} demands={<8*2,1>,<8*2+1,2>,<9*2,2>,<9*2+1,1>};

dvar interval it_x[e in Employees] optional in xx..yy+1  size 8..16;

cumulFunction cumulWork=
sum(e in Employees) pulse(it_x[e],1);

// minimize nbr of employees we need to call
minimize sum(e in Employees) presenceOf(it_x[e]);
subject to
{
forall(d in demands) alwaysIn(cumulWork,d.time,d.time+2,d.d,1000);
}


which will call 2 employees

And you will see the gantt for employees and the graph for cumulWork.

• This is what I was looking for. I was not familiar with the alwaysIn function. Thank you! Mar 21, 2020 at 12:54