尽可能减少在P个代理上完成N个任务的时间

Question

我有N个任务，其中第I个任务需要A[i]时间来处理。每个任务彼此独立，并且可以在任何P个处理器上随时进行调度。一个任务只能在一个处理器上运行，一个处理器可以处理任意数量的任务。每个代理/处理器一次只能处理一个任务，并且一旦开始，必须继续处理它，直到任务完成

我想尽量减少完成所有任务所需的时间

我使用最小堆(即(来实现这一点

1. 按降序对任务进行排序
2. 创建初始化为0的大小为P的最小堆
3. 对于每个任务i，从堆中提取min，将任务时间A[i]添加到其中，然后将其添加回堆

完成所有任务的时间是堆中的最大值。到目前为止，这一直在工作，我想验证它的正确性

你认为这会中断任何输入吗？我相信我正在做类似贪婪数字分区的事情

Answer 1

这是一个多项式时间算法，用于将NP完全问题作为特例的问题(例如，对于p=2，您有一个子集和问题(。因此，你应该期望它并不总是有效的。

我能找到的最简单的情况是，如果权重是1, 1, 5, 5和P=2，那么你的算法会崩溃。你的算法应该结合这样的东西：

1 1 5 5
1,1 5 5
1,1,5 5

并且将花费7。你找不到的更好的解决方案是：

1,5 1,5

这将在6分钟内完成。