Abstract
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) |
---|---|
Pages (from-to) | 974-992 |
Number of pages | 19 |
Journal | Operations Research |
Volume | 38 |
Issue number | 6 |
State | Published - Nov 1990 |
Externally published | Yes |
ASJC Scopus subject areas
- Computer Science Applications
- Management Science and Operations Research