A multistage linear array assignment problem

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. The authors 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.