我目前正在研究轮类调度算法。我们的轮类时间表完全由4-3(开4天，休3天)和轮换4-3(包括周日，周一，周二，下周和下周的休假以及周日，周五，周六下周的休假)组成)-从星期日到星期六的星期。
“直线” 4-3变速或旋转4-3有49种可能的变化。由于它是24/7全天候操作，因此需要考虑一周中的所有7天。截至目前，我正在将其用于一个较小的工作组，前类有11人，下类有12人，但是我希望将其他算法的工作组扩展到200人。
基本前提是管理组每天都有所需的人力，并且算法将仅返回一组早晚的类次，以赋予他们所需的人力。
很快就非常痛苦地意识到，为11个人(带重复)安排49个可能的类次并对所有这些可能的组合进行分类将花费数千年的时间。结果，我已经能够将49个类次的列表剔除到最常用类次的16-20个左右。
这使其易于管理，但仅适用于11或12个人。显然，每次添加一个人时，可能组合的数量就呈指数增长。截至目前，我的算法执行以下操作:
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个)，这是最常见的(如果不是专门使用的)类次，还有一个用于计算人数的变量和一个经理要求的变量(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)。然后，星期一生成器引用引用那些确实在星期日合并的值，将所有那些星期一制成表格，然后用“星期二”列表引用。我在十四天的时间内执行此操作-因为某些轮换操作会扭曲第二周的人员平衡:
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)
生成器表达式STILL必须生成一些东西，检查它是否有5个或更少的'a'移位，如果有更多，则跳过它，对吗？
最佳答案
您可以使用蒙特卡洛模拟来解决此问题。您不需要经历所有可能的组合。您只需要找到一个符合条件的工具即可。让我重新确定您的问题。假设您的管理员要求为 [sun，mon，tue，...，sec_sat] 。 [q1，q2，...，q49] 是49个不同类次中每个类次的人数。和矩阵:
是一周中每个类次的开/关表。例如:如果星期日是类次1的开类日，则s1 [0]为1，否则为0。如果第二个星期日是类次3的工作日，则s3 [7]将为1，否则为零。等等等等。使用此定义，您的问题可以通过以下方式重写:
您的未知数是 [q1，q2，...，q49] 。其余的是已知的。如何使用模拟找到解决方案？您将生成随机的 [q1，...，q49] 向量，并检查是否满足您的条件。如果是，则中断算法并返回结果。例如(某种伪代码):
我为上面的示例实现了一个有限的轮类解决方案:
执行并不需要太多时间。这是找到的解决方案之一: [0，3，2，2，2，1，2，1，0]
关于Python类次调度优化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25953565/