algorithm - 哪种算法分配类次(离散优化问题)

我正在开发一种应用程序，可以最佳地将轮类分配给医院的护士。我相信这是一个离散变量的linear programming问题，因此可能是NP-hard:

为每一位护士(约15-20岁)每天分配一个类次

少量(大约6个)不同的类次

有相当多的约束和优化标准，涉及一天或有关员工的问题，例如:

每天每个类次必须分配最少的人数

某些类次重叠，因此如果有人进行中间类次okt_rli可以减少一名早类人员

有些人喜欢早类，有些人喜欢晚类，但是要获得更高的轮类工作报酬，需要最少的轮类变更。

不允许一个人一天上类晚类，第二天上类早类(由于有最短的休息时间规定)

session 分配的工作周时长(因人而异)

...

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

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

从随机分配开始

为每个人和每一天提供健身功能

选择健身值最差的人或一天

随机选择当天/人的一项任务，并将其设置为产生最佳适应度值的值

重复

，直到达到最大迭代次数或找不到所选日期/人的改进

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

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

最佳答案

这是一个很难解决的难题。关于此主题的学术论文很多，尤其是在Operations Research Realm -例如，参见nurse rostering papers 2007-2008或仅谷歌“护士排类操作研究”。复杂度还取决于以下方面:解决多少天；护士可以做出什么样的“要求”；名册是“循环的”；这是一项长期计划还是需要处理诸如病假和掉期等之类的短期名册“修复”？

您描述的算法是heuristic方法。
您可能会发现您可以对其进行调整，使其在一种特定的问题实例中正常工作，但是一旦“某些内容”更改，它就可能无法很好地工作(例如，局部最优，收敛性差)。

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