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.
|Original language||English (US)|
|Number of pages||19|
|State||Published - Nov 1990|
ASJC Scopus subject areas
- Computer Science Applications
- Management Science and Operations Research