Shift Organization algorithms (Constraint Programming + Marriage problem)

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)

• 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.
– D.W.
Feb 17 '18 at 19:17
• 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. Feb 19 '18 at 12:59