我不知道有关此类问题的文献。不过,我认为有一些,因为排队论是一个很大的学术领域,这听起来不像是一个荒谬的人为情况。请注意,您关心平均延迟而不是最坏情况延迟或第 N 个百分位延迟这一事实可能会使您成为少数派。
我的第一直觉是,由于周围似乎有很多工作,一个好的解决方案应该是连续雇用几个“灵活”的工人。这是一组工人,他们之间可以以可接受的延迟完成大多数类型的常见工作。您希望延迟越低,此集合中的资源就越多,它们花费的空闲时间就越多。此外,您的输入越“突发”(假设突发是不可预测的),您需要更多的空闲时间来防止突发期间的高延迟。
然后在两次情况下,您雇用了额外的“专业”工人:
1) 一种罕见的工作类型是,您当前的一组员工只能以高时间成本处理或根本无法处理。所以你雇佣(粗略地说)任何可以转移它的人,然后尽可能多地完成你的队列的其余部分。
2) 没有这样的工作,但你发现了一个机会,可以雇佣一个恰好能够从当前队列中移除一些工作组合的人,并且比你当前的员工更便宜,但不会让你当前的员工闲置. 所以你雇佣了那个资源。
至于实际算法:几乎可以肯定,找到最佳解决方案在计算上是不可行的,因此正确答案取决于处理资源,并且您正在研究启发式方法并解决部分问题。只要你雇佣的每个人都很忙,而且你不能雇佣其他人而不在未来的某个时候造成大量空闲时间,那么你可能就在一个好的解决方案附近,并且在某个地方接近“每块钱的最大收益” ” 延迟/成本权衡点。在此之后雇用更多资源会导致收益递减,但这并不意味着您不愿意为指定的延迟和/或指定的预算这样做。
但这取决于新来的工作是什么样的:如果你有一个资源只能做一种工作,而且该工作每天/每周/每年只来一次,那么最好每天雇用他们一次而不是等到你有足够的工作来填补他们可能的最短时间片(这就是为什么消防员大部分时间都在玩纸牌游戏,而打字员大部分时间都在打字。总有足够的打字时间让至少一个打字员忙,但是火灾是很少见的。此外,我们不想要“性价比最高”的火灾解决方案,我们想要比这更低的延迟)。因此,如果您正在解决问题的一个特定实例而不是编写通用调度软件,则可能有机会针对您的特定资源集和传入作业模式调整算法。
另外,如果资源是人,你实际上不能保证招聘成功。他们不会整天坐在那里,只在每分钟都有工作时才得到报酬,是吗?