我有一个由 m 个处理器(列)和 n 个任务(行)组成的二维矩阵,该矩阵填充了每个进程在处理器上运行所花费的时间,我需要找到运行这 n 个任务的最佳时间m 个处理器。
最佳答案
所描述的问题属于并行机器调度问题的范畴。
此外,由于每个任务在不同处理器上花费的时间不同,因此该问题称为统一机器调度问题。
此类问题具有很强的 NP-hard 问题,因此没有已知的多项式时间算法。因此,除非矩阵非常小,否则真的不鼓励使用蛮力方法,因为复杂度类似于 O( n ^ m )
。
也就是说,通过使用混合整数线性规划 (MILP) 并使用 Cplex 或 Gurobi 等最佳线性求解器求解它(我几乎不认为开源求解器像LP-solve 可以处理超过一定规模的问题)。
描述了适用于此问题的 MILP 模型示例 here .
但是,考虑到它们的复杂性,此类问题通常使用启发式/元启发式方法来解决,因此无法确保达到最佳解决方案。无论如何,一个好的贪心算法加上一个好的局部搜索来改进贪心解,可以非常接近最优。
编辑:
一种可能的蛮力方法是计算所有可能的任务组合 TASK-PROCESSOR,然后计算完工时间。 Here's an example in C/C++
关于c++ - 需要包含运行任务时间的二维矩阵的最优解,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10401955/