An algorithm for the multiprocessor assignment problem. (English) Zbl 0679.68055

Summary: 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 polynomially solvable. It is also pointed out that the problem is NP-complete even in the case of 3 processors.


68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90C27 Combinatorial optimization
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Bokhari, S.H., A shortest tree algorithm for optimal assignment across space and time in a distributed processor system, IEEE trans. soft. eng., 7, 583-589, (1981)
[2] Bokhari, S.H., Assignment problems in parallel and distributed computing, (1987), Kluwer Academic Publishers MA
[3] Dahlhaus, E.; Johnson, D.S.; Papadimitriou, C.H.; Seymour, P.; Yannakakis, M., The complexity of multi-way cut, (1987), Unpublished manuscript
[4] Gehrlin, W.V., On methods for generating random partial orders, Oper. res. lett., 5, 285-291, (1986) · Zbl 0606.90078
[5] Ma, P.R.; Lee, E.Y.S.; Tsuchiya, M., A task allocation model for distributed computing systems, IEEE trans. comput., 31, 41-47, (1982)
[6] Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization: algorithms and complexity, (1982), Prentice-Hall NJ · Zbl 0503.90060
[7] Price, C.C., The assignment of computational tasks among processors in a distributed system, (), 291-296
[8] Price, C.C.; Pooch, U.W., Search techniques for a nonlinear multiprocessor scheduling problem, Naval res. logist. quart., 29, 213-233, (1982) · Zbl 0535.68016
[9] Sedgewick, R., Algorithms, (1983), Addison-Wesley MA · Zbl 0529.68002
[10] Stone, H.S., Multiprocessor scheduling with the aid of network flow algorithms, IEEE trans. soft. eng., 3, 85-93, (1977) · Zbl 0355.68042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.