1
$\begingroup$

I am working on a employee scheduling problems (assigning shifts to temporary workers) by modeling it as a MIP. There is a one shift per day constraint for the employees. There are overnight shifts and need to take care of the day boundaries and employee rest periods -- for example an employee working between 8pm on a day till 2am the next day can not start their shift the next day without having a rest time of x hours. So in summary, there are overlapping shifts and need to choose a single shift from the set of overlapping shifts. There can be multiple such overlapping groups for a single employee. We have modeled it as mutual exclusive constraints (sum of all variables in an overlap group can be at most one). But the problem is that in certain cases,the number of variables in such constraints is quite big (1000+) and these are all binary variables. So the problem is getting hard to solve pretty fast. I wanted to know if there is any other way to model this or can we simplify in any way. Thank you.

$\endgroup$
2
  • $\begingroup$ Cross-posted: math.stackexchange.com/questions/4812413/… $\endgroup$
    – RobPratt
    Nov 22, 2023 at 23:19
  • $\begingroup$ Sorry, I did not know both or and math stackexchange are accessible by both communities. I will take care of this going forward. $\endgroup$
    – SDC
    Nov 23, 2023 at 20:06

2 Answers 2

2
$\begingroup$

Consider a side-constrained network formulation in which you have a node for each employee-day-shift and a directed arc if the employees are the same, the days are consecutive, and the shifts do not overlap. You will also need for each employee a dummy source node and a dummy sink node. Now for each employee you want to find a directed source-sink path, which by construction of the network will visit each day exactly once. So far, this is a pure network problem for each employee, but you presumably also have side constraints across employees so each day-shift has enough employees to cover the demand.

$\endgroup$
26
  • $\begingroup$ Thanks. I am using Gurobi to solve our scheduling MIP. I am not sure how to fit this network formulation into a MIP model. As you pointed out correctly there are other side constraints like demand coverage, employee min/max daily/weekly hours, consistency of shifts, and so on. $\endgroup$
    – SDC
    Nov 22, 2023 at 20:15
  • $\begingroup$ You will need a binary decision variable for each arc and a “flow balance” equality constraint for each node. $\endgroup$
    – RobPratt
    Nov 22, 2023 at 20:19
  • $\begingroup$ My current model has employee-shift binary variables. With these network problem related constraints I will have to introduce binary variables for all the arcs. So looks like will have to introduce these new binary variables in lieu of the original employee-shift binary variables. So now all other constraints like demand coverage, minimum weekly hours, etc. will be defined in terms of these arc binary variables.Is that correct? Also, I am trying to understand why this formulation is better than the original formulation with mutually exclusive variables for non overlapping shifts. $\endgroup$
    – SDC
    Nov 26, 2023 at 21:16
  • $\begingroup$ You can link the original variables to the arc variables via equality constraints. A pure network problem would have the total unimodularity property and hence require no branching. If you have only a small percentage of side constraints, the resulting branch-and-cut tree can often still be small. $\endgroup$
    – RobPratt
    Nov 26, 2023 at 21:23
  • $\begingroup$ So performancewise is there any difference between removing the original variables and formulating everything using only the arc variables vs keeping the originals and linking them to the arc variables? From the implementation perspective retaining original variables might be easier and faster. $\endgroup$
    – SDC
    Nov 28, 2023 at 3:25
0
$\begingroup$

We typically handle "overlapping shifts", "minimum X hours between two shifts" and/or "one shift per day" as separate constraints. This is because in some cases they aren't always all hard constraints. Some of them can be soft constraints with a heavy weight.

We avoid binary variables by given each shift a variable to hold an employee, instead of creating a variable for each shift-employee combination. So if there are 1000 shifts and 200 employees, there are 1000 variables with 200 values. Not 200 000 variables with 2 values. That's a huge difference in search space (200^1000 ~ 2^8000 versus 2^200000).

For what it's worth, here's an implementation of those constraints in Timefold (not a MIP solver):

Constraint noOverlappingShifts(ConstraintFactory constraintFactory) {
    return constraintFactory.forEachUniquePair(Shift.class, 
                    Joiners.equal(Shift::getEmployee),
                    Joiners.overlapping(Shift::getStart, Shift::getEnd))
            .penalize(HardSoftScore.ONE_HARD,
                    EmployeeSchedulingConstraintProvider::getMinuteOverlap)
            .asConstraint("Overlapping shift");
}

Constraint atLeast10HoursBetweenTwoShifts(ConstraintFactory constraintFactory) {
    return constraintFactory.forEachUniquePair(Shift.class,
                    Joiners.equal(Shift::getEmployee),
                    Joiners.lessThanOrEqual(Shift::getEnd, Shift::getStart))
            .filter((firstShift, secondShift) -> Duration.between(firstShift.getEnd(), secondShift.getStart()).toHours() < 10)
            .penalize(HardSoftScore.ONE_HARD,
                    (firstShift, secondShift) -> {
                        int breakLength = (int) Duration.between(firstShift.getEnd(), secondShift.getStart()).toMinutes();
                        return (10 * 60) - breakLength;
                    })
            .asConstraint("At least 10 hours between 2 shifts");
}
$\endgroup$
2
  • $\begingroup$ Thank you. For us constraint programming is not on table so need to think about simplifying the MIP model only. I think your variable creation also works better for a CP model, but not sure if it would have the same advantage for a MIP. In fact I think having shift-employee binary variables seems a better approach for a MIP? $\endgroup$
    – SDC
    Nov 23, 2023 at 19:59
  • $\begingroup$ We use metaheuristics instead of CP, but some principles are the same. Yes, for a MIP approach, binary variables make sense. $\endgroup$ Nov 24, 2023 at 20:26

Your Answer

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

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