0

我正在尝试清理当前正在使用优先级 FIFO 调度算法的企业 BI 系统（因此周二的优先级 4 报告将在周四的优先级 4 报告和周一的优先级 3 报告之前执行。）其他详细信息：

  • 队列永远不会为空，总是在添加作业
  • 作业的执行时间从不到一分钟到超过 24 小时不等
  • 有 40 个奇怪的相同应用服务器用于执行作业

我想我可以让 optaPlanner 启动并运行这种情况，围绕优先级制定硬性规则，围绕队列中的平均时间制定一些软性规则。我是调度优化的新手，所以我想我的问题是在这种情况下我应该寻找什么来决定 optaPlanner 是否会帮助我？

4

1 回答 1

3

这个问题看起来像是一种装箱形式（可能还有作业车间调度），它们是NP-complete 的，因此 OptaPlanner 会比 FIFO 算法做得更好。

但它真的是NP-complete吗？如果满足所有这些条件，则可能不是：

  • 所有 40 台服务器都是相同的。因此，在服务器 A 而不是服务器 B 上运行优先级报告不会更快地交付报告。
  • 所有 40 台服务器都是相同的。所以总持续时间（对于特定的输入集）是一个常数。
  • 总制造时间无关紧要。因此，给定 20 个 1 小时的小作业和 1 个 20 小时的大作业和 2 台机器，考虑到总工时为 30 小时，在大作业开始前 10 小时后完成所有小作业是可以的。不希望将制造时间缩短到 20 小时。
  • “队列中的平均时间”是有争议的：您是否关心作业在队列中等待多长时间才能开始或完成？如果总持续时间是一个常数，这可以通过先或最后对小作业进行 FIFO 来完成（当然，同时仍然尊重优先级）。
  • 作业之间没有依赖关系。

如果满足所有这些条件，OptaPlanner 将无法比正确编写的贪心算法做得更好（它首先调度最小/最大的最高优先级作业）。如果不满足这些条件中的任何一个（例如，您购买了 10 台速度更快的新服务器），那么 OptaPlanner 可以做得更好。您只需要评估是否值得花费 1 个线程来解决这个问题。

如果您使用 OptaPlanner，请务必查看实时调度和守护程序模式，以便在新报告进入系统时重新计划。

于 2014-10-14T07:54:58.260 回答