分配班次的算法（离散优化问题）
我正在开发一个应用程序，可以为医院的护士最佳地分配轮班。 我相信这是一个带有离散变量的线性规划问题，因此可能是NP困难的：
- 每天，每位护士（约 15-20）被分配一个轮班
- 有少量（约 6）个不同的轮班
- 有大量的约束和优化标准，无论是关于一天，还是关于员工，例如：
- 每天每个班次必须分配最少人数
- 有些轮班会重叠，因此如果有人做中班，早班少一个人也没关系
- 有些人喜欢早班，有些人喜欢晚班，但需要最少的换班才能仍然获得较高的轮班工资。
- 不允许一个人一天晚班次日早班（根据最短休息时间规定）
- 满足指定的工作周长度（因人而异）
- ...
所以基本上有很大数量（大约 20 *30 = 600) 个变量，每个变量可以取少量离散值。
目前，我的计划是使用修改后的最小冲突算法，
- 随机分配开始
- 从具有适应度函数的 对于每个人和每一天，
- 选择适合度值最差的人或天，
- 随机选择当天/人的分配之一，并将其设置为导致最佳适合度值的值，
- 重复直到最大迭代次数为所选日期/人已达到或未发现
任何改进 有更好的想法吗？ 我有点担心它会陷入局部最优。 我应该使用某种形式的模拟退火吗？ 或者不仅考虑一次一个变量的变化，还考虑两个人之间的轮班切换（当前手动算法的主要组成部分）？ 我想避免根据当前的约束调整算法，因为这些约束可能会发生变化。
编辑：没有必要找到严格的最佳解决方案； 名册目前是手动完成的，我很确定大多数时候结果都不是最佳的 - 应该不难击败它。 短期调整和手动超控也肯定是必要的，但我不认为这会成为问题； 将过去的手动分配标记为“固定”实际上应该通过减少解决方案空间来简化任务。
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:
- 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)
- ...
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
- start with random assignments
- have a fitness function for each person and each day
- select the person or day with the worst fitness value
- select at random one of the assignments for that day/person and set it to the value that results in the optimal fitness value
- repeat until either a maximum number of iteration is reached or no improvement can be found for the selected day/person
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.
Edit: 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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
这是一个很难很好解决的问题。 关于这个主题有很多学术论文，特别是在运筹学领域 - 例如参见护士排班论文 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.
嗯，您知道一些 ILP 求解器做得很好吗？ 尝试 AIMMS、Mathematica 或 GNU 编程工具包！ 600 个变量当然比 Lenstra 定理可以轻松解决的要多得多，但有时这些 ILP 求解器具有良好的处理能力，并且在 AIMMS 中，您可以稍微修改分支策略。 另外，ILP 具有非常快的 100% 近似值。
Umm, did you know that some ILP-solvers do quite a good job? Try AIMMS, Mathematica or the GNU programming kit! 600 Variables is of course a lot more than the Lenstra theorem will solve easily, but sometimes these ILP solvers have a good handle and in AIMMS, you can modify the branching strategy a little. Plus, there's a really fast 100%-approximation for ILPs.
我最近解决了一家大型制造工厂的轮班分配问题。 首先，我们尝试生成纯随机计划并返回任何通过 is_schedule_valid 测试（后备算法）的计划。 当然，这是缓慢且不确定的。
接下来我们尝试了遗传算法（正如您所建议的），但找不到一个好的适应度函数来关闭任何可行的解决方案（因为最小的变化可以使整个计划正确或错误 - 几乎没有分数）。
最后我们选择了以下方法（效果很好！）：
could_schedule_be_valid的函数，即如果剩余元组以可能的方式填充，则此调度是否有效！could_schedule_be_valid，只需回滚（并递增）在（2）中添加的元组。schedule_is_complete，返回时间表您可以通过这种方式逐步构建部分班次。 这样做的好处是，一些有效计划的测试可以在步骤 2（预测试）中轻松完成，而其他测试则必须保留在步骤 5（后测试）中。
祝你好运。 我们浪费了数天时间尝试前两种算法，但在不到 5 小时的开发时间内就得到了推荐的算法，立即生成有效的时间表。
此外，我们还支持算法所遵循的分配的预先固定和后固定。 您只需不在步骤 1 中随机化这些槽即可。您会发现解决方案不必接近最佳。 我们的解决方案至少是 O(N*M)，但对于整个制造工厂来说，在 PHP(!) 中执行只需不到半秒。 美妙之处在于使用良好的
could_schedule_be_valid测试快速排除错误的时间表。习惯于手动执行此操作的人并不关心是否需要一个小时 - 他们只是知道他们不必再手动执行此操作。
I solved a shift assignment problem for a large manufacturing plant recently. First we tried generating purely random schedules and returning any one which passed the
is_schedule_validtest - the fallback algorithm. This was, of course, slow and indeterminate.Next we tried genetic algorithms (as you suggested), but couldn't find a good fitness function that closed on any viable solution (because the smallest change can make the entire schedule RIGHT or WRONG - no points for almost).
Finally we chose the following method (which worked great!):
could_schedule_be_valid, that is, could this schedule be valid if the remaining tuples were filled in a possible way!could_schedule_be_valid, simply rollback (and increment) the tuple added in (2).schedule_is_complete,return scheduleYou incrementally build a partial shift this way. The benefit is that some tests for valid schedule can easily be done in Step 2 (pre-tests), and others must remain in Step 5 (post-tests).
Good luck. We wasted days trying the first two algorithms, but got the recommended algorithm generating valid schedules instantly in under 5 hours of development.
Also, we supported pre-fixing and post-fixing of assignments that the algorithm would respect. You simply don't randomize those slots in Step 1. You'll find that the solutions doesn't have to be anywhere near optimal. Our solution is O(N*M) at a minimum but executes in PHP(!) in less than half a second for an entire manufacturing plant. The beauty is in ruling out bad schedules quickly using a good
could_schedule_be_validtest.The people that are used to doing it manually don't care if it takes an hour - they just know they don't have to do it manually any more.
迈克，
不知道你是否对此有一个好的答案，但我很确定约束编程就是关键。 虽然 GA 可能会给您一个答案，但 CP 旨在为您提供许多答案或告诉您是否没有可行的解决方案。 搜索“约束编程”和调度应该会带来很多信息。 这是一个相对较新的领域，CP 方法可以很好地解决传统优化方法无法解决的许多类型的问题。
Mike,
Don't know if you ever got a good answer to this, but I'm pretty sure that constraint programming is the ticket. While a GA might give you an answer, CP is designed to give you many answers or tell you if there is no feasible solution. A search on "constraint programming" and scheduling should bring up lots of info. It's a relatively new area and CP methods work well on many types of problems where traditional optimization methods bog down.
动态编程像贝尔吗？ 听起来好像有它的用武之地：重叠的子问题，最优的子结构。
Dynamic programming a la Bell? Kinda sounds like there's a place for it: overlapping subproblems, optimal substructures.
我使用 CSP 编程编写了用于自动 Shitfs 排班的程序。 例如：
规则
和几个类似的系统。 所有这些都在我的家用电脑（1.8GHz，双核）上进行了测试。 执行时间总是可以接受的，即。 3/ 大约需要 5 分钟和 300MB RAM。
这个问题最困难的部分是选择合适的求解器和合适的求解策略。
Using CSP programming I made programms for automatic shitfs rostering. eg:
rules
and a couple of similiar systems. All of them were tested on my home PC (1.8GHz, dual-core). Execution times always were acceptable ie. for 3/ it took around 5 min and 300MB RAM.
Most hard part of this problem was selecting proper solver and proper solving strategy.
Metaheuristics 在2010 年国际护士排班竞赛中表现出色。
有关实施方式，请观看连续护士排班的视频 (java)。
Metaheuristics did very well at the International Nurse Rostering Competition 2010.
For an implementation, see this video with a continuous nurse rostering (java).
您可以做的一件事就是尝试寻找问题中的对称性。 例如，就问题而言，您能否将所有护士视为同等？ 如果是这样，那么您只需要以某种任意顺序考虑护士 - 您可以避免考虑这样的解决方案：将任何护士 i 安排在任何护士 j 之前，其中 我> j。 （您确实说过个别护士有更喜欢的轮班时间，这与这个例子相矛盾，尽管这也许是一个不太重要的目标？）
One thing you can do is to try to look for symmetries in the problem. E.g. can you treat all nurses as equivalent for the purposes of the problem? If so, then you only need to consider nurses in some arbitrary order -- you can avoid considering solutions such that any nurse i is scheduled before any nurse j where i > j. (You did say that individual nurses have preferred shift times, which contradicts this example, although perhaps that's a less important goal?)