哪种算法用于分配移位(离散优化问题)

Question

我正在开发一种应用程序,可以最佳地为医院的护士分配班次.我认为这是一个带离散变量的线性规划问题,因此可能是NP难的:

• 对于每一天,每位护士(约15-20岁)都会被分配轮班
• 有少量(约6个)不同的班次
• 有相当多的约束和优化标准,无论是关于一天,还是关于一个emplyoee,例如:
  • 每天必须为每个轮班分配最少数量的人员
  • 有些班次重叠,所以如果有人做中间班,可以让一个人在早班换一个人
  • 有些人更喜欢提前班次,有些人更喜欢延迟班次,但需要最少的换班才能获得更高的轮班工资.
  • 不允许一个人一天工作到第二天工作到第二天早班(由于最短的休息时间规定)
  • 满足指定的工作周长度(不同的人不同)
  • ...

因此,基本上存在大量(约20*30 = 600)变量,每个变量可以采用少量离散值.

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

• 从随机分配开始
• 每个人和每一天都有健身功能
• 选择具有最差健身值的人或日
• 随机选择该日/人的任务之一并将其设置为导致最佳适合度值的值
• 重复直到达到最大迭代次数或者找不到所选日期/人的改进

有更好的想法吗？我有点担心它会陷入局部最佳状态.我应该使用某种形式的模拟退火吗？或者不仅考虑一次改变一个变量,而且特别考虑两个人之间的转换(当前手动算法中的主要部分)？我想避免将算法定制到当前约束,因为那些可能会改变.

编辑:没有必要找到严格的最佳解决方案; 名单目前是手工完成的,我很确定结果在大多数时候都是非常不理想的 - 不应该难以击败.短期调整和手动覆盖也一定是必要的,但我不认为这是一个问题; 将过去和手动分配标记为"已修复"实际上应该通过减少解决方案空间来简化任务.

Answer 1

这是一个难以解决的难题.有关此主题的学术论文很多,特别是在运筹学领域 - 例如参见护士排班论文2007-2008或只是谷歌"护士排班运算研究".复杂性还取决于以下方面:需要多少天才能解决; 护士可以做出什么样的"要求"; 名单是"循环的"; 这是一个长期计划还是需要处理短期排班"维修",如疾病和掉期等.

您描述的算法是一种启发式方法.你可能会发现你可以调整它以适应问题的一个特定实例,但一旦"某些东西"改变它可能不会那么好(例如局部最优,收敛性差).

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