Probabilistic Analysis of Packing and Partitioning Algorithms

The problems to be studied in this book generally require the partitioning of a set S = {X sub 1, X sub 2,...,X sub n} of non-negative numbers so that the sums of the elements in the blocks of the partition satisfy some given property. For example, an instance of the makespan scheduling problem is made up of S and an integer m greater than or equal to 2; the objective is to find a partition of S into m blocks so that the maximum block sum (i.e. makespan) is minimized over all such partitions. Although there are many possible interpretations in the one motivating the name of the problem each X sub i represents a task or job running time an a block corresponds to the set of tasks to be run on the same processor of an m-processor multiprocessor system.