使用最大流或最小切割最小化 2 个处理器的总时间

Question

这是CSE521：算法设计与分析I的问题

问题：
在这个问题中，我们研究程序模块的两个处理器分配。
假设有 n 程序模块索引为 1, 2, ...。 。 。 ， n 和两个处理器 A 和 B。如果程序模块 i 在一个处理器上执行，程序模块 j 在另一个处理器上执行，则处理器间通信的时间为 cij ≥ 0。我们假设 cij = cji。处理器具有不同的速度，因此程序模块 i 在处理器 A 上花费时间 Ai，在处理器 B 上花费时间 Bi。
问题是找到程序模块到处理器的分配，以最小化总时间。 将这个问题简化为最大流或最小割问题。简要论证你的还原是正确的。

演示问题的示例：
表：处理器的时间成本，n=4

 i  1  2  3  4    
Ai  6  5 10  4     
Bi  4 10  3  8   

cij = { c(1,2)=5, c(2,3)=6, c(2,4)=2, c(3,4)=1 }
其余的都是0沟通时间成本

将模块分配给两个处理器的一种方法是
将 1 分配给 A，2 分配给 A，3 分配给 A，4 分配给 B
总时间成本 = A1+A2+A3+B4+c24+c34 = 6+5+10+8+2+1

我们希望最小化总时间成本。

这是我的解决方案：

设 G=(V,E) V={p1, p2, v1,...,vn}，且 E={(p1,vi),(vi,p2): i=1..n}U{ (vi,vj): cij}。 p1 和 p2 是源和汇。

对于 i=1..n，边 (p1,vi) 的权重为 Ai，(vi, p2) 的权重为 Bi。 (vi, vj) 的权重为 cij=cji。

然后我就有货了。
我认为将图 G 切割成两个顶点集的最小切割可能就是答案。

我在这里误解了什么？

Answer 1

假设，正如 @Jaka C 所建议的，目标是最小化总时间而不是流逝时间：

• 将每项任务分配给最高效的处理器。

• 检查因分配了不同处理器而产生通信成本的每个任务对。如果通过将它们分配给同一处理器可以减少“总时间”，那么就这样做。

（我无法想象这种“优化”在现实世界中会有任何效用的任何场景。）