Python 类次调度优化

Question

我目前正在研究一种工作轮类调度算法。我们的轮类时间表完全包括 4-3(4 天上类，3 天休息)和 4-3 轮换(例如:周日、周一、周二，一周和下周休息，周日、周五、周六休息) - 星期从星期日到星期六。

“直接”4-3 换档或旋转 4-3 有 49 种可能的变体。由于它是 7 天 24 小时运行，因此一周中的所有 7 天都需要考虑在内。截至目前，我正在将此算法用于一个较小的工作组，该工作组有 11 人早类和 12 人晚类，但我想将此算法扩展到其他多达 200 人的工作组。

基本前提是管理组每天都有所需的人手，算法将只返回一组早类和晚类，为他们提供所需的人手。

很明显，为 11 个人安排 49 次可能的轮类(重复)并整理所有这些可能的组合将需要数千年的时间，这一点很快变得非常痛苦。因此，我已经能够从 49 个类次列表中筛选出大约 16-20 个最常用的类次。

这使得它易于管理，但仅适用于 11 或 12 人。显然，每增加一个人，可能的组合数量就会呈指数级增长。截至目前，我的算法执行以下操作:

1. 作为变量，我有一堆类次，其中 1 和 0 代表一周中的每一天的“轮类”和“下类” - 在两周的时间段内。我现在只使用一个示例....例如:

   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]
   

然后我有一个列表，其中包含大约 16-20 个(在这个例子中我只打算使用 8 个)轮类，这些轮类是最常见的，如果不是专门使用的话，加上一个用于计算人数的变量for 和经理要求的变量(early_count):

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

然后我用一个生成器表达式为早类创建所有可能的类次组合，并查看星期日加起来是否达到所需数量 (5)。那些确实在星期天加起来的，然后由 mon 生成器表达式引用，所有这些星期一被制成表格，然后由 Tue 列表引用。我在 14 天的时间内执行此操作 - 因为一些轮类会在第二周扭曲人员平衡:

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]))

我遍历的 sec_sat 表达式，在自定义字典中查找 1 和 0 的字符串，并将其转换为移位赋值的实际字母。然后我基本上为晚类再做同样的事情。两者结合起来可以为经理提供他们正在寻找的确切数字。这很好用，例如，11 个人只有 8 个类次可供选择，而 12 个人有 8 个类次可供选择。但是，如果工作组规模扩大到，比如说20个人，我想用12、14、16，或者gasp全部49个类次来决定类次，还是很不合理的.

我知道第一个生成器表达式仍在用替换检查每个组合，只返回星期日相加的组合，这是核心问题。我可以认真地使用一些帮助来找出一种比 O(n^2) 或更糟的方法。

有没有办法生成所有可能的组合并检查每个组合？此外，如果我在初始生成器表达式中加入一些约束，例如最多只有 5 个“a”类次:

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)

生成器表达式仍然必须生成一些东西，检查它是否有 5 个或更少的 'a' 移位，如果有更多则跳过它，对吗？

Answer 1

您可以使用蒙特卡罗模拟来解决这个问题。您不需要遍历所有可能的组合。您只需要找到符合条件的即可，而且有很多。让我重新定义你的问题。让 [星期日、星期一、星期二、...、sec_sat] 您经理的要求。 [q1, q2, ..., q49] 将是 49 个不同类次中每个类次的人数。和矩阵:

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

是每个类次和一周中每一天的开/关表。例如:如果星期日是类次 1 的上类日，s1[0] 将为 1，否则为零。如果第二个星期日是类次 3 的上类日，s3[7] 将为 1，否则为零。等等等等。使用此定义，您的问题可以这样重写:

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]

您的未知数是[q1, q2, ..., q49]。其余的是众所周知的。如何使用模拟来找到解决方案？您将生成随机 [q1,...,q49] 向量并检查是否满足您的条件。如果是，则破坏算法并返回结果。例如(某种伪代码):

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

我为您上面的示例实现了一个解决方案，但类次数量有限:

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

执行起来并不费力。这是它找到的解决方案之一:[0, 3, 2, 2, 1, 2, 1, 0]