算法:某种版本的生产者/消费者？调度

Question

我不确定这是否是生产者/消费者问题，但我找不到更好的方式来表达我的问题。

我想知道这个问题(或类似问题)是否已得到解决。如果没有，是NP问题吗？这是问题的描述和我要回答的问题

• 假设您有 4 个生产者和 2 个消费者。
• 假设您已经知道生产者将要生产的所有东西(作为项目列表，每个项目的大小不同)
• 假设每个消费者可以以不同的速度消费任何数据(例如，消费者 1 消费任何项目的速度是消费者 2 的两倍)

问题:如果我控制调度器(即哪个消费者得到什么元素)，我如何找出元素的什么分配将使消费者最快完成(消耗所有元素)。

我希望这是有道理的。我花了几个小时思考这个问题，然后又花了几个小时寻找可能的解决方案，但仍然没有运气。希望我能从大家那里得到一些头脑 Storm /解决方案。提前致谢!

Answer 1

我相信这是 bin-packing problem 的变体，在这里你有两个不同大小的垃圾桶而不是一个垃圾桶；您希望最大程度地减少使用的箱子总数，并且您希望使用大致相同数量的每种箱子类型。这是一个 NP-Hard 问题。

请注意，我认为这里使用的生产者数量无关紧要。