我正在开发一种应用程序，可以最佳地将轮班分配给医院的护士。我相信这是带有离散变量的线性规划问题，因此可能是NP难的问题：

• 每天为每位护士（约15至20岁）分配一个班次
• 少数（大约6个）不同的班次
• 有很多约束和优化标准，涉及一天或员工，例如：
  • 每天每个班次必须分配最少人数
  • 某些班次重叠，因此如果有人进行中间班次，可以减少一个人早班
  • 有些人喜欢早班，有些人喜欢晚班，但是要获得更高的轮班工作报酬，需要最少的轮班变动。
  • 不允许一个人一天上班晚班，第二天上班早班（由于有最短的休息时间规定）
  • 满足分配的工作周时长（因人而异）
  • …

因此，基本上有大量变量（总共20 * 30 = 600），每个变量都可以使用少量离散值。

目前，我的计划是使用修改后的Min-
conflicts算法

• 从随机分配开始
• 具有适合每个人每天的健身功能
• 选择适合度最差的人或一天
• 随机选择当天/人的一项任务，并将其设置为可产生最佳适应性值的值
• 重复此操作，直到达到最大迭代次数或在选定的日期/人中找不到任何改善

还有更好的主意吗？我有点担心它将陷入局部最优状态。我应该使用某种形式的模拟退火吗？还是不仅要考虑一次变量的变化，还要特别考虑两个人（当前手动算法的主要组成部分）之间的换档切换？我想避免针对当前约束条件调整算法，因为这些约束条件可能会发生变化。

编辑： 没有必要找到严格的最佳解决方案；目前，花名册是手动完成的，我可以肯定，大多数情况下结果是次优的-
应该不难做到。当然也必须进行短期调整和手动操作，但是我认为这不会成为问题。将过去的作业和手动作业标记为“固定”实际上可以通过减少解决方案空间来简化任务。