1
$\begingroup$

I want to assign people to cover shifts considering a set of constraints and preferences. Here's the problem definition:

Daily shifts must be covered by workers, who are divided in three groups:

  • Trainees (Nt = 2)
  • Regulars (Nr = 3)
  • Experts (Ne = 7)

The organization constraints are:

  • All shifts must be covered
  • A Trainee must always cover a shift with an Expert
  • Workers covering Friday must also cover Sunday
  • Nobody can cover two shifts in a row
  • Nobody works more than M shifts every D days

The process should maximize the following output:

  • Workers get shifts assigned based on their preference
  • Experts work as less as possible, only covering unassigned gaps
  • Number of shifts are evenly distributed

My initial idea is to write a branch and bound algorithm to generate all possible combinations allowed by the constraints. I would then score each solution for each worker based on their preferences, and run a marriage algorithm to get the best combination.

The main problem is that the number of combinations is too (damn) high. Without constraints, there would be 6**30 (~1e24) possible arrangements. I know most of these will be bound, but currently I'm generating at a pace of ~1e8/minute.

I'm wondering if there are any heuristics I could apply to improve the process. Any ideas here? How does this whole thing sound?

Thanks!

Sample code to generate combinations:

def get_combinations(population, base, spots):
    if len(base) == spots:
        yield base
        return

    for candidate in population:
        combo = base + (candidate, )

        if is_viable(combo, population, spots):
            yield from get_combinations(population, combo, spots)

population = {'t1', 't2', 'n1', 'n2', 'n3'}
get_combinations(population, tuple(), 30)
Improve this question
$\endgroup$
2
  • $\begingroup$ Rather than implementing branch-and-bound yourself, I suggest you formulate this as an integer linear programming instance (or a SAT instance) and try applying an off-the-shelf ILP/SAT solver to see if they can find a solution for you. They implement multiple techniques and heuristics that are probably beyond what anyone on person could reasonably be expected to implement on their own. $\endgroup$
    – D.W. ♦
    Feb 17, 2018 at 19:17
  • $\begingroup$ Thanks @D.W. that's exactly what I've been investigating, I'll try to solve a simpler version following this approach! For what is worth, looks like some of the real-world constraints of this problem makes finding an optimal solution impossible. $\endgroup$
    – jminuscula
    Feb 19, 2018 at 12:59

1 Answer 1

Reset to default
1
$\begingroup$

Turns out this problem is pretty hard to solve and is still under active research. This paper (2004) describes the state of the art.

Improve this answer
$\endgroup$

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.