Originally posted by: Jazzi

Hello, I'm building a model of the shift assignment to the employees. In my case, there are different patterns of shifts with various duration and start/end time. Also there are different tasks for different qulifications. The employees have different labor contracts. i.e. the shifts with duration of 8 hours can be assigned to the full-time employees but not the part-time ones. It is preferable to use first the empolyees with full-time contracts beforing using the part-time ones. Besides an employees can perform serveral tasks during his shift.

I would like to minimize the both the total number of employees (or the total number of shift assignment) and the non-working time in the shifts. Therefore I design the following objective function:

// Which resource should be scheduled on that day
dvar interval roster[days][employees][shifts] optional;

// The idle time means the time during a shift when the employee doesn't work on any task
dvar int idle [days][employees][shifts];

// The objective is to maximize the total hours worked with less employees
// In other words, to minimize the total shift assignments
// plus to minimize the idle time within each shift assignment.
minimize sum(d in days, e in employees, s in shifts) min(d, e, s in presenceOf(roster[d][e][s])) idle[d][e][s];

Is it possible to fulfill these two goals at the same time?

Thank you!

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

Hi Jazzi

There is several issues about your model. I suppose the start and end date of the shifts are known. That is dates are not decision for your problem. So, you do not need interval variables in the model but only Boolean integer variables that represent the assignments of an employee to a shift. Am I right?

Second: you say

// The idle time means the time during a shift when the employee doesn't work on any task

That means there is a cost as soon as an employee does not work in a shift. I am not sure this is meaningful.

In any case the integer variable are Boolean that is with a 0..1 rage domain.

range Idle = 0..1;

dvar int idle [days][employees][shifts] in Idle

Last I think the objective should be:

minimize sum(d in days, e in employees, s in shifts) idle[d][e][s];

Hope that helps.

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Jazzi

Thank you for your answer. Yes, the start/end time of the shifts are known. I use "dvar interval roster[days][employees][shifts] optional" because I have also set some constraints as following: 

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

Hi Jazzy

I understand far better your problem which appears quite interesting.

Another question about the shifts: From your drawing the shifts can start at any time. For an actual worker its shift can start at any time in the day. If I am right, the model with interval variable is certainly required. In fact the most there is contiguity and recuperation rules for the workers or flexibilities in start dates and duration of the shifts, the strongest the scheduling aspect is dominating.

The operational interval variable represent the production of a worker in its shift of a day. That is an optional interval variable per worker and per day temporally constrained to be in a possible shifts of the day. use fordidStart and forbidEnd constraints to sate the set of start points

Then the interval variables are hierarchically grouped in alternative and span in order to cover the workload and state some continuity constraints from the manner the workforce  is managed.

Note you do not need Boolean integer variables as you can use the presenceOf(it) constraint on interval variable as Boolean expression. That is be itv1 and itv2 two interval variable, the constraint

presenceOf(itv1) + presenceOf(itv2) <= 1; // if itv1 is present, presenceOf(itv1) is 1  then presenceOf(itv2) is 0 then itv2 is absent.

Then you cumul all the shifts in order to cover the demand. Note that the demand curve should be a stepwise integer function: avoid having useless step for sake of efficiency.  Note the following code is only indicative as I am not completely sure understanding all the features of your problem.

tuple UserDemand {

int start;

int end;

int height;

};

UserDemands = ...;

int maxH = max (ud in UserDemands) ud.height;

cumulfunction cover = sum (d in Days, s in Shifts) tasks[d][s];

 

minimize sum(d in Days, s in Shifts) presenceOf(tasks[d][s]);

subject to {

forall(d in Days, s in Shifts)

alternative(tasks[d][s], all (w in Workers) pulse(opers[d][s][w], 1);

forall (ud in UserDenands)

alwaysIn(cover, ud.start, ud.end, ud.height, maxH);

}

I am not completely sure of the efficiency of the optimization procedure. Try it. In any case think adding redundant constraints. E.g from the curve you know the ending points of all tasks.

In fact, you know that the work will be organized by contiguous blocks of task whose few last (or few ones of) being of free duration, all the others are regular length shifts.

By pre-processing the demand curve you can have a lower and upper bound of the optimal number of blocks: in the example you give it is 6 or 7 blocks.

You can use it by modeling each block a set of unary resource.

 

int delta = ...; // to have some slack in the size of the block.

dvar interval blocks[b in Blocks] in b.star, b.end + delta] size delta + b.end - b.start optional b.surelyPresent

//Pre affecting the tasks to a block

cumulFunction cumulBlock[b in Blocks] = sum (t in Tasks; t.block == b ) pulse(task[t.day][t.shift], 1);

cumulfunction cover = sum (b in Blocks) pulse(blocks[b], 1);

//minimize the slack in a second order of magnitude (eps << 1)

minimize sum(d in Days, s in Shifts) presenceOf(tasks[d][s]) + eps*delta;

forall(b in Blocks) {

alwaysIn(cumulBlocks[b], blocks[b], 1, 1); // no idle time in a block

span(blocks[b], all (t in Tasks; t.block == b ) task[t.day][t.shift]);

}

 

You may also pre-ordering some task using temporal constraints.

 

Finally you can also having a decomposed model that may simplify your problem: e.g first ignoring the worker assignment. That is a model without the alternative of worker. Then a second model is essentially an assignment problem.

Another idea could be starting to search for a solution with only regular shift and use it as starting point of a second pone that exchange regular workers by non regular ones to adjust the blocks.

 

Hope that helps

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Matt_sev

Hi GCR,

I am a student in biomedical engineering and one of our projects this year is the scheduling of nurses in OR rooms. I stumbled upon this question and read your code which already helped me quite a lot in visualizing the problem. We were able to reduce our problem as follows:

"The objective of our project is to find the optimal shift combination to minimize the number of workers in one day (consists of 54 timeslots). There are three possible shifts types with different duration size: 32,42 and 50 timeslots.

Furthermore there are 54 timeslots in total and we know for each timeslot 1..54 the number of required workers for that timeslot (see attached excel file). The goal is thus to know how many shifts we need from each shift type to cover the required amount of workers for each timeslot, while minimizing the total number of shifts. In the end we would like to see a Gantt chart and outcome how many of each shift we need to minimize the total number of shifts."

I tried to relate my problem to your explanation, but I was unable to figure out how to write the cumulative function to keep track of the number of workers, so that they meet the required demands. I also tried out some coding, but it does not seem to work that well, I'm not quite sure how to solve this problem. I would be very gratefull for your help.

Thanks in advance for your time, 

Kind regards Matt_Sev

#DecisionOptimization
#OPLusingCPOptimizer