1
$\begingroup$

Suppose we have an office with $n$ employees and we want to make a planning for the upcoming $T$ weeks. In each week there are $m_t, t\in \{1, 2, \ldots, T\},$ jobs to do.

Each employee can give a top three preferred jobs for each week. When there are no further constraints and $n = m_t$ one can easily solve this by the Hungarian algorithm.

However, I have some constraints:
1 - Each employee gets at least once a first choice.
2 - Each employee only gets preferred jobs.
3 - If the same job appears in several weeks, a employee can only be assigned once to this job
4 - Each job is done by at least $min_i$ employees and by at most $max_i$ employees. So these bounds can differ per job.

Furthermore, some employees do not have a preference and can be assigned to each job.

It is not that hard to model this as a MIP and solve it for example in AIMMS (AIMMS only needs less than a second). However, I want to solve it in C++11 without a 'black box' library to increase my knowledge of the problem and therefore I need to come up with the algorithm myself. My first thought was to solve it with a Branch-and-bound. However, I'm afraid that this will take too long since in the given instance we have $n \approx 450$, $m_t \approx 25$ $\forall t$, $min_i \approx 18$, $max_i = 22$, and $T = 3$. Assuming that each employee has three preferences this lead to a tree with $(T\cdot n)^{\# preferences} = (3\cdot 450)^3$ nodes, where the power is only three and not 25 due to the second constraint.

Does anyone know an algorithm to solve this problem? Or will a branch-and-bound be an option? But then the question arises, which bound to use?

Furthermore, I know that there is a feasible solution for my current instance. But is there a way to check this in advance?

Thanks in advance

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.