ABSTRACT
This case study is devoted to the chains-on-chains partitioning (CCP) problem. Given an array of n elements a1, a2, . . . , an, the problem is to partition the array into p intervals whose element sums are well balanced. This problem has been extensively studied in the literature because it has various applications. In particular, it amounts to load-balancing n computations whose ordering must be preserved (hence, the restriction to intervals) onto p processors. Then, each ai corresponds to the execution time of the i-th task, and the sum of the elements in interval Ik is the load of the processor to which Ik is assigned. Several algorithms and heuristics have been proposed to solve this load-balancing problem, including [19, 47, 52, 53, 81]. We refer the reader to the survey paper by Pinar and Aykanat [86] for a detailed overview and comparison of the literature.
