Skip to main content
Open Access Publications from the University of California

One-Dimensional Partitioning for Heterogeneous Systems: Theory and Practice


We study the problem of one-dimensional partitioning of nonuniform workload arrays with optimal load balancing for heterogeneous systems. We look at two cases: chain-on-chain partitioning, where the order of the processors is specified, and chain partitioning, where processor permutation is allowed. We present polynomial time algorithms to solve the chain-on-chain partitioning problem optimally, while we prove that the chain partition is NP-complete. Our empirical studies show that our proposed exact algorithms produce substantially better results than heuristics while the solution times remain comparable.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View