c++ - 需要包含运行任务时间的二维矩阵的最优解

Question

我有一个由 m 个处理器(列)和 n 个任务(行)组成的二维矩阵，该矩阵填充了每个进程在处理器上运行所花费的时间，我需要找到运行这 n 个任务的最佳时间m 个处理器。

Answer 1

所描述的问题属于并行机器调度问题的范畴。
此外，由于每个任务在不同处理器上花费的时间不同，因此该问题称为统一机器调度问题。

此类问题具有很强的 NP-hard 问题，因此没有已知的多项式时间算法。因此，除非矩阵非常小，否则真的不鼓励使用蛮力方法，因为复杂度类似于 O( n ^ m )。

也就是说，通过使用混合整数线性规划 (MILP) 并使用 Cplex 或 Gurobi 等最佳线性求解器求解它(我几乎不认为开源求解器像LP-solve 可以处理超过一定规模的问题)。

描述了适用于此问题的 MILP 模型示例 here .

但是，考虑到它们的复杂性，此类问题通常使用启发式/元启发式方法来解决，因此无法确保达到最佳解决方案。无论如何，一个好的贪心算法加上一个好的局部搜索来改进贪心解，可以非常接近最优。

编辑:

一种可能的蛮力方法是计算所有可能的任务组合 TASK-PROCESSOR，然后计算完工时间。 Here's an example in C/C++