Python移位调度优化

Question

我目前正在为工作制定一种轮班调度算法。我们的轮班安排完全包括4-3天(4天休息，3天休假)和4-3周轮班(例如:太阳、星期一、图伊，一周休息一周，下一周休息，太阳，星期五休息)--每周从周日到周六。

有49种可能变化的“直”4-3位移或旋转4-3。因为这是一次24/7的手术，所以每周的7天都需要计算。到目前为止，我正在为一个较小的工作组使用这个工具，其中11人在早班，12人在晚班，但还有其他有多达200人的工作组，我想把这个算法扩展到。

基本的前提是，管理小组每天都有所需的人力，而算法只会返回一组早班和晚班，从而为他们提供所需的人力。

很明显，为11个人安排49个可能的轮班(带重复)并对所有这些可能的组合进行排序需要数千年的时间，这一点非常明显。因此，我已经能够筛选出49种轮班的名单，减少到16到20种最常用的班次。

这使得它易于管理，但只适用于11或12个人。显然，每次添加一个人时，可能的组合数都会成倍增长。到目前为止，我的算法做了以下工作：

1. 作为变量，在每周的每一天，我都有一组1和0的轮班，代表“换班”和“下班”--为期两周。我现在只用一个样本..。例如： H=0，1，1，1，1，0，0，1，1，1，0，0，0，1，1，0d=0，0，1，1，1，0，0，1，1，1，c=1，1，1，1，1，1，c=1，1，1，1，1，1，1，0，0 m=0，1，1，1，1，1，1，1，0，1，1，1，0，1，0，1，1，1，1，1，0，0，1，1，1，1，1，0，0，1，1，0，1，1，0，1，1，0，1，1，0，1，1,000，0，0，1，1,000，0，1，1,000，0，1，0，1，1，0，1，0，1，0，1，0，1，0，1,000，0，0，1，1，1，0，1，0，0，0，1，1，1，1，0，

然后，我有一个大约16到20的列表(本例中只使用8)，这些移位是最常用的，如果不是专用的话，再加上要计算的人员数量的变量和经理需求的变量(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，或喘息所有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

你可以用蒙特卡罗模拟来解决这个问题。你不需要经过所有可能的组合。你只需要找到一个符合标准，而且有很多。让我再解释一下你的问题。sun，mon，tue，.，sec_sat您的经理的要求。q1，q2，.，q49将是49种不同轮班中每一班的人数。以及矩阵：

s1 s11 ..。s113 s2 s21 .s213 .s49 s491 ..。s4913

是一周中每班和每一天的开/关桌。例如:如果星期日是换班1的一天，则s1为1，否则为零。如果第二个星期日是换班3的一天，s37将是1，否则为零。以此类推。有了这些定义，您的问题可以用以下方式重写：

sun <= q1*s1 ++ q49*s49 mon <= q1*s11 +.+q49*s 491 tue <= q1*s12 +.+q49*s 492结婚<= q1*s13 +.+q49*s 493清华<= q1*s14 +…+q49*s 494 fri <= q1*s15 +.+q49*s 495 sat <= q1*s16 +.+q 49*s 496 sec_sun <= q1*s17++Q49*s 497 sec_mon <= q1*s18 ++Q49*s 498 sec_tue <= q1*s19 +.+Q49*s 499 sec_wed <= Q1*S 110++Q49*s 4910 sec_thu <= Q1*s 111++Q49*s 4911 sec_fri <= Q1*s 112+.+Q49*s 4912 sec_sat <= Q1*s 113+Q49*s 4913

你不知道的是q1，q2，.，q49。其余的都知道了。如何使用模拟来找到一个解决方案？您将生成随机的q1，.，q49向量，并检查您的条件是否满足。如果是，则破坏算法并返回结果。例如(某种伪代码)：

导入随机#定义您的限制mon = tue =.sec_sat =#定义您的班次s1 =1，1，1，1，0，0，1，1，1，0，0 s2 =0，1，1，1，0，0，1，1，1，1，0，0，1，1，1，0，0.s49 =。当True: Q= *49 #时，我们将工作人员随机移到I在范围内(Number_of_workers)：qrandom.randint(0，len(q)-1) += 1 if (mon <= q*s1 + q1*s2 +.+ q48*s49)和(tue <= q*s11 + q1*s21 +.+ q48*s491)和<=(sec_sat <= q*s 113+q1*s 213+.+q48*s 4913)：满足#条件，返回结果返回q

我为上面的示例实现了一个解决方案，其轮班次数有限：

进口随机#限制r= 5、6、7、7、6、8、5、5、6、7、7、6、8、5#移位s= [] s.append(0，1，1，1，0，0，1，1，1，1，0)s.append(0，0，1，1，1，0，0，0，1，1，1，0，0，0，1，1，1，0)s.append(0，0，0，1，1，1，1，0，0，0，0，0，0，0，0，0，0，1，1，1，0，0，1，1，0，1，1，0，1，0，1，1，1，1，1，1，1，1，1，1，1，1，1，1，0，1，0，1，1，0，1，1，0，0，1，1，1，1，0，1，1，0，0，1，1，1，1，0)s.append(0，0，0S.append(1，1，0，0，0，0，0，1，0，1，0，1，1，1，0，0，1，1，1，0，1，1,0) s.append(1，1，0，0，1，1，0)s.append(1，0，0，1，1，0，0，1，1，1) number_of_shifts = len(s) number_of_workers = 11 number_of_days = len(s)，而True: Q= *number_of_shifts for I in range(number_of_workers)：qrandom.randint(0，len(q)-1) += 1t= [sum([qj*sj for j in range(number_of_shifts)]) i in range(number_of_days)] if sum([ri <= ti in range(number_of_days)]) == number_of_days:打印Q中断

没花多少钱就能执行。这是它找到的解决方案之一：0，3，2，2，1，2，1，0