作业队列优化算法 [英] Job queue optimization algorithms

问题描述

我们有一个需要将作业分配给资源的应用程序。资源具有许多属性，这些属性定义了它们对特定作业的适用性-有些是首选项，有些是硬约束（所有成员资格都不同，例如资源A适合于具有X，Y或Z颜色的作业。

We have an application that requires assignment of jobs to resources. The resources have a number of attributes that define their suitability to a particular job -- some are preferences, some are hard constraints (all of the membership variety, e.g. "resource A is suited to jobs with color X, Y, or Z".

资源具有与之相关的成本（它们在网络上花费的持续时间）。我们具有募集资源的能力-这需要花费可变的时间。

Resources have a cost associated with them (the duration they spend on-line). We have the ability to recruit resources -- this takes a variable amount of time. We can recruit for a fixed interval of time.

要给出规模的构想：在任何给定时间大约有20种资源，有100个出色的工作。 5到15秒。招聘资源大约需要1-2分钟，而我们可以从1到30分钟的时间内进行招聘（允许招聘）。我们对提交的工作没有太多的了解，也许是几秒钟

To give an idea of scale: There will be about 20 resources at any given time, 100 outstanding jobs. Completion of jobs takes 5-15 seconds. Recruiting a resource takes about 1-2 minutes, and we can recruit from 1-30 minutes of time (rerecruiting is allowed). We don't have much heads-up on jobs being submitted, maybe a few seconds.

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

The goal is completion of jobs with lowest cost (resource usage) for a given average latency (job completion time).

我很感谢指向算法的指针，所以ftware库或解决此问题的方法。

I'd appreciate pointers to algorithms, software libraries, or approaches to solving this problem.

推荐答案

可能想研究背包问题或 bin包装问题，因为这些原则上与您在此处尝试的操作类似。

Might want to look into the knapsack problem or the bin packing problem as those are similar in principle to what you are trying to do here.

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

In your problem description you mention that the goal is the completion of jobs with the lowest latency. If that is actually your only goal, then the solution is simple - hire all available resources. Many of them will be idle much of the time, but it pretty much guarantees the lowest possible latency.

我怀疑您的真正目标是尽可能减少延迟和空闲资源，因此在这里，延迟和浪费资源之间总会有一些折衷

I suspect that your real goal though is to minimize both latency and idle resources as much as possible, so there will always be some tradeoff between latency and wasted resources in play here.

这篇关于作业队列优化算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！