Minimizes the total time of 2 processors using max flow or min cut

Question

This is a question from CSE521: Design and Analysis of Algorithms I

Question:
In this problem we investigate a two-processor assignment of program modules.
Assume that there are n program modules indexed 1, 2, . . . , n and two processors A and B. If program module i is executed on one processor and program module j on the other then the time for interprocessor communication is cij ≥ 0. We assume that cij = cji. The processors have different speeds so that program module i takes time Ai on processor A and Bi on processor B.
The problem is to find an assignment of the program modules to processors that minimizes the total time. Reduce this problem to the max flow or the min cut problem. Argue briefly that your reduction is correct.

An example to demonstrate the question:
Table: time cost on processors, 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 }
and the rest have 0 communication time cost

One way to assign the modules to the two processors is
assigning 1 to A, 2 to A, 3 to A, 4 to B
and the total time cost = A1+A2+A3+B4+c24+c34 = 6+5+10+8+2+1

We want to minimize the total time cost.

This is my solution:

let G=(V,E) V={p1, p2, v1,...,vn}, and E={(p1,vi),(vi,p2): i=1..n}U{(vi,vj): cij}. p1 and p2 are the source and sink.

For i=1..n, the weight for edge (p1,vi) is Ai and Bi for (vi, p2). The weight for (vi, vj) is cij=cji.

And then I'm stocked.
I think the min-cut that cut the graph G into two vertex sets might be the answer.

What am I misunderstanding here?

Answer 1

Assuming that the objective is to minimize total time rather than elapsed:

• Assign every task to its most efficient processor.

• Check for every task pair that incur a communications cost because they have been assigned different processors. If the "total time" would be reduced by assigning them to the same processor, then do so.

( I cannot imagine any scenario where this 'optimization' would have any utility in the real world. )