## 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 1 1990 |

Externally published | Yes |

## ASJC Scopus subject areas

- Computer Science Applications
- Management Science and Operations Research