logo标签列表

作业队列优化算法

algorithmscheduling
11
我们有一个应用程序需要将工作分配给资源。这些资源具有许多属性，定义了它们对特定工作的适合程度——其中一些是偏好，一些是硬性约束（全是成员类型，例如，“资源A适合颜色为X、Y或Z的工作”）。
资源有一个与之相关的成本（在线时间）。我们可以招募资源——这需要不同的时间量。我们可以在固定的时间间隔内进行招募。
为了估计规模：任何时候都会有大约20个资源，100个未完成的工作。完成工作需要5-15秒。招募资源需要1-2分钟，我们可以在1-30分钟的时间内招募（允许重新招募）。我们没有太多提前了解提交的工作，也许只有几秒钟的时间。
目标是以最低的成本（资源使用）完成工作，并保持给定平均延迟（工作完成时间）不变。
我希望得到关于算法、软件库或解决此问题的方法的指导。
抱歉，资源是有成本的。我已经编辑了帖子以使这一点更清晰。平衡延迟（作业等待时间）+成本是问题所在。 - sehugg
不幸的是，这个问题无法通过优化来解决。这是一个管理问题。 - ebo
杰出的工作 - 它们是提前知道的，还是有一些随机分配来确定它们何时到达以及需要什么资源？如果是后者，那么这个过程的持续时间是多久？这将影响到工作完成和资源招募的时间。 - user447688
看起来你正在尝试解决一个可能很难的问题，这取决于你想要解决得有多好。乍一看，它听起来像是你正在尝试做一些“作业车间调度”、“工作计划”、“约束规划”、“作业排队”等领域的事情。许多问题都是NP难的。你可以用我提供的一些短语在谷歌上搜索，以确定我们所处的领域。 - jitter
我说“需要” - 它想要，因为越早雇用资源并期望其被充分利用，就越好。 - Steve Jessop
显示剩余5条评论
9个回答
2
您可能想要研究背包问题或装箱问题，因为这些问题在原则上与您在此处尝试的类似。
在您的问题描述中，您提到目标是以最低延迟完成作业。如果那确实是您唯一的目标，那么解决方案很简单-雇用所有可用资源。其中许多资源大部分时间都会空闲，但几乎可以保证最低可能的延迟。
我怀疑您的真正目标是尽可能地减少延迟和空闲资源，因此在这里始终存在延迟和浪费资源之间的某种权衡。
是的，我没有明确说明资源在线时间会产生成本。抱歉。 - sehugg
1

这感觉像是几个方面：经济订货量，平衡前期招聘成本和运行成本；线性规划或整数规划，最小化总成本的公式，同时受到各种限制条件的约束；还有概率分布（招聘时间；所需工作资源？），使整个过程具有随机性。

听起来足够复杂，如果我在做这件事，我可能会建立一个模拟。这种方式似乎不太复杂，也不需要进行大量迭代或长时间运行的数学负担，因此您可以获得一些相当稳定和有用的结果。

John，感谢你的评论，现在我有新的和旧的东西要去Google ;)招聘问题似乎主要是一个预测问题，因为当我招募资源时，期望的工作完成时间已经过去了。我知道解决预测问题的唯一方法是“保持耐心” :)我认为可以优化的部分是最大限度地利用可用资源，而这对我来说似乎是NP难问题。模拟可能是正确的方法。 - sehugg
你需要建立一些启发式招聘策略，这显然是基于预期需求、现有能力、招募前期成本VS空置资源时间成本等方面的考虑。这就是模拟的好处：你可以进行设置，然后测试各种启发式方法，直到找到看起来成本较低的那个为止。 - user447688
0

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

1) "资源" 实际上可以被视为 "工作中心"。 有多少个工作中心可以用来处理 "工作" 取决于谁登录了系统。

2) 按等待时间分配资源 - 等待工作的时间越长，他们在下一个请求的列表中就应该越靠前。这样就不会有人感到冷或者减速。您需要找到并设置一个门槛，根据此门槛（相对于资源和工作），您可以决定是让他们点击以获取下一个工作，还是让系统在工作之间自动获取一个工作。

3) 设置作业计划队列 - 我不知道这是否相关，但可能会有高/低优先级的作业等。你需要一个作业池，按 "攻击顺序" 列出。作业计划中的每个作业都可以通过不同的阶段，因此你知道每件事情的进展情况，并且知道何时完成后移动到下一个阶段。作业调度程序将寻找可用资源并将其分配给作业计划中的作业。这很可能是您安排系统的大部分核心。

我只希望你不是在建立一个出站呼叫中心 :P

嗯...2)? 变冷会变慢吗？我们在谈论真实的人吗？我以为这是关于计算机进程作为工人执行“一些工作”（例如在线搜索某些内容）的问题。 - jitter
顺便说一下，这不是一个外呼中心 ;) - sehugg
@Jitter；是的，我在谈论人。我不确定这种情况是否适用于人，所以我假设它是适用的。当在任何类型的生产线/队列上工作时，保持稳定的流程和节奏至关重要。你不想走得太快或太慢，因为两者都会对产出（和错误）产生太大影响。对于程序员来说，当我们想进入并保持处于一种状态时，情况也类似。如果我们在输入/输出之间等待时间太长，我们容易失去注意力。希望这有所帮助。 - Jas Panesar
@sehugg 你可能想要根据人才/技能/能力/速度将你的资源分开，将更快、更准确的放在队列的优先部分，让其他人逐渐提高。这样你就可以让无错误和快速工作的文化贯穿应用程序和组织中。很高兴听到它不是一个外向的抄送。如果你能提供更多细节，也许我说的话可以更加具体？ - Jas Panesar
此外，您可以为资源创建性能公式，以便趋势表现良好且应该（或可能符合）高队列的资源。一开始一个简单的公式就足够了... - Jas Panesar
显示剩余5条评论
0

我对这类问题的文献不太了解。不过，排队理论是一个广泛的学术领域，而这种情况并不像是一个荒谬的编造。当然，你关心的是平均延迟，而不是最坏情况下的延迟或第N个百分位数的延迟，这可能会让你成为少数派。

我的第一反应是，既然似乎有很多工作机会，那么一个好的解决方案就是雇用几个“灵活”的工人持续就业。这是一组工人，他们之间可以完成大多数常见工作，并且延迟可接受。你想要的延迟越低，这个集合中的资源就越多，他们花费的空闲时间也就越多。此外，如果输入是“突发性”的（假设突发事件是不可预测的），则需要更多的空闲时间以防止在突发事件期间出现高延迟。

然后，在两个场合你会雇用额外的“专业”工人：

1）出现了一种罕见类型的工作，你当前雇用的人只能以高时间成本或根本无法处理。因此，你雇用（粗略地说）能够处理它并且能够完成其余队列中大部分工作的人。

2) 没有这样的工作，但是您发现有机会雇用某些人，他们碰巧能够从当前队列中取出某些组合的工作，并以比您目前雇用的人更便宜的价格完成它们，但不会让您目前雇用的人空闲。因此，您雇用了这个资源。

至于实际算法：几乎肯定无法找到最佳解决方案，因此正确答案取决于处理资源，您正在寻找启发式和解决部分问题。只要您雇用的每个人都很忙，并且您不能雇用其他人而不在未来某个时间点导致显着的空闲时间，您可能在一个很好的解决方案附近，并且在延迟/成本权衡的“最大回报”点附近。在那之后再雇用更多资源将带来递减的回报，但这并不意味着您不愿意为指定的延迟和/或指定的预算这样做。

但这取决于传入的工作类型：如果您有一个只能做一种类型工作的资源，并且该工作每天/每周/每年只出现一次，那么最好是每天雇用他们，而不是等到有足够的工作来填补他们最小可能的时间片（这就是为什么消防员大部分时间都在打牌，而打字员大部分时间都在打字。总是有足够的打字工作让至少一个打字员忙碌，但火灾很少发生。此外，我们不希望对于火灾采用“性价比最高”的解决方案，我们需要比这更低的延迟）。因此，如果您正在解决问题的一个特定实例而不是编写通用调度软件，则可能存在调整算法以适应您特定资源集和传入工作模式的机会。

此外，如果资源是人类，您可能无法保证招聘成功。他们不会整天坐在那里，按分钟计算报酬，对吧？

感谢您的帖子，提供了很好的想法。我认为招聘情况很有趣，因为您想要雇用“通才”，他们有最大的机会解决即将出现的大多数工作，而不是“专家”在某些工作上做得更好，但无法完成其他工作。我几乎担心我的问题太普遍了 :) 我也担心最坏情况下的延迟，我的直觉告诉我那样做是难以处理的。 - sehugg
0

这个问题可以看作是线性优化问题，所以 这里应该是一个很好的开始。我曾经使用这个库，但它有很多其他的功能，可能会有点过度。相反，开发自己的库并不难， 这本书 中有一个关于线性规划的好章节。

0
0

太棒了的问题！！

我会研究动态规划、线性优化和排队理论。不幸的是，我无法以简单的方式回答这些问题。我没有数学专业知识，无法为这些问题提供坚实、最佳的答案。

然而，如果你对这些事情感兴趣，这听起来像是一个使用人工智能算法得到好的解决方案的机会，虽然可能不是最优的。我建议使用遗传算法或模拟退火算法。这两种方法都不需要很长时间编码。思路是选择随机的有效输入，然后可以调整这些潜在的解决方案，随着时间的推移将它们演变成更好的解决方案（或自动选择新的解决方案）。这是在获取最佳答案和花费大量时间编码和证明正确性之间的一个很好的折衷。

0

这听起来非常像实时操作系统调度。维基百科详细介绍了一些算法：

  • 合作式调度
    • 轮流调度
  • 抢占式调度
    • 固定优先级的抢占式调度，是抢占式时间片的一种实现
    • 临界区抢占式调度
    • 静态时间调度
  • 最早截止时间优先方法
  • 使用随机和MTG的高级调度
这是正确的，但在这里找出时间表是困难的部分，而不仅仅是选择将要使用的调度算法。 - San Jacinto
0

一些想法：

  • 能否将一些有着相同基本要求的工作分组？
  • 有没有人也可以分组，他们都具备基本技能？

如果是这样，你就可以从一开始减少一些复杂性，然后使用某种形式的加权平均值来考虑偏好。另外，在招聘时，既然你最小的招聘时间为30分钟，并且假设他们成本更高，你可能希望确保他们具有最高的利用率。

这里有一些可能有所帮助的文章：

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接