1

似乎有大量关于循环(或“轮换”)劳动力调度问题的信息。我正在寻找一种算法,该算法将有助于生成员工轮班时间表,而无需关心前一周的时间表是什么样的。根据我的研究,这听起来像是一个非循环的劳动力调度问题。

本质上,我知道员工的空闲时间、他们的最小/最大小时数以及他们请求的休假时间。有了这些信息,我想创建一个优化的时间表,既能满足员工所需的可用性,又能满足每天所需的轮班次数。

有没有人为此目的提供有关良好算法的提示?谢谢!

4

1 回答 1

1

对于像员工调度这样的问题,解决方案有很多限制,我更喜欢从不违反任何限制或尽可能接近的方法。(某些方法,例如基因交叉,会违反约束,然后执行额外的操作来修复解决方案 - 这也是一种有效的方法,但您需要注意走入死胡同。)

两种方法基于使用贪心算法。

第一种是使用半随机贪心算法;如果你有两个选择,那么通常你总是会选择局部最优的选择,但是使用半随机贪心方法,你会引入选择不是局部最优的选择的可能性。例如,选项一的权重为 5,选项二的权重为 2;通常您会选择选项一,但在这种情况下,您将使用随机数生成器并在 rand(5 + 2) 小于 5 时选择选项一,否则选择选项二。现在多次运行算法并采用“最佳”解决方案。

第二种选择是从贪心或半随机贪心解决方案开始,并使用本地搜索算法重新分配员工职位以尝试改进解决方案。例如,如果员工的工作时间少于他们想要的工作时间,那么将占用对次优员工合法的位置的员工进行碰撞,并将次优员工分配给它,如果需要,继续搜索以重新分配被碰撞的员工。与第一个解决方案不同,如果您不小心,这个解决方案可能不会终止。

这两种方法可以结合使用,使用半随机贪心方法生成多个解决方案,然后进行局部搜索以提高最佳结果。

于 2013-08-09T22:24:37.323 回答