0
$\begingroup$

I have the following problem which I have been asked to solve. I like to think that a few years ago, I'd be able to do it myself, but these days I must admit that help is good :)

Given $n$ employees $E = \{e_1,\ldots,e_n\}$, an organisation wants to construct a plan for the next $w$ weeks: each week, $k<n$ employees must be chosen to be on a specific duty in a team.

For each employee $e_i$, we would like to maximize the time between any two consecutive weeks that $e_i$ is on duty. This goes for all $i$, so it should be fair in the sense that no employee is favored.

Further, we would like to have as diverse teams as possible, so for any $1 \leq i,j \leq n$, we would like to minimize the number of times $e_i$ and $e_j$ are on the same team.

As an additional hiccup, $m<n$ of the employees are not available from the beginning, so let's say that employees $\{e_i \mid 1 \leq i \leq m\}$ are only available from week $q_i$ onwards. These $m$ employees should not be "punished" in the sense that they have to make up for work they "missed" when they were not yet employed.

Any ideas and tips on how to model this, e.g. as a MIP would be great!

As a concrete example, $n=17$, $w=17$, $k=3$ and $m=4$ where $q_1=q_2=q_3=5$ and $q_4=9$.

Edit: I want to add that this is not a homework question, but a real life problem. There is no mathematically stringent way to pose my constraints; this is up to interpretation, as is how the constraints should combine and weigh against each other in an objective function. In this lies the heart of my question. As some approaches may be a lot simpler than others, I am willing to sacrifice some stringency in return of a simpler problem/model.

$\endgroup$
  • $\begingroup$ I think you need to think more about your question formulation first. I don't see a single objective function you want to minimize. If you want to minimize the time-between-weeks for all employees, that is $n$ different objective functions, and minimizing the number for one employee might increase the number for a different one. Then you also add the goal of having teams as diverse as possible. Well, you'll need a way to identify a single objective function that you want to minimize, which captures how you want to trade off between those goals. $\endgroup$ – D.W. Feb 16 '18 at 20:02
  • $\begingroup$ Anyway, once you've figured that out, cs.stackexchange.com/q/12102/755 has techniques that may be helpful here. $\endgroup$ – D.W. Feb 16 '18 at 20:07
  • $\begingroup$ Hi @D.W. Thanks for your comments. The goal of incorporating my requirements into a meaningful single objective function is what I'm asking for help with. I apologize if that was unclear. I realize that my goals are themselves not clearly defined, in the sense that I did not specify e.g. how bad it would be to share team with 2 previous members compared to just 1 would be, let alone how the frequency constraint weighs against the diversity constraint. As this is not a homework question, but a real life problem, these are up for interpretation. $\endgroup$ – Martin Lauridsen Feb 19 '18 at 7:13
  • $\begingroup$ Further, some approaches may be a lot simpler than others. I think we're willing to trade off quite some stringency on the constraints in offer for simplicity of the problem/model. $\endgroup$ – Martin Lauridsen Feb 19 '18 at 7:14
  • $\begingroup$ OK. I don't think we can do that for you. That requires figuring out how you want to trade off these different goals, and we can't make that decision for you. Only you know what you'll consider meaningful. $\endgroup$ – D.W. Feb 19 '18 at 12:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.