algorithm - 作业队列优化算法

Question

我们有一个应用程序需要将作业分配给资源。资源具有许多定义其对特定工作的适用性的属性——一些是偏好，一些是硬性约束(所有成员种类，例如“资源 A 适合颜色为 X、Y 或 Z 的工作”。

资源有与之相关的成本(他们在线花费的时间)。我们有能力招募资源——这需要不同的时间。我们可以在固定的时间间隔内招聘。

给出规模的概念:在任何给定时间都会有大约 20 种资源，100 个未完成的工作。完成作业需要 5-15 秒。招募资源大约需要 1-2 分钟，我们可以在 1-30 分钟的时间内招募(允许重新招募)。我们对正在提交的作业没有太多提醒，可能需要几秒钟。

目标是在给定的平均延迟(作业完成时间)内以最低成本(资源使用)完成作业。

如果能提供算法、软件库或解决此问题的方法，我将不胜感激。

Answer 1

可能想查看 knapsack problem或 bin packing问题，因为这些原则上与您在此处尝试执行的操作类似。

在您的问题描述中，您提到目标是以最低延迟完成作业。如果这实际上是您唯一的目标，那么解决方案很简单——雇用所有可用资源。他们中的许多人大部分时间都是空闲的，但它几乎可以保证尽可能低的延迟。

我怀疑您的真正目标是尽可能地减少延迟和空闲资源，因此这里总是会在延迟和浪费的资源之间进行权衡。