哪些算法用于分配的变化（离散优化问题） [英] Which algorithm for assigning shifts (discrete optimization problem)

问题描述

我开发的最佳分配转移到护士在医院的应用程序。我相信这是一个线性规划问题离散变量，因此可能NP难：

I'm developing an application that optimally assigns shifts to nurses in a hospital. I believe this is a linear programming problem with discrete variables, and therefore probably NP-hard:

• 在每一天，每名护士（约15〜20）分配一个移
• 有不同班次的一小部分（约6）
• 有相当数量的约束和优化的标准，无论是涉及了一天，还是涉及的emplyoee，例如：
  • 在这里每天都必须是人民赋予给每个最小数量的移位
  • 在某些班次重叠，因此​​，它的确定，少了一个人，早班，如果有一个人在做中间移
  • 在一些人preFER早班，一些preFER晚班，但至少交接班时必须仍然获得较高的轮班工作的报酬。
  • 在它不允许一个人工作到很晚轮班一天，第二天早班（由于最低休息时间的规定）
  • 在会议指定工作周的长度（不同对不同的人）
  • ...
  • For each day, each nurse (ca. 15-20) is assigned a shift
  • There is a small number (ca. 6) of different shifts
  • There is a considerable number of constraints and optimization criteria, either concerning a day, or concerning an emplyoee, e.g.:
    • There must be a minimum number of people assigned to each shift every day
    • Some shifts overlap so that it's OK to have one less person in early shift if there's someone doing intermediate shift
    • Some people prefer early shift, some prefer late shift, but a minimum of shift changes is required to still get the higher shift-work pay.
    • It's not allowed for one person to work late shift one day and early shift the next day (due to minimum resting time regulations)
    • Meeting assigned working week lengths (different for different people)
    • ...

    因此​​，基本上有一个大的数字（AOUT 20 * 30 = 600）变量，每个人都可以采取少量离散值。

    So basically there is a large number (aout 20*30 = 600) variables that each can take a small number of discrete values.

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

    Currently, my plan is to use a modified Min-conflicts algorithm

    • 开始随机分配
    • 具有健身功能，每个人，每一天
    • 选择最差适应值的人或一天
    • 选择随机一个用于天/人的作业以及其设置为导致最佳的适应值
    价值
    • 在重复，直到迭代或者最大数目达到或无改善，可以发现所选择的天/人

    更好的想法？我有些担心，它会停留在局部最优。我应该使用某种形式的模拟退火？或者考虑不仅在时间的改变一个变量，但具体是切换两个人之间的转移（主要成分目前的人工算法）？我想避免剪裁算法，目前制约，因为这些可能会改变。

    Any better ideas? I am somewhat worried that it will get stuck in a local optimum. Should I use some form of simulated annealing? Or consider not only changes in one variable at a time, but specifically switches of shifts between two people (the main component in the current manual algorithm)? I want to avoid tailoring the algorithm to the current constraints since those might change.

    编辑：这是没有必要找一个严格的最优解;名册目前正在做手工，我pretty的肯定的结果是大大次优的大部分时间 - 不应该是很难被击败的。短期的调整和手动覆盖也将肯定是必要的，但我不相信这将是一个问题;过去的标记和手动分配为固定通过降低解空间实际上应该简化任务。

    it's not necessary to find a strictly optimal solution; the roster is currently done manual, and I'm pretty sure the result is considerably sub-optimal most of the time - shouldn't be hard to beat that. Short-term adjustments and manual overrides will also definitely be necessary, but I don't believe this will be a problem; Marking past and manual assignments as "fixed" should actually simplify the task by reducing the solution space.

    推荐答案

    这是一个难以解决的问题很好。已经有关于这个问题的许多学术论文特别是在运筹学领域 - 例如见的nurse排班论文2007-2008 或只是谷歌护士排班运筹学。的复杂性也取决于方面，如：多少天解决;什么是请求可以护士的化妆类型;是花名册循环;它是一个长期的计划，​​还是需要处理短期排班修复，如疾病和掉期等等等等。

    This is a difficult problem to solve well. There has been many academic papers on this subject particularly in the Operations Research field - see for example nurse rostering papers 2007-2008 or just google "nurse rostering operations research". The complexity also depends on aspects such as: how many days to solve; what type of "requests" can the nurse's make; is the roster "cyclic"; is it a long term plan or does it need to handle short term rostering "repair" such as sickness and swaps etc etc.

    您所描述的算法是启发式的方法。 您可能会发现，你可以调整它的工作以及对问题的一个特定实例，但只要事情发生了变化，可能无法正常工作这么好（如局部最优，收敛差）。

    The algorithm you describe is a heuristic approach. You may find you can tweak it to work well for one particular instance of the problem but as soon as "something" is changed it may not work so well (e.g. local optima, poor convergence).

    不过，根据您的特定业务需求的这种做法可能是适当的 - 例如，是多么重要，以获取优化的解决方案，是问题的轮廓你描述预计保持不变，什么是潜在的节省（金钱和资源），重要的是如何的质量护士的看法他们的名册，什么是预算这项工作等。

    However, such an approach may be adequate depending your particular business needs - e.g. how important is it to get the optimal solution, is the problem outline you describe expected to stay the same, what is the potential savings (money and resources), how important is the nurse's perception of the quality of their rosters, what is the budget for this work etc.

    这篇关于哪些算法用于分配的变化（离散优化问题）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！