1

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

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

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

问题:如果我控制调度程序(意味着哪个消费者得到什么项目),我如何找出哪些项目分配将使消费者最快完成(消耗所有项目)。

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

4

1 回答 1

0

我相信这是装箱问题的一种变体,你有两个不同大小的箱子,而不是一个箱子;您希望最小化使用的 bin 总数,并且您希望使用大致相同数量的每个 bin 类型。这是一个 NP-Hard 问题。

请注意,我认为这里使用的生产者数量不相关。

于 2013-04-24T13:54:25.797 回答