A MULTISTAGE LINEAR-ARRAY ASSIGNMENT PROBLEM

• 成果类型: Article
• 署名作者: KINCAID, RK; NICOL, DM; SHIER, DR; RICHARDS, D
• 署名单位: University of Virginia
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.38.6.993
• 发表日期: 1990
• 页码: 993-1005
• 关键词: computers; PARALLEL ALGORITHMS AND WORKLOAD BALANCING; networks; Applications; multiobjective optimization

摘要

Implementation of certain algorithms on parallel computing architectures may involve partitioning contiguous elements into a fixed number of groups, each to be handled by a single processor. We wish to find an assignment of elements to processors that minimizes the sum of the maximum workloads experienced at each stage. This problem may be viewed as a multiobjective network optimization problem. Polynomially-bounded algorithms are developed for the case of two stages, whereas the general problem, for an arbitrary number of stages, is shown to be NP-hard. Heuristic procedures are therefore proposed and analyzed for the general problem. Computational experience with one of the exact algorithms, incorporating certain pruning rules, is presented for a variety of test problems. Empirical results also demonstrate that one of the heuristic procedures is especially effective in practice.