时间戳

首页 > 解决方案 > 如何高效快速地从字符串元素数组中找到有效的组合进行员工排班？

python - 如何高效快速地从字符串元素数组中找到有效的组合进行员工排班？

问题描述

我正在做一个需要非常具体的调度的项目（以及为什么我不使用库）。它有效，但我正在尝试为以下问题找到更快的解决方案：

我们每周都有员工要求工作时间。他们输入了一周的总可用性（例如：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 MF 的可用性，他们可以有很多有效和无效的组合。（我需要全部测试的原因是因为我们有 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

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

标签： pythonpython-3.xlistcombinationsscheduling

解决方案

我认为这是著名的护士调度问题的一个例子。这个问题是 NP 难的，即要找到最佳解决方案，您必须创建所有可能的分配组合，并选择最适合的一个。由于这是指数时间复杂度，它只适用于小问题，而你的问题显然已经太大了。
如果您只想找到一个合理（不是最优）的解决方案，可以应用通用随机算法，正如上面提到的 Wiki 帖子中引用的那样，例如随机优化、遗传算法和模拟退火。但是这样的方法通常具有很长的计算时间。
无论如何，这里是通过遗传算法解决护士调度问题的示例。也许您可以尝试将其应用于您的问题，并检查它是否可以改善您的情况。

推荐阅读