Magirou, V. F.; Milis, J. Z. An algorithm for the multiprocessor assignment problem. (English) Zbl 0679.68055 Oper. Res. Lett. 8, No. 6, 351-356 (1989). 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. Cited in 17 Documents MSC: 68M20 Performance evaluation, queueing, and scheduling in the context of computer systems 90C27 Combinatorial optimization 68Q25 Analysis of algorithms and problem complexity Keywords:multiprocessor assignment; computational complexity; branch-and-bound PDF BibTeX XML Cite \textit{V. F. Magirou} and \textit{J. Z. Milis}, Oper. Res. Lett. 8, No. 6, 351--356 (1989; Zbl 0679.68055) Full Text: DOI OpenURL References: [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.