1

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

4

2 回答 2

1

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

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

话虽如此，通过使用混合整数线性规划 (MILP) 并使用 Cplex 或 Gurobi 等最佳线性求解器（我几乎不认为像 LP-solve 这样的开源求解器可以处理超出一定规模的问题）。

此处描述了适用于此问题的 MILP 模型示例。

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

编辑 ：

一种可能的蛮力方法是计算任务 TASK-PROCESSOR 的所有可能组合，然后计算制造跨度。这是 C/C++ 中的一个示例

于 2012-05-01T18:20:42.300 回答
0

首先计算完成所有处理所需的总线性时间（将所有任务的持续时间相加）。现在除以数量或处理器，m。

这是您的目标平均时间。您想找到每个处理器的持续时间组合，它们加起来尽可能接近这个数字

最基本的方法是：

avg = <the average from earlier>
list = <all jobs>
FOR i = 0 to m
    WHILE duration(processor[i]) < avg:
        processor[i].add(longest lasting job in `list` that will keep the time less than `avg`

这将在最后留下一些作业，将持续时间最长的作业添加到最短的处理器时间，直到没有作业留在list

于 2012-05-01T18:10:34.803 回答