Python移位调度优化

Question

我目前正在研究用于工作的班次调度算法.我们的轮班时间表完全由4-3(4天开,3天开)和4-3开(例如:太阳,周一,周二,关闭一周和下一周以及周日,周五,周六下午) ) - 周日从周日到周六.

"直线"4-3换档或旋转4-3有49种可能的变化.由于这是一次全天候运营,因此需要计算一周中的所有7天.截至目前,我正在利用这个为一个较小的工作组,其中有11人在早班,12人在晚班,但还有其他工作组有多达200人,我想将此算法扩展到.

基本前提是管理小组每天都有必要的人力,算法只返回一组早期和晚期轮班,这些轮班为他们提供了所需的人力.

令人痛苦地显而易见的是,为11个人安排了49个可能的班次(重复)并且对所有这些可能的组合进行分类将花费数千年.结果,我已经能够将49个班次列表剔除到最常用班次的16-20个.

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

1. 作为变量,我有一堆1和0代表他们在那一周的每一天代表"On Shift"和"Off Shift"的班次 - 超过两周的时间.我现在只使用一个样本....例如:

   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作为这个例子)最常见的转换,如果不是专门使用的,加上一个变量,它将计算的人数和a经理要求的变量(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列表引用.我这样做了十四天 - 因为一些轮换班次在第二周扭曲了人员的平衡:

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'移位并跳过它,如果它有更多,正确吗？

Answer 1

您可以使用蒙特卡罗模拟来解决此问题.您无需经历所有可能的组合.你只需要找到符合标准的那个,而且有很多.让我重新解决你的问题.让[sun,mon,tue,...,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]