| Article ID: | iaor19891081 |
| Country: | Netherlands |
| Volume: | 8 |
| Issue: | 6 |
| Start Page Number: | 351 |
| End Page Number: | 356 |
| Publication Date: | Dec 1989 |
| Journal: | Operations Research Letters |
| Authors: | Magirou V.F., Milis J.Z. |
An exhaustive search algorithm is presented for the assignment of tasks to processors in a distributed processing system so that the sum of execution and communication costs is minimized. The algorithm relies on an efficient lower bound generated by reducing the original task graph to a tree, for which the optimization problem is polynomial solvable. It is also pointed out that the problem is NP-complete even in the case of 3 processors.