11

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

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

给出一个规模的概念:任何时候都会有大约 20 个资源,100 个出色的工作。完成作业需要 5-15 秒。招募一个资源大概需要1-2分钟,我们可以招募1-30分钟的时间(允许招募)。我们对提交的工作没有太多的注意,可能只有几秒钟。

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

我很感激有关算法、软件库或解决此问题的方法的指针。

4

9 回答 9

2

可能想研究背包问题垃圾箱包装问题,因为它们原则上与您在这里尝试做的事情相似。

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

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

于 2009-06-23T15:17:34.183 回答
1

这感觉像是几件事:经济订单数量,平衡前期招聘成本和运行成本;LP 或 IP,将受各种约束的总成本公式最小化;然后是概率分布(招聘时间;需要的工作资源?),使整个事情变得随机。

这听起来很复杂,如果我这样做,我可能会设置一个模拟。这样做的系统似乎不太复杂,或者在数学上过于繁琐而无法运行大量迭代或长时间运行,因此您可以获得一些相当稳定和有用的结果。

于 2009-06-23T15:50:52.500 回答
0

Awesome question!!

I would look into dynamic programming, linear optimization, and queueing theory. Unfortunately, there's no real easy way for me to answer these things. I do not have the mathematical expertise necessary to give you a solid, optimal answer for these things.

However, if you are keen on such things, this sounds like an opportunity to get a good, though likely not optimal, solution using an artificial intelligence algorithm. I would recomment either a genetic algorithm or a simulated annealer. Either of these will not take very long to code. The idea is that you pick random, valid inputs and you can tweak these potential solutions, evolving them into better ones (or picking new ones automatically) as time goes by. These are a good compromise between getting optimal answers and spending forever to code and prove correctness.

于 2009-06-23T18:46:23.580 回答
0

一些想法:

  • 是否有可以组合在一起的工作组——所有工作都具有相同的基本要求?
  • 有没有人也可以成群结队——都具备基本技能

如果是这样,那么您可以从一开始就减少一些复杂性,然后对偏好使用某种形式的加权平均值。另外,当你招募时,因为分钟。您可以招募 30 分钟,并且假设它们的成本较高,您可能希望确保它们具有最高的利用率水平。

以下是一些可能有帮助的文章:

于 2009-06-25T01:35:28.967 回答
0

我会这样看……不确定它是否涵盖了所有内容。

1)“资源”实际上可以被视为“工作中心”。 您有多少工作中心可以在“工作”上工作,这与登录系统的人有关。

2)按等待时间分配资源——他们等待工作的时间越长,他们应该在下一个请求的列表中越高。这样一来,任何人都不会感冒或放慢速度。您必须找到并设置一个阈值(相对于资源和工作)。您可以决定是否希望他们单击​​以选择下一份工作,或者让系统自动在工作之间找到一个

3) 设置作业计划队列 -我不知道它是否相关,但可能有高/低优先级作业等。您需要一个作业池,“按攻击顺序”列出。工作计划中的每项工作都可以经历不同的阶段,这样您就可以知道一切都在哪里,并知道什么时候完成才能进入下一个阶段。作业调度程序将查找可用资源并将它们分配给计划中的作业。这可能是您调度系统的大部分大脑。

我只是希望你没有建立一个外呼呼叫中心:P

于 2009-06-23T15:25:16.010 回答
0

这个问题可以看成一个线性优化问题,所以应该是一个开始。我用过这个,但是它还有很多其他的东西,所以它可能有点矫枉过正。相反,开发自己的库并不难,这本书有一个很好的关于LP的章节。

于 2009-06-23T18:04:07.970 回答
0

这听起来很像实时操作系统调度。维基百科详细介绍了一些使用的算法:

  • 协同调度
    • 循环调度
  • 抢占式调度
    • 固定优先级抢占式调度,抢占式时间片的一种实现
    • 临界区抢占式调度
    • 静态时间调度
  • 最早期限优先方法
  • 使用随机和 MTG 的高级调度
于 2009-06-23T18:52:29.527 回答
0

恐怕我没有一个简单的答案给你,但这里有一些更相关的资源来梳理想法。

关于多维包装问题

一种基于向量的动态资源分配策略

于 2009-06-23T18:20:40.500 回答
0

我不知道有关此类问题的文献。不过,我认为有一些,因为排队论是一个很大的学术领域,这听起来不像是一个荒谬的人为情况。请注意,您关心平均延迟而不是最坏情况延迟或第 N 个百分位延迟这一事实可能会使您成为少数派。

我的第一直觉是,由于周围似乎有很多工作,一个好的解决方案应该是连续雇用几个“灵活”的工人。这是一组工人,他们之间可以以可接受的延迟完成大多数类型的常见工作。您希望延迟越低,此集合中的资源就越多,它们花费的空闲时间就越多。此外,您的输入越“突发”(假设突发是不可预测的),您需要更多的空闲时间来防止突发期间的高延迟。

然后在两次情况下,您雇用了额外的“专业”工人:

1) 一种罕见的工作类型是,您当前的一组员工只能以高时间成本处理或根本无法处理。所以你雇佣(粗略地说)任何可以转移它的人,然后尽可能多地完成你的队列的其余部分。

2) 没有这样的工作,但你发现了一个机会,可以雇佣一个恰好能够从当前队列中移除一些工作组合的人,并且比你当前的员工更便宜,但不会让你当前的员工闲置. 所以你雇佣了那个资源。

至于实际算法:几乎可以肯定,找到最佳解决方案在计算上是不可行的,因此正确答案取决于处理资源,并且您正在研究启发式方法并解决部分问题。只要你雇佣的每个人都很忙,而且你不能雇佣其他人而不在未来的某个时候造成大量空闲时间,那么你可能就在一个好的解决方案附近,并且在某个地方接近“每块钱的最大收益” ” 延迟/成本权衡点。在此之后雇用更多资源会导致收益递减,但这并不意味着您不愿意为指定的延迟和/或指定的预算这样做。

但这取决于新来的工作是什么样的:如果你有一个资源只能做一种工作,而且该工作每天/每周/每年只来一次,那么最好每天雇用他们一次而不是等到你有足够的工作来填补他们可能的最短时间片(这就是为什么消防员大部分时间都在玩纸牌游戏,而打字员大部分时间都在打字。总有足够的打字时间让至少一个打字员忙,但是火灾是很少见的。此外,我们不想要“性价比最高”的火灾解决方案,我们想要比这更低的延迟)。因此,如果您正在解决问题的一个特定实例而不是编写通用调度软件,则可能有机会针对您的特定资源集和传入作业模式调整算法。

另外,如果资源是人,你实际上不能保证招聘成功。他们不会整天坐在那里,只在每分钟都有工作时才得到报酬,是吗?

于 2009-06-23T17:51:41.220 回答