Python Shift Scheduling Optimization

Question

I am currently working on a shift scheduling algorithm for work. Our shift schedules consist entirely of either 4-3 (4 days on, 3 days off) and rotating 4-3's (Example: Sun, Mon, Tue, off one week and the next week and Sun, Fri, Sat off the next week) - weeks run from Sunday to Saturday.

There are 49 possible variations of either a "straight" 4-3 shift or a rotating 4-3. Since it's a 24/7 operation, all 7 days of the week need to be accounted for. As of right now, I am utilizing this for a smaller work group with 11 people on the early shift and 12 people on the late shift but there are other work groups with as many as 200 people that I would like to expand this algorithm to.

The basic premise is that the management group has a required manpower on each day and the algorithm will return only a set of early and late shifts that give them the required manpower.

It became painfully obvious very fast that arranging 49 possible shifts for 11 people (with repeats) and sorting through all those possible combinations would take thousands of years. As a result, I have been able to cull the list of 49 shifts down to about 16-20 of the most commonly used shifts.

That makes it manageable, but only for 11 or 12 people. Obviously, the number of possible combinations grows exponentially every time a person is added. As of right now, my algorithm does the following:

1. I have, as variables, a bunch of shifts with 1's and 0's representing "On Shift" and "Off Shift" for each day of the week they're there - over a two week period. I'll only use a sample for now.... For example:

   h = [0,1,1,1,1,0,0,0,1,1,1,1,0,0]
   e = [0,0,1,1,1,1,0,0,0,1,1,1,1,0]
   d = [0,0,0,1,1,1,1,0,0,0,1,1,1,1]
   c = [1,1,1,1,0,0,0,1,1,1,1,0,0,0]
   m = [0,1,1,0,1,1,0,0,1,1,0,1,1,0]
   p = [1,1,0,0,0,1,1,1,1,0,0,0,1,1]
   q1 = [1,1,1,0,0,0,1,1,1,1,0,0,0,1]
   a = [1,0,0,0,1,1,1,1,0,0,0,1,1,1]
   

I then have a list of about 16-20 (I'm only going to use 8 for this example) shifts that are the most commonly, if not exclusively used, plus a variable for the number of people it's going to calculate for and a variable for the manager's requirements (early_count):

shifts = [h,e,c,d,m,p,q1, a]
early_bid_personnel = 11
early_count = [5,6,7,7,6,8,5]

I then have a generator expression create all the possible shift combinations for the early shift and see if the Sundays add up to the required number (5). Those that do add up on Sundays are then referenced by the mon generator expression, all those Mondays are tabulated and then referenced by the Tue list. I do this over a fourteen day period - because some rotating shifts skew the balance of personnel on the second week:

sun = (combs for combs in combinations_with_replacement(shifts,early_bid_personnel) if (sum(combs[i][0] for i in range(0,early_bid_personnel)) == early_count[0]))
mon = (mon for mon in sun if (sum(mon[i][1] for i in range(0,early_bid_personnel)) == early_count[1]))
tue = (tue for tue in mon if (sum(tue[i][2] for i in range(0,early_bid_personnel)) == early_count[2]))
wed = (wed for wed in tue if (sum(wed[i][3] for i in range(0,early_bid_personnel)) == early_count[3]))
thu = (thu for thu in wed if (sum(thu[i][4] for i in range(0,early_bid_personnel)) == early_count[4]))
fri = (fri for fri in thu if (sum(fri[i][5] for i in range(0,early_bid_personnel)) == early_count[5]))
sat = (sat for sat in fri if (sum(sat[i][6] for i in range(0,early_bid_personnel)) == early_count[6]))
sec_sun = (sec_sun for sec_sun in sat if (sum(sec_sun[i][7] for i in range(0,early_bid_personnel)) == early_count[0]))
sec_mon = (sec_mon for sec_mon in sec_sun if (sum(sec_mon[i][8] for i in range(0,early_bid_personnel)) == early_count[1]))
sec_tue = (sec_tue for sec_tue in sec_mon if (sum(sec_tue[i][9] for i in range(0,early_bid_personnel)) == early_count[2]))
sec_wed = (sec_wed for sec_wed in sec_tue if (sum(sec_wed[i][10] for i in range(0,early_bid_personnel)) == early_count[3]))
sec_thu = (sec_thu for sec_thu in sec_wed if (sum(sec_thu[i][11] for i in range(0,early_bid_personnel)) == early_count[4]))
sec_fri = (sec_fri for sec_fri in sec_thu if (sum(sec_fri[i][12] for i in range(0,early_bid_personnel)) == early_count[5]))
sec_sat = (sec_sat for sec_sat in sec_fri if (sum(sec_sat[i][13] for i in range(0,early_bid_personnel)) == early_count[6]))

The sec_sat expression I iterate through, look up the string of 1's and 0's in a custom dictionary and convert that into the actual letter of the shift assignment. Then I basically do the exact same thing over again for the late shift. The two combined give the manager's the exact numbers they're looking for. That works just fine, for say, 11 people with only 8 shifts to choose from early and 12 people with 8 shifts late. But, if the size of the workgroup expands to, say, 20 people, and I want to use 12,14,16, or gasp all 49 shifts to make a shift determination, it is still pretty unreasonable.

I understand that the first generator expression is still checking each combination with replacement and only returning the ones in which Sundays add up and THAT is the core problem. I could seriously use some help figuring out a way to make this better than O(n^2) or worse.

Is there any way around me generating all possible combinations and checking each one? Also, if I put in some constraints in the initial generator expression, such as a maximum of only 5 'a' shifts:

sun = (combs for combs in combinations_with_replacement(shifts,early_bid_personnel) if (sum(combs[i][0] for i in range(0,early_bid_personnel)) == early_count[0]) and combs.count(a) <= 5)

The generator expression STILL has to generate something, check if it has 5 or less 'a' shifts and skip over it if it has more, correct?

Answer 1

You could use Monte Carlo simulations to solve this problem. You don't need to go through every combination possible. You just need to find one that meets the criteria, and there are many. Let me redifine your problem. Let be [sun, mon, tue, ..., sec_sat] your manager's requirement. [q1, q2, ..., q49] would be the number of people in each of the 49 different shifts. And the matrix:

s1[0]  s1[1] ... s1[13]
s2[0]  s2[1] ... s2[13]
....................
s49[0] s49[1] ... s49[13]

is the on/off table for every shift and every day of the week. For example: s1[0] would be 1 if Sunday is an on day for shift 1, or zero otherwise. s3[7] would be 1 if second Sunday is an on day for shift 3, or zero otherwise. And so on and so forth. With this definitions your problem could be rewritten this way:

sun       <=  q1*s1[0] + ... +  q49*s49[0]
mon       <=  q1*s1[1] + ... + q49*s49[1]
tue       <=  q1*s1[2] + ... + q49*s49[2]
wed       <=  q1*s1[3] + ... + q49*s49[3]
thu       <=  q1*s1[4] + ... + q49*s49[4]
fri       <=  q1*s1[5] + ... + q49*s49[5]
sat       <=  q1*s1[6] + ... + q49*s49[6]
sec_sun   <=  q1*s1[7] + ... + q49*s49[7]
sec_mon   <=  q1*s1[8] + ... + q49*s49[8]
sec_tue   <=  q1*s1[9] + ... + q49*s49[9]
sec_wed   <=  q1*s1[10] + ... + q49*s49[10]
sec_thu   <=  q1*s1[11] + ... + q49*s49[11]
sec_fri   <=  q1*s1[12] + ... + q49*s49[12]
sec_sat   <=  q1*s1[13] + ... + q49*s49[13]

Your unknown is [q1, q2, ..., q49]. The rest is known. How to use simulations to find a solution? You would generate random [q1,...,q49] vectors and check if your criteria is met. If it is, you break the algorithm and return the result. For example (sort of pseudo code):

import random
# Define your restrictions
mon = 
tue = 
.........
sec_sat = 
# Define your shifts
s1 = [1,1,1,1,0,0,0,1,1,1,1,0,0,0]
s2 = [0,1,1,1,1,0,0,0,1,1,1,1,0,0]
...................................
s49 = [...]
while True:
    q = [0]*49
    # We place workers in random shifts
    for i in range(number_of_workers):
        q[random.randint(0,len(q)-1)] += 1

    if (mon <= q[0]*s1[0] + q[1]*s2[0] + ... + q[48]*s49[0]) and
       (tue <= q[0]*s1[1] + q[1]*s2[1] + ... + q[48]*s49[1]) and         
       .........................................................
       (sec_sat <= q[0]*s1[13] + q[1]*s2[13] + ... + q[48]*s49[13]):
       # Condition met, return result
       return q

I implemented a solution for your example above with a restricted number of shifts:

import random
# Restrictions
r = [5, 6, 7, 7, 6, 8, 5, 5, 6, 7, 7, 6, 8, 5]
# Shifts
s = []
s.append([0,1,1,1,1,0,0,0,1,1,1,1,0,0])
s.append([0,0,1,1,1,1,0,0,0,1,1,1,1,0])
s.append([0,0,0,1,1,1,1,0,0,0,1,1,1,1])
s.append([1,1,1,1,0,0,0,1,1,1,1,0,0,0])
s.append([0,1,1,0,1,1,0,0,1,1,0,1,1,0])
s.append([1,1,0,0,0,1,1,1,1,0,0,0,1,1])
s.append([1,1,1,0,0,0,1,1,1,1,0,0,0,1])
s.append([1,0,0,0,1,1,1,1,0,0,0,1,1,1])

number_of_shifts = len(s)
number_of_workers = 11
number_of_days = len(s[0])

while True:
    q = [0]*number_of_shifts
    for i in range(number_of_workers):
        q[random.randint(0,len(q)-1)] += 1
    t = [sum([q[j]*s[j][i] for j in range(number_of_shifts)]) for i in range(number_of_days)]
    if sum([r[i] <= t[i] for i in range(number_of_days)]) == number_of_days:
        print q
        break

It didn't take much to execute. This is one of the solutions it found: [0, 3, 2, 2, 1, 2, 1, 0]