21

我正在开发一个应用程序，可以优化地为医院的护士分配轮班。我相信这是一个离散变量的线性规划问题，因此可能是 NP-hard：

  • 每天，每位护士（约 15-20 名）都被分配一个轮班
  • 有少量（约 6 个）不同的班次
  • 有相当多的约束和优化标准，无论是与一天有关，还是与员工有关，例如：
    • 每天必须为每个班次分配最少人数
    • 一些班次重叠，因此如果有人在做中间班次，则可以在早期班次少一个人
    • 有些人更喜欢早班，有些人更喜欢晚班，但需要最少的换班才能获得更高的轮班工作工资。
    • 一个人一天不能晚班，第二天早班（由于最低休息时间规定）
    • 会议分配的工作周长度（不同的人不同）
    • ...

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

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

  • 从随机分配开始
  • 对每个人和每一天都有一个健身功能
  • 选择健身值最差的人或日子
  • 为那一天/人随机选择一项任务，并将其设置为产生最佳适应度值的值
  • 重复直到达到最大迭代次数或对于选定的日期/人无法找到改进

有更好的想法吗？我有点担心它会陷入局部最优。我应该使用某种形式的模拟退火吗？或者不仅考虑一次只改变一个变量，还特别考虑两个人之间的轮班切换（当前手动算法的主要组成部分）？我想避免根据当前的约束来定制算法，因为这些可能会改变。

编辑：没有必要找到严格的最优解；名册目前是手动完成的，我很确定结果在大多数情况下都不是最理想的——应该不难打败它。短期调整和手动覆盖也肯定是必要的，但我不认为这会是一个问题；将过去和手动分配标记为“固定”实际上应该通过减少解决方案空间来简化任务。

4

9 回答 9

12

这是一个很难很好解决的问题。有很多关于这个主题的学术论文，特别是在运筹学领域——例如，参见2007-2008 年护士轮班论文或只是谷歌“护士轮班运营研究”。复杂性还取决于以下方面：要解决多少天；护士可以提出什么样的“要求”；名册是“循环的”；这是一个长期计划还是需要处理短期排班“修复”，例如疾病和掉期等。

您描述的算法是一种启发式方法。您可能会发现您可以对其进行调整以使其适用于问题的一个特定实例，但是一旦“某事”发生更改，它可能就不能很好地工作（例如局部最优、收敛性差）。

但是，根据您的特定业务需求，这种方法可能就足够了 - 例如，获得最佳解决方案有多重要，您描述的问题大纲是否预期保持不变，潜在的节省（金钱和资源）是多少，有多重要是护士对其名册质量的看法，这项工作的预算是多少等。

于 2009-02-21T21:05:49.180 回答
4

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

于 2009-02-21T20:57:39.387 回答
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美妙之处在于使用良好的测试快速排除不良日程安排。

习惯于手动操作的人不在乎是否需要一个小时——他们只知道他们不再需要手动操作。

于 2009-02-21T21:52:20.940 回答
2

麦克风，

不知道您是否对此有过很好的回答，但我很确定约束编程就是门票。虽然 GA 可能会给您一个答案，但 CP 旨在为您提供许多答案或告诉您是否没有可行的解决方案。搜索“约束编程”和调度应该会带来很多信息。这是一个相对较新的领域，CP 方法可以很好地解决传统优化方法陷入困境的许多类型的问题。

于 2010-01-28T20:54:42.533 回答
0

像贝尔一样的动态编程？听起来有点像它的位置：重叠子问题，最佳子结构。

于 2009-02-21T20:41:36.460 回答
0

您可以做的一件事是尝试在问题中寻找对称性。例如，就问题而言，您能否将所有护士视为同等对待？如果是这样，那么您只需要按任意顺序考虑护士 - 您可以避免考虑将任何护士i安排在 i > j 的任何护士j之前的解决方案。（你确实说过个别护士更喜欢轮班时间，这与这个例子相矛盾，尽管这可能是一个不太重要的目标？）

于 2009-02-21T21:05:29.833 回答
0

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

  • 它最适合大型问题实例。
  • 它以不准确的答案为代价降低了时间复杂度（不是最终最好的）
  • 您可以通过调整未满足的健身惩罚来轻松指定约束和偏好。
  • 您可以指定程序执行的时间限制。

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

    遗传算法定义

    遗传算法教程

    带有 GA 的课程安排项目

也看看：一个类似的问题和另一个

于 2011-01-04T14:46:19.003 回答
0

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

  1. 2 班制 - 针对 100 多名护士、30 天时间范围、10 多条规则进行了测试
  2. 3 班制 - 针对 80 多名护士、30 天时间范围、10 多条规则进行了测试
  3. 3 班制，4 个团队 - 测试 365 天，10 多个规则，

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

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

于 2013-04-06T17:24:37.673 回答
0

Metaheuristics在2010 年国际护士排班比赛中表现出色。

有关实施，请参阅此视频，其中包含连续护士排班 (java)。

于 2014-02-14T15:13:32.397 回答