作业队列优化算法

Question

我们有一个应用程序需要将作业分配给资源.资源具有许多属性,用于定义它们对特定作业的适用性 - 一些是偏好,一些是硬约束(所有成员类型,例如"资源A适合具有颜色X,Y或Z的作业").

资源具有与之相关的成本(它们在线上花费的持续时间).我们有能力招募资源 - 这需要不同的时间.我们可以按固定的时间间隔招募.

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

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

我非常感谢指向算法,软件库或解决此问题的方法.

Answer 1

可能需要研究背包问题或装箱问题，因为这些问题在原则上与您在这里尝试做的事情类似。

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

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