Multistage linear array assignment problem

R. K. Kincaid, D. M. Nicol, D. R. Shier, D. Richards

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)974-992
Number of pages19
JournalOperations Research
Volume38
Issue number6
StatePublished - Nov 1 1990
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Multistage linear array assignment problem'. Together they form a unique fingerprint.

Cite this