如何将一组任务最优地打包到最少数量的时隙中？

Question

我有一套

独立任务和

相同长度的时隙

，每个任意长度的任务

。

如何将任务分配到不同的时隙，同时将任务最小化。

Answer 1

你在看垃圾箱包装问题，这是NP-完全的。然而，存在很好的近似多项式解。

请参阅此链接：problem

Answer 2

下面是FFD (first )算法，它速度快，易于实现，并且非常接近最优解。

1. 将所有任务按成本降序排序，这将是我们的待定列表。
2. 选择挂起列表中的第一个剩余任务。
3. 找到最左边的插槽，把它放进去。
4. 从挂起列表中删除任务。
5. 当挂起的列表不是空的时候，从2开始重复。

这种算法最坏的性能是11/9*OPT + 1，在最坏的情况下，它需要比理论上的最小时隙多22%。