4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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]. $\endgroup$ – dhasson Mar 16 at 21:37
  • $\begingroup$ 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. $\endgroup$ – ORspecialist Mar 18 at 16:05
  • $\begingroup$ 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] $\endgroup$ – ORspecialist Mar 18 at 16:08
  • $\begingroup$ can an employee work multiple times like from 8 am to 2 pm and 4 pm to 8 pm? $\endgroup$ – anoop Mar 20 at 12:09
  • $\begingroup$ No, an employee can only work once per day. $\endgroup$ – ORspecialist Mar 21 at 12:56
3
$\begingroup$

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.

gantt for employees

cumul work graph

| improve this answer | |
$\endgroup$
  • $\begingroup$ This is what I was looking for. I was not familiar with the alwaysIn function. Thank you! $\endgroup$ – ORspecialist Mar 21 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.