How to efficiently and quickly find valid combinations out of an array of string elements for employee scheduling?

Question

I am working on a project where very specific scheduling is needed (and why I am not using a library). It works, but I am trying to find a faster solution to the following problem:

We have employees requesting hours every week. They input their total availability for the week (ex: 8-1 M,W,R). They all must work 10 hours per week, and each shift has to be at least 2 continuous hours. (All shifts are continuous, no breaks in between).

For example, employee 1 says availability is: 8-3 M,W,R,F: he can be scheduled for 3 hours on M, 3 hours on W, and 2 on F, or any other combination (such as 4,4,2; 2,2,4 etc.). The problem is trying to find these combinations. Right now I store their availability as a semi-colon separated string (etc: 8,9,10,11,12,1;8,9,10,11,12,1;8,9,10;;8,9 would be hours for each day (5 days)) I separate these during my scheduling into an array, and then this is the hard part for me:

I want to be able to determine combinations of these hours where each combination has at least 2 hours for each day, where all hours are continuous, and 10 total hours are selected. Right now, my solution is very brute force.

I use itertools combinations. I take their availability, and for each day append the letter of that corresponding day to it and put into one array. So the example 8,9,10,11;8,9;;8,9,10,11; becomes [m8,m9,m10,m11,t8,t9,r8,r9,r10,r11]

Then I use the itertools combination to look through all combinations of this array, and have a function that reads through to see if each day has continuous hours, at least 2 hour shifts, and a total of 10 hours (or other number of hours, this can change).

This is a very slow process because is someone has availability 8-5 M-F they can have lots of combinations that do and don't work. (Reason I need to test all is because we have 100+ employees filling similar roles, and if one role is taken, another employee cannot be scheduled at that time)

Example of how I do it now.

    # let availability be the string of availability 
    availability = "8,9,10,11;8,9;;8,9,10,11;"
    poss_times = availability.split(";")
    # where I put into one array with each day letter in front
    sched=[]
    sched.extend(["m" + day for day in list(filter(None,poss_times[0].split(",")))])
    sched.extend(["t" + day for day in list(filter(None,poss_times[1].split(",")))])
    sched.extend(["w" + day for day in list(filter(None,poss_times[2].split(",")))])
    sched.extend(["r" + day for day in list(filter(None,poss_times[3].split(",")))])
    sched.extend(["f" + day for day in list(filter(None,poss_times[4].split(",")))])
    sched.extend(["s" + day for day in list(filter(None,poss_times[5].split(",")))])
    sched.extend(["u" + day for day in list(filter(None,poss_times[6].split(",")))])

    for poss_combination in itertools.combinations(sched, 10):
        # check if the combination fulfills the requirements, and if so continue to see if it is possible to schedule that employee

I am hoping there might be a faster, more elegant solution that can speed up the process. Thank you for any help.

Answer 1

I think this is an example of the famous Nurse scheduling problem. This problem is NP-hard, i.e. to find an optimal solution you had to create all possible combinations of assignments, and select one that fits best. Since this is of exponential time complexity, it is only feasible for small problems, and yours is apparently already too large.
If you only want to find a reasonable (not the optimal) solution, one could apply general-purpose stochastic algorithms, as they are cited in the Wiki post mentioned above, e.g. stochastic optimization, genetic algorithms, and simulated annealing. But such methods have typically long computation times.
Anyway, here is an example where the Nurse scheduling problem is solved by a Genetic Algorithm. Maybe you can try to adopt it to your problem, and check whether it improves your situation.