哪种算法用于分配的变化(离散优化问题)
https://stackoverflow.com/questions/573670
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我正在开发一个应用程序，最佳地分配转移到护士在一家医院。我相信这是一个 线性规划 问题与离散变量，因此可能NP-难：
- 每一天、每一个护士(加利福尼亚州。15-20个)被指定移位
- 有一个小数目(加利福尼亚州。6)的不同的变化
- 有相当数量的限制和优化标准，无论是关于一个天，或者关于一个emplyoee，例如：
- 必须有一个最低数量的人分配给每个转移的每一天
- 一些变化重叠，因此，它是确定有一个小人在早期的转变如果有人做中间转移
- 有些人喜欢早期的移，一些人喜欢晚班，但是最低的转移变化的需要仍然获得更高的转变-的工作支付。
- 这是不允许一个人工作的后期转移一天早班的第二天(由于最低休息时间的规定)
- 会议分配的每周工作时间的长度(不同对不同的人)
- ...
所以基本上有一个大数量(aout20*30=600)的变量，每一个可以拿一个小号的离散数值。
目前，我的计划是利用一个修改 Min-冲突的算法
- 开始随机任务
- 有一个功能健身对于每个人和每一天
- 选择的人或天最严重的健身价值
- 在随机选择一项任务，每人每天设置的价值，结果在最佳的健身价值
- 重复，直至最大数量的迭代达到或没有改善可能被发现为选定的每人每天
什么好主意吗？我有点担心，它会停留在当地的最佳。我应该用某种形式的 模拟退火?或考虑不仅改变了在一个变量在一段时间，但是具体的交换机的的转变，两个人之间(主要成分在目前的手册算法)?我想要避免的剪裁算法的当前限制，因为那些可能会改变。
编辑： 这是没有必要找到一个严格的最佳解决方案；该名册目前完成手册，而且我相当肯定的结果是相当大的次优的大部分时间应该不难击败。短期的调整和手册的复盖也将肯定是必要的，但我不相信这将是一个问题；标记过去和手册，分配如"固定"实际上应该简化的任务，通过减少方案的空间。
解决方案
这是一个难以解决的问题。已经有许多学术论文在这一主题的特别是 行动研究 现场-例如见 护士列入名册的论文2007-2008年 或者只是谷歌"护士列入名册作业的研究"。复杂性还取决于各方面，诸如：多少天以解决；什么类型的"请求"可能的护士；是的名册"循环";它是一个长期计划，或是否需要处理短期名册"修复"，如疾病和全部门办法等等。
算法你描述的是一个 试探 办法。你可以找到可以调整它的工作以及一个具体实例问题，但是尽快"什么"是改变了它可能不那么好的工作(例如当地optima，穷人收敛).
然而，这样一种方法可以充分的根据你的特定业务需求，例如如何重要的是它得到的 最优的 解决方案，是该问题的概要你描述的预期保持相同，什么是潜在的节省(金钱和资源)，怎样重要的是护士的感知质量，他们的名册，什么是预算为此工作等。
其他提示
嗯，你知道，一些指令级解决做的相当良好的工作吗？试着诚邀相关，Mathematica或GNU编程工具包！600变量，当然是更多的俱乐部理会解决很容易，但有时这些指令级解决有一个良好的处理和在诚邀相关，可以修改的分支战略的一点。另外，还有一个真的快速100%的逼近于ILPs.
我解决了一个移位分配问题的大型制造厂。第一，我们试图产生纯粹是随机安排和返回任何一种，其通过了 is_schedule_valid 试验的后备算法。这当然是缓慢和不确定的。
接下来，我们尝试了遗传算法(如你所建议的)，但无法找到一个良好的健身的功能，关闭任何可行的解决方案(因为最小的变化可能使整个时间表正确或错误-没有点几乎).
最后，我们选择了以下方法(其工作的伟大!):
- 随机的输入设置(即就业、移，工作人员，等等)。
- 创建一个有效的多元组和将它添加到您的暂定时间表。
- 如果不是有效的多元组可以创建，rollback(和增量)的最后一tuple加。
- 通过部分时间表的函数测试
could_schedule_be_valid, ，那就是，这个时间表可能是有效的，如果剩余的组填补了一个可能的方式 - 如果
!could_schedule_be_valid, 只需rollback(和增量)tuple加入(2)条。 - 如果
schedule_is_complete,return schedule - Goto(2)
你逐步建立一个局部转移这种方式。益的是，一些测试对于有效安排可以很容易地中的步骤2(预测)，和其他人必须保持步骤5(post-检验)。
好运气。我们浪费了天试的第一次两种算法，但得到的建议的算法产生有效的安排立即在以下5个小时的发展。
此外，我们支持预定后的固定分配算法将尊重。你根本不随机的那些槽步骤1。你会找到的解决办法没有被附近的任何地方最佳的。我们的方案是O(N*M)在最低限度，但执行在PHP(!) 在不到一半的第二个为整个制造工厂。美容是在排除不好的时间表迅速使用一个很好的 could_schedule_be_valid 测试。
人们用来做手工不在乎如果它需要一个小时-他们只知道他们没有做到手动。
迈克，
不知道如果你有了一个良好的答案，但我非常确定约束的编程的机票。虽然大会可能给你答案，CP的目的是给你的许多答复或者告诉你，如果没有可行的解决方案。搜索"约束规划"和调度应该带来了很多的信息。这是一个相对较新的领域和CP方法的工作以及在许多类型的问题在传统优化方法沼泽下来。
动态规划 a la Bell?听起来有点像没有一个地方:重叠的子问题，最佳的子结构。
有一件事你可以做的是试图寻找对称的问题。E.g。你可以把所有的护士作为同等目的的问题？如果是这样，那么你只需要考虑的护士在一些武断了-你可以避免考虑到这样的解决方案，任何护士 我 定之前，任何护士 j 哪里 我 > j.(你没有说那个护士选择移的时间，这违背了这个例子，虽然也许这是一个不太重要的目标是什么？)
使用CSP编程，我由导师的自动shitfs名册.例如：
- 2转移系统进行测试，用于100多个护士，30天的时间范围，将10+ 规则
- 3转移系统进行测试的80+护士，30天的时间范围，将10+规则
- 3转移系统，4-队伍-测试对于365天天边，10+规则，
和几个类似的系统。所有的他们测试了我的家庭PC(1.8千兆赫，双芯)。执行时间总是可接受的。3/花了大约5分钟300MB RAM。
最难的部分这一问题是选择适当的解和适当的解决战略。
启发式方法 做的非常好的 国际护士列入名册的竞争2010年.
为实现，看到这个 视频连续的护士列入名册(java).
