哪种算法适用于分配班次（离散优化问题）

Question

我正在开发一个应用程序，可以将护士在医院的班次最佳地分配。我认为这是一个具有离散变量的线性规划问题，因此可能是NP-hard问题：

• 对于每天，每个护士（约15-20名）都会被分配一个班次
• 有少量（约6个）不同的班次
• 有相当数量的限制和优化标准，无论是关于一天还是关于员工，例如：
  • 每天必须至少有一定数量的人分配到每个班次
  • 某些班次重叠，因此如果有人做中间班次，则早班次可以少一个人
  • 有些人喜欢早班次，有些人喜欢晚班次，但仍需要最少的换班次数才能获得更高的轮班工资。
  • 不允许一个人连续工作晚班次和早班次（由于最小休息时间法规）
  • 满足分配的工作周长度（对于不同的人员有所不同）
  • ...

因此，基本上有大量（约20 * 30 = 600）变量，每个变量都可以取少量的离散值。

目前，我的计划是使用修改过的最小冲突算法。

• 从随机分配开始
• 为每个人和每天设置适应度函数
• 选择适应度值最差的人或者日期
• 随机选择该日期/人员的一个分配，并将其设置为导致最佳适应度值的值
• 重复以上步骤，直到达到最大迭代次数或无法找到所选日期/人员的改进为止

还有更好的想法吗？我有些担心它会陷入局部最优解。我应该使用某种形式的模拟退火吗？或者考虑不仅一次更改一个变量，而是专门在两个人之间切换班次（当前手动算法中的主要组件）？我希望避免将算法定制为当前的约束条件，因为这些条件可能会发生改变。

编辑：不需要找到严格的最优解；目前的排班是手动完成的，我相信大部分时间结果都明显不够优秀 - 应该很容易超越它。短期调整和手动覆盖肯定也是必要的，但我不认为这会成为问题；将过去和手动分配标记为“固定”实际上应该通过减少解决方案空间来简化任务。

- Michael Borgwardt

---

我记得有一个关键词可能会有所帮助（但不确定，因为记忆已经褪色）：列生成技术。 - Anonymous

我已经阅读过了，这个问题通常非常难以解决。此外，有一个不容易的可能性，它实际上可能会被过度约束。祝你好运。 - dmckee --- ex-moderator kitten

每个班次通常需要多少名护士？您通常会安排多少天？ - j_random_hacker

一个典型的需求是在一天之内需要1个（夜班）到5个（工作日早班）人。我目前计划每次制定一个月的时间表，尽管我将不得不至少考虑一个约束条件，即月份之间的班次变更。 - Michael Borgwardt

模拟退火算法不应该陷入局部最小值。约束满足问题也可以，但老实说，对我来说SA似乎每次都能胜过它们。SA的额外好处是非常便宜。 - ldog

我认为你的最小冲突方法是解决问题的好途径。 - Pete855217

Answer 1

这是一个难以很好解决的问题。在此领域，特别是运筹学领域已经有许多学术论文，例如2007-2008护士排班论文或只需谷歌“护士排班运筹学”即可查阅。复杂度还取决于以下方面：需要解决几天；护士能提出什么类型的请求；是否为“循环”排班；是长期计划还是需要处理短期排班“修理”，如生病和交换等。

你所描述的算法是一种启发式方法。您可以发现可以调整它使其适用于问题的一个特定实例，但是一旦“某些东西”被改变，它可能就无法很好地工作（例如，局部最优、收敛性差）。

然而，这样的方法可能会根据您的特定业务需求足够，例如：获得最佳解决方案对您有多重要，您所描述的问题概要预计将保持不变，可节省多少资金和资源，护士对其排班质量的看法有多重要，这项工作的预算是多少等。

- luapyad

---

哇，我没想到这会是那么多研究工作的主题。谢谢，我一定会看一些那些论文。我会编辑问题以指定您提到的一些因素。 - Michael Borgwardt

Answer 2

嗯，您知道一些ILP求解器做得很好吗？试试AIMMS、Mathematica或GNU编程工具包！600个变量当然比Lenstra定理容易解决的多，但有时这些ILP求解器能够很好地处理。在AIMMS中，您可以稍微修改分支策略。此外，还有一种非常快速的100%近似ILP解法。

- Niko

---

谢谢提供指引，我会仔细研究一下这些内容，看看是否可以应用到我的项目中。 - Michael Borgwardt

好的指针，这些求解器已经比OP要深入研究他的问题了。你也应该指出ILP使用启发式搜索(我认为是分支定界)。 - ldog

Answer 3

最近我为一家大型制造工厂解决了一个班次分配问题。首先，我们尝试生成纯随机的时间表，并返回通过了is_schedule_valid测试的任何一个 - 后备算法。当然，这很慢而且不确定。

接下来，我们尝试了遗传算法（正如您建议的那样），但是找不到一个良好的适应度函数，可以得出任何可行的解决方案（因为最小的更改可能使整个时间表正确或错误 - 几乎没有得分）。

最后，我们选择了以下方法（效果非常好！）：

1. 随机化输入集（即作业、班次、员工等）。 2. 创建一个有效的元组并将其添加到您的暂定时间表中。 3. 如果无法创建有效的元组，则回滚（并增加）上次添加的元组。 4. 将部分时间表传递给测试could_schedule_be_valid的函数，即如果剩余的元组以可能的方式填充，此时间表是否有效。 5. 如果!could_schedule_be_valid，只需回滚（并增加）在（2）中添加的元组。 6. 如果schedule_is_complete，return schedule 7. 转到（2）

通过这种方式逐步构建部分班次。好处是，在第2步（预测试）中可以轻松执行某些有效时间表的测试，而其他测试必须保留在第5步（后测试）中。

祝你好运。我们浪费了数天尝试前两个算法，但是在不到5小时的开发时间内，推荐的算法即可生成有效的时间表。

此外，我们支持分配的前缀和后缀，算法会尊重这些分配。在第1步中，您只需不随机化这些插槽即可。您会发现解决方案不必接近最佳。我们的解决方案至少为O（N * M），但在PHP中仅需要不到半秒钟就可以为整个制造工厂执行。美妙之处在于使用良好的could_schedule_be_valid测试快速排除错误的时间表。

那些习惯手动操作的人不在乎花费一个小时 - 他们只知道他们不再需要手动操作。

- Andy

---

我的要求是不同的 - 结果不是对或错，它可以在一个连续的范围内任何位置，从“可怕”到“可接受”，再到“完美” - 实际上，这是每个人和每天的个体量表的组合。 - Michael Borgwardt

我猜你所说的“元组”是指一天或一个工人的任务分配组合？你描述了一个基本的回溯算法，第四步显然是一个至关重要的优化，但我不明白如何高效地实现它——我想这可能对你的需求非常特定。 - Michael Borgwardt

是的，我的意思是这个算法并不是最优的，但它“足够好”。 它非常简单但有效。 它的时间复杂度至少为O（N*M）。对于这个问题来说，因为N，M很小，所以运行时间并不长。优化在于在消除它们之前不必构建整个时间表。 - Andy

如果你的时间表在连续的范围内变化，你仍然可以使用分支定界算法来跟踪当前解决方案的得分，并在它比当前的“最佳得分”更差时进行回溯。每当找到更好的解决方案时，请更新全局的“最佳得分”。 - j_random_hacker

我不确定能否使用B＆B算法，因为我认为变量的数量意味着很难甚至不可能找到可用的分区并计算剩余适应度的有意义的界限。 - Michael Borgwardt

Answer 4

Mike，

不知道你是否得到了一个好的答案，但我相信约束编程是解决问题的关键。虽然遗传算法可能会给出一个答案，但约束编程旨在为您提供多个答案或告诉您是否没有可行的解决方案。搜索“约束编程”和“调度”应该会带来很多信息。这是一个相对较新的领域，CP方法在许多类型的问题上运作良好，而传统的优化方法则陷入困境。

- Grembo

---

依我的经验，约束编程确实应该能够处理这个问题的规模。 - willem

Answer 5

使用CSP编程，我制作了自动班次排班程序。例如：

1. 2班制-在100多名护士、30天时间范围和10个以上规则的测试下
2. 3班制-在80多名护士、30天时间范围和10个以上规则的测试下
3. 4组3班制-在365天时间范围和10个以上规则的测试下

还有一些类似的系统。所有这些系统都在我的家用电脑上进行了测试（1.8GHz，双核）。执行时间总是可以接受的，例如对于3/，需要大约5分钟和300MB RAM。

这个问题最难的部分是选择合适的求解器和求解策略。

- dlpx

Answer 6

元启发式算法在2010年国际护士排班竞赛中表现出色。

有关实现，请参见此连续护士排班（Java）视频。

- Geoffrey De Smet

Answer 7

我认为你应该使用遗传算法，因为：

• 它最适合大规模问题实例。
• 它在减少时间复杂度的同时会得到不太准确的答案（不是终极最佳）。
• 通过调整未满足约束条件的适应度惩罚，您可以轻松指定约束条件和偏好。
• 您可以为程序执行指定时间限制。

• 解决方案的质量取决于您打算花多少时间解决该程序。

  遗传算法定义

  遗传算法教程

  使用GA进行课程安排项目

还要看看：一个类似的问题和另一个问题

- Betamoo

---

遗传编程在这种问题上几乎没有用处。如果要将其作为有效解决方案，您需要做的不仅是引用其广泛的优点，而是解释其适用性，以解决这种集合覆盖问题（您链接的示例与此问题非常不同）。不幸的是，它们并不存在：遗传算法解决完全不同类型的问题。这个问题的难点在于减少0/1矩阵中列的数量，以便LP求解是实际可行的，但启发式方法可以在这里提供帮助。 - Pete855217

Answer 8

动态规划有点像贝尔的做法？听起来好像有它的用武之地：重叠子问题，最优子结构。

- Charlie Martin

---

我认为这种技术不适用，因为子问题相互影响，因此不是独立的，解决方案也不能重复使用。 - Michael Borgwardt

动态规划不适用于这种问题。该问题既常见又难以解决，需要大量使用启发式算法。研究集合覆盖问题，并使用0/1矩阵作为约束条件以获取更多信息。作为一种技术，约束编程是可能的，但比具有明确定义的约束条件的LP不太合适。目标函数定义是所有工作的关键。航空公司在乘务员分配方面面临这个问题（在LP生成班次模式或行程/旅游之后），有许多软件提供商，例如Carmen（请参见论文）。 - Pete855217

这些问题最终会导致列数巨大（例如30万），因此大部分处理都集中在启发式地减少问题规模。我已经成功使用GLPK，但其他商业LP求解器也很好，例如Gurobi和CPLEX。 - Pete855217

Answer 9

你可以尝试在问题中寻找对称性。例如，你能否将所有护士视为等同的？如果是这样，那么你只需要按任意顺序考虑护士，你可以避免考虑任何护士i在护士j之前安排的解决方案，其中i>j。（你说过每个护士都有首选班次，这与此示例相矛盾，但也许这不是一个很重要的目标？）

- j_random_hacker

---

首选班次并不是非常重要，但人们之间有其他不能忽视的差异，比如由于医疗条件豁免夜班的人。 - Michael Borgwardt

@RouteMapper：这取决于你使用的求解器类型。无论如何，你最有可能需要量化变量i、j和n，例如，“对于给定的n，以及对于每个i < j，...”。顺便说一句，如果你的意思是对于所有的i < j和所有的n，那么这里存在矛盾（没有解决方案）。如果你的意思是对于所有的i < j和一个固定的n，我认为你需要n > j-i（可能更高）来避免矛盾。 - j_random_hacker

@j_random_hacker 我觉得我需要澄清一下。每个护士都具备不同的能力c。每个班次s有两名护士。每个s需要安排具备特定能力c的护士来工作。能力会过期，此时具备过期能力c的护士将无法在需要c的s上工作。但是，只要在本周早些时候存在一个班次s，在该班次中，具备所需能力c的护士与具备过期能力的护士一起工作（因此可以更新过期能力），则可以为需要c的s安排护士。 - RouteMapper

@j_random_hacker 是的，一个持有过期c能力证书的护士意味着她在那个时候没有c能力。 - RouteMapper

@RouteMapper：通常情况下，您可以将护士i在时间t是否具备能力c的描述作为函数NurseHasCompetence(i, c, t)的一个值为真或假的函数。您可能需要其他参数，可能需要一个参数s来描述时间t之前的完整日程安排。 - j_random_hacker