7.1 Introduction

7.1.1 Problems

The problems studied here all involve the partitioning of a set of positive numbers into a collection of subsets satisfying a sum constraint. The following two problems are among the most fundamental. They have wide-ranging applications throughout computer science and operations research (see, e.g., Coffman et al., 1984b; Coffman et al., 1988; and Dyckhoff, 1990).

Bin Packing (BP). Given c > 0 and a set S = {X1, ..., Xn} with , , partition S into a minimum number of subsets such that the sum of the Xi's in each subset is no more than c.

The Xi's are usually called items or pieces and are thought of as being packed into bins B1, B2, ..., each with capacity c; the items packed in a bin constitute one of the subsets in a solution to the optimization problem.

Multiprocessor Scheduling (MS). Given an integer and a set S = {X 1, ..., Xn}, partition S into m subsets such that among all such partitions, the maximum subset sum is minimized.

Note that the MS problem is complementary to the BP problem in that the objective function and the given parameter are interchanged. The items are now called tasks or jobs, with running times or durations instead of sizes. The bins become processors P1, ..., Pm, and the partition becomes a schedule of S on m processors that minimizes the makespan c, i.e., the completion time of a latest finishing task. Because of the sequential nature of most heuristics, it is convenient to assume that the set to be partitioned is given as a list Ln = (X1, ..., Xn) from which items are packed or scheduled one by one. If H denotes an MS heuristic, then H(Ln, m) denotes the makespan of the m-processor schedule generated by H for the tasks in Ln. In the BP problem the bin capacity is only a scale factor, so we take c = 1 without loss of generality. Thus, if H denotes a BP heuristic, then H(Ln) denotes the number of unit capacity bins in which H packs the items of Ln.

Merely deciding whether a list of numbers can be partitioned into two subsets with equal sums is NP-complete, so, as one would expect, both the BP and the MS problems are NP-complete. Thus, one is unlikely to find an



The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement