0
$\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 that restricts more than one shift per day. While doing that we have overnight shifts and need to take care of the day boundaries -- 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. 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$
1

1 Answer 1

1
$\begingroup$

It will depend a bit on what language you're modelling in and what solver you're using. Some languages are designed for this kind of problem, for example in MiniZinc there are scheduling constraints so that you can directly specify that certain resources cannot be allocated to overlapping tasks or shifts (and you can incorporate rest times into those constraints as well).

If you don't have access to that kind of constraint, then you will have to find other ways to implement them, and unfortunately they are going to involve a lot of variables because scheduling is a complicated problem. One way to improve the efficiency of the program may be to add some redundant constraints - that is, introduce constraints that are already logically implied by the model that may help the solver to eliminate bad solutions more quickly. This might involve, for example, tightly bounding the total number of hours worked by all employees across all shifts.

$\endgroup$
2
  • $\begingroup$ Thank you. We are using Gurobi to solve the MIP. As you said, scheduling is hard and solving it as a MIP makes it a huge problem with a lot of variables and constraints. I thought adding redundant constraints as you suggested may not work as the presolve phase will remove those? $\endgroup$
    – SDC
    Nov 23, 2023 at 20:04
  • $\begingroup$ It depends a little on how the constraints are structured. If they're just rearrangements of the existing constraints then they'll probably get removed, but if they involve some steps of logic from knowledge of the overall problem they can sometimes help. The MiniZinc manual gives an example, but there is probably better discussion of the topic elsewhere. $\endgroup$
    – ConMan
    Nov 23, 2023 at 22:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .