如何高效快速地从字符串元素数组中找出有效组合用于员工排班?

How to efficiently and quickly find valid combinations out of an array of string elements for employee scheduling?

我正在从事一个需要非常具体的日程安排的项目(以及为什么我不使用图书馆)。它有效,但我正在尝试为以下问题找到更快的解决方案:

我们每周都有员工要求工作时间。他们输入他们本周的总可用性(例如:8-1 M,W,R)。他们都必须每周工作 10 小时,并且每个班次必须至少连续工作 2 小时。 (所有班次都是连续的,中间没有休息)。

例如,员工 1 说空闲时间是:8-3 M,W,R,F:可以安排他在 M 工作 3 小时,在 W 工作 3 小时,在 F 工作 2 小时,或任何其他组合 (例如 4、4、2;2、2、4 等)。问题是试图找到这些组合。 现在我将它们的可用性存储为分号分隔的字符串(等:8,9,10,11,12,1;8,9,10,11,12,1;8,9,10;;8,9每天将是几个小时(5 天)) 我在调度过程中将它们分成一个数组,然后这对我来说是困难的部分:

我希望能够确定这些小时的组合,其中每个组合每天至少有 2 小时,所有小时都是连续的,并且总共选择了 10 小时。现在,我的解决方案是非常蛮力的。

我使用 itertools 组合。我考虑他们的可用性,并且每天将相应日期的字母附加到它并放入一个数组中。所以例子 8,9,10,11;8,9;;8,9,10,11;变成 [m8,m9,m10,m11,t8,t9,r8,r9,r10,r11]

然后我用itertools组合把这个数组的所有组合都翻一遍,有个函数翻一遍看每天有没有连续的小时数,至少2小时轮班,一共10小时(或者其他小时数,这可以更改)。

这是一个非常缓慢的过程,因为如果某人有 8-5 M-F 的可用性,他们可以有很多有效和无效的组合。 (我需要全部测试的原因是因为我们有 100 多个员工担任类似的角色,如果一个角色被占用,那时候就不能安排另一个员工)

我现在如何做的例子。


    # let availability be the string of availability 
    availability = "8,9,10,11;8,9;;8,9,10,11;"
    poss_times = availability.split(";")
    # where I put into one array with each day letter in front
    sched=[]
    sched.extend(["m" + day for day in list(filter(None,poss_times[0].split(",")))])
    sched.extend(["t" + day for day in list(filter(None,poss_times[1].split(",")))])
    sched.extend(["w" + day for day in list(filter(None,poss_times[2].split(",")))])
    sched.extend(["r" + day for day in list(filter(None,poss_times[3].split(",")))])
    sched.extend(["f" + day for day in list(filter(None,poss_times[4].split(",")))])
    sched.extend(["s" + day for day in list(filter(None,poss_times[5].split(",")))])
    sched.extend(["u" + day for day in list(filter(None,poss_times[6].split(",")))])

    for poss_combination in itertools.combinations(sched, 10):
        # check if the combination fulfills the requirements, and if so continue to see if it is possible to schedule that employee

我希望有一个更快、更优雅的解决方案可以加快这个过程。感谢您的任何帮助。

我认为这是著名的例子Nurse scheduling problem。这个问题是 NP-hard,即要找到最佳解决方案,您必须创建所有可能的分配组合,并且 select 最适合的组合。由于这是指数时间复杂度,所以只适用于小问题,而你的显然已经太大了。
如果你只想找到一个合理的(不是最优的)解决方案,可以应用 general-purpose 随机算法,因为它们在上面提到的 Wiki post 中被引用,例如随机优化、遗传算法和模拟退火。但是这样的方法通常计算时间很长。
无论如何,here 是一个用遗传算法解决护士调度问题的例子。或许您可以尝试将其应用于您的问题,并检查它是否改善了您的情况。