3

鉴于我有这个 O(n!) 调度程序问题：

  • 我想在 5 天的工作周内安排 10 个不同持续时间的任务
  • 每天有 8 个工作小时，分为 15 分钟。插槽（1 天 = 8 小时 = 32 个插槽）
  • 这些任务在“允许的日期和时间范围”方面有不同的要求（例如，一项任务可能只允许在星期四上午 8 点至上午 9 点之间进行，另一项仅允许在周一、周二和周三上午 10 点至上午 11 点之间进行）

要求的结果： 应该有尽可能多的“连续空闲槽”可用于以后分配更多/其他任务

当前解决方案： 我尝试通过 BFS/DFS 解决方案组合所有可能的插槽，然后找到没有重叠任务和“最大空闲插槽块”的最佳组合。由于 O(n!) 的复杂性，这个解决方案在性能和/或内存方面会扼杀我。

问题： 在有限的时间内解决这个问题，计算机科学必须提供的最“合理”的方法是什么（或者也许你以前解决过这样的问题）。

4

6 回答 6

3

以下是可以相对容易地添加到深度优先搜索方法中的几件事，该方法首先探索最有前途的孩子：

1）有限差异搜索 - 基本上，当您探索作为其节点的第 x 个最佳子节点的子节点时，您通过累积 x 罚分来获得部分扩展的解决方案，并且您丢弃累积超过总罚分某个阈值的部分解决方案。搜索短语 Limited Discrepancy Search 应该会给你很多点击。这至少应该停止您对 n! 的搜索！秒。

2）给定一个可能非法的假定解决方案，将其用作爬山过程的开始以改进它或至少尝试使其合法。无论如何，您都需要这样做，以消除您的程序生成解决方案的可能性，用户可以在其中找到微不足道的改进。

于 2013-06-19T18:41:10.750 回答
2

您可能可以使用开源的OptaPlanner来解决这个问题。

另一种选择是使用贪心算法快速找到解决方案，首先安排最受约束的任务，最后安排最不受约束的任务。接下来，使用本地搜索到 a。使贪心解决方案有效并且 b. 改进贪心解法。例如，贪婪的解决方案可能会给您留下一个未安排的任务，因此本地搜索会取消安排一个冲突的任务并将未安排的任务安排在它的位置，然后重新安排新的未安排的任务。

于 2013-06-23T14:20:27.690 回答
1

由于任务的限制（允许的日期和时间范围），我会使用（递归）回溯。

来自维基百科（http://en.wikipedia.org/wiki/Backtracking）：

回溯是一种通用算法，用于找到某个计算问题的所有（或部分）解决方案，它逐步构建解决方案的候选者，并在确定 c 不可能完成时放弃每个部分候选者 c（“回溯”）有效的解决方案。

对于你的问题。我想说，让我们为每个任务分配可能的日期来安排。这是一个通用的解决方案。

M[level] 表示子问题的可能解决方案的集合（R[level]）

Backtracking(level = 0, result={0})
i = 0
Do
    i = i + 1 
    //With i - iterate over the possible solutions to result[level] (iterate over M[level])
    If(R[i] is a good result candidate) 
        k = 1
        While(k<level AND (R[k],R[i] are good solutions together)) k++
        If(k == level) //R[i] is a good result, it's in harmony with the results found before
            result[level] = R[i]
            If(level == N)
                bestResult = Max/Min(bestResult,result)
            Else
                Backtracking(level+1,result) //Backtracks
While(i<M[level])
于 2013-06-23T21:06:26.863 回答
0

可能要考虑简单的 AI，例如https://en.wikipedia.org/wiki/Support_vector_machine

有一些图书馆可供您尝试：

C# 的支持向量机库

此外，Boli 有一个很好的解决方案（递归回溯）。有关示例视频，请参阅评论。

于 2013-06-28T05:44:36.290 回答
0

您的数字是如此之小，这立即看起来像是在映射到一定程度的成功（效用）函数的所有可能解决方案中的蛮力方法的候选者。

于 2013-06-28T19:08:42.250 回答
-1

我总是更喜欢为问题创建自定义解决方案，而不是依赖通用方法。在这个特定的案例中，问题已经得到了很好的定义，我认为有一个快速可靠的迭代过程，可以相对容易地定义：通过遵循“填充天”的想法，将分析基于任务的顺序分配，直到完全的。

该算法将遍历可用 (5) 天，将与分配的每个任务相关的时间相加，并将结果添加与给定日期的剩余可用时间进行比较。它将包括两个主要部分：

  1. 最高优先级分配。一开始，该算法将计算给定日期的“灵活性”：它将在给定日期必须完成的任务的所有时间段相加。如果他们消耗了所有可用时间，所有这些任务的分配将立即完成，并直接跳到第二天。在有可用时间的情况下，算法只会分配具有详细（时间/天）定义的任务；示例：要在星期一执行的任务，包括给定的时段（例如，9 到 9:15）。完成所有详细定义任务的分配后，将在给定日期完成剩余任务所需的全部时间相加；这个值就是我在下面所说的“当天剩余”；属于该组的任务（即，

  2. 默认首选项规则。如果没有为上述给定日期分配所有可用时间，则将通过应用通用偏好规则系统开始对所有任务（不属于上述标记为给定日期的任务）进行新的迭代（如下面的例子所述）。在分配任何新任务之前，该算法会检查是否还有足够的时间来解决所有“当天剩余”的问题。如果新分配的任务耗尽了可用时间（即避免分配“当天的剩余时间”），算法将继续迭代“首选任务”（不属于“剩余时间”的任务）的一天”），直到找到一个其分配不会耗尽可用时间的人。如果找不到这样的任务，

第 2 点的优先规则示例：周一 9 点到 9:15 时段；首先在当天独立检查分配给特定时间的任务（不会是星期一，因为这些情况已经由第 1 点管理）；然后是可能在星期一完成的最大任务（更多插槽）。如果处于最后一种情况，也可以为任务创建排名（例如，在开始按大小最后排序的情况下，任务 X 将在星期一具有最大优先级）。

上面描述的算法（或这些行中的任何其他算法）代表了我可以为您遇到的问题提出的最快选择。它主要关注速度和可靠性，因此“许多连续空闲时隙”约束没有得到充分优化；尽管有创建这些的趋势（主要是在一周的最后几天）。尽管如此，最后一个问题可能会通过增加第 2 点中规则的详细程度来进一步改进（主要是按时间大小分配的任务）。总之，我确实认为这些方面的方法将为您提出的问题提供最佳解决方案。

于 2013-06-23T10:20:39.423 回答