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)
Turns out this problem is pretty hard to solve and is still under active research. This paper (2004) describes the state of the art.