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!

Improve this question
$\endgroup$
5
  • $\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, 2020 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, 2020 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, 2020 at 16:08
  • $\begingroup$ can an employee work multiple times like from 8 am to 2 pm and 4 pm to 8 pm? $\endgroup$
    – ooo
    Mar 20, 2020 at 12:09
  • $\begingroup$ No, an employee can only work once per day. $\endgroup$
    – ORspecialist
    Mar 21, 2020 at 12:56

1 Answer 1

Reset to default
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$
1
  • $\begingroup$ This is what I was looking for. I was not familiar with the alwaysIn function. Thank you! $\endgroup$
    – ORspecialist
    Mar 21, 2020 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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